题解1203 div cf
Educational Codeforces Round 134 (Div.2) D 题解
题目链接 D. Maximum AND 题目大意 给定两组序列 \(a\) \(b\),长度为 \(n\) ,现有一新序列 \(c\),长度也为 \(n\) 。 其中,\(c_i = a_i \oplus b_i\) 。 定义 \(f(a,b) = c_1\&c_2\&……\&c_n\)。 现在你可 ......
Educational Codeforces Round 128 (Rated for Div. 2)
添加链接描述 C题显然二分0的数量,然后双指针,算一下前缀和后缀1的数量即可。 #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<map> #include<vector> #include ......
TheForces Round #24 (DIV3-Forces)11.1
TheForces Round #24 (DIV3-Forces) A - Banis and Cards 思路:不大于n的m的倍数的和 #include<bits/stdc++.h> using namespace std; #define int long long //#define int ......
CF1868B1 Candy Party (Easy Version) 题解
Problem - 1868B1 - Codeforces Candy Party (Easy Version) - 洛谷 喵喵题。首先每个数最终肯定变成 \(\overline a\) ,如果 \(\overline a\) 不是整数显然无解。 然后记 \(b_i=a_i-\overline a\ ......
abc194f O(nk)题解
前言 洛谷唯一的题解似乎是 \(O(nk^2)\) 的,怎么卡过去的orz 这里提供一种与 AT 官方题解时间复杂度相同的 \(O(nk)\) 做法。 Solution 题意很显然,就不解释了。 一眼丁真,考虑数位 dp。 设 \(dp_{i,j}\) 表示做到第 \(i\) 位,不同的个数有 \( ......
CF743C Vladik and fractions
大胆拆开,变成两个 \(\frac{1}{n}\),令 \(z=n\),那么 \(\frac{1}{x}+\frac{1}{y}=\frac{x+y}{xy}=\frac{1}{n}\)。 注意到分母是乘积,分子是和,可以令 \(x,y\) 的单位为 \(n\)。设 \(x=kn\),那么 \(x+ ......
Codeforces Round 906 (Div. 2)
Codeforces Round 906 (Div. 2) 比赛链接 A. Doremy's Paint 3 题目链接 判断给定的数组是不是满足a1+a2=a2+a3=a3+a4=......=an-1+an A思路: 这个题一开始没有读仔细问题,导致一时间出错了,后来读清楚问题之后发现其实这个数组 ......
[ARC159F] Good Division 题解
[ARC159F] Good Division 题解 首先对于题目要求的划分方式转化一下,转化为划分的每一段都没有 绝对众数,可以证明这与题目中的要求是完全等价的,证明如下: 充分性:考虑构造一种操作方法,就是每次操作都消去一个出现次数最多的数,按照这样操作可以保证每次操作之后该区间仍然不会出现绝对 ......
10.30 CF1685 题解
10.30 CF1685 A.Circular Local MiniMax 题意 给你 \(n\) 个整数 $ a_1, a_2, \ldots, a_n $ 。 问有没有可能将它们排列在一个圆上,使每个数字严格地大于其相邻的两个数字或严格地小于其相邻的两个数字? 题解 直接排序然后按照 \(1,4 ......
题解:[SCOI2008] 城堡
应该是联赛前最后一次任性了,浪费的时间有点多,不过也揭露了我的基础知识和代码能力都很弱的问题,得加油啊。 先 sto dwt。 给定一棵基环树森林,起初有 \(m\) 个点已被选进 \(S\) 里,你需要再选 \(k\) 个点加入到 \(S\) 中,最小化其余点到 \(S\) 距离的最大值。 这个问 ......
Codeforces Round 907 (Div. 2) B. Deja Vu(二分+后缀和+位运算)
Codeforces Round 907 (Div. 2) B. Deja Vu 思路: 预处理31位的 \(2^x\) 存在\(tmp_i\) 对于输入\(a_i\),通过查找最后一个二进制1位置,存在\(x0_i\) 由题意可知,对于输入的\(x\),如果有\(a_i\)可整除\(x\),则会使 ......
Luogu P3862 数圈 题解
看数据范围 ——题记 传送门 考虑记 \(f_i\) 表示有 \(i\) 个点的完全图的圈数 \(g_i\) 表示有 \(i\) 个点的完全图中一个点到另一个点不同路径的方案数 \(ans\) 表示答案 容易知道递推式 \[f_i=g_{i-1} \times C_{i-1}^2+f_{i-1} \ ......
「Note」CF 杂题集 6
前言 难度:CF 2600-2700(有一道是 2500) 别问我为啥没有 1 到 5。 \(\color{blueviolet}{CF1473F}\) 此题是坏题,他卡你空间。 每一个元素有选或不选两种状态,并且有依赖项,元素的贡献有正负,数据范围不大,可以自然联系到最大权闭合子图,采用最小割模型 ......
《CF1889C2 Doremy's Drying Plan (Hard Version)》 解题报告
考场上不会做。 如果考虑删掉哪些区间实际上不太可做。正难则反,转化贡献,考虑哪些点可以有贡献。 显然一个点如果可能有贡献,那么当且仅当覆盖它的区间 \(\le K\) 个。 于是我们记一个状态 \(f_{i,j}\) 表示前 \(i\) 个点中, \(i\) 是最后一个贡献的点,已经删除了 \(j\ ......
CF911G Mass Change Queries
CF911G Mass Change Queries 题解 首先这题有一个很一眼的分块做法,并且由于只需要维护颜色,所以会极其好写。 对每个块维护并查集,表示整块中颜色变成了哪个颜色,每个位置单独也指向一个颜色表示最初指向哪个颜色,这样就很好维护了。 但是发现值最大只有 \(100\),所以考虑和值 ......
题解 P2217 [HAOI2007] 分割矩阵
题目描述 将一个矩形分割成 \(n\) 个小矩形,每个小矩形的总分为这个矩形内所有数的和。求各矩形总分均方差最小值。 具体思路 先来几个定义。 均方差:$$\sqrt{\frac{1}{n} \times \sum_{i=1}^n (a_i-avg)^2}$$ 方差:$$\frac{1}{n} \t ......
CF1889C2 Doremy's Drying Plan (Hard Version) 题解
Description 有 \(n\) 个点和 \(m\) 条线段,你可以选择 \(k\) 条线段删除,最大化未被线段覆盖的点的数量,输出最大值,\(n, m \le 2 \times 10^5, k \le \min(m, 10)\) Solution 一道比较好玩的 dp 题。建议评级紫。 单独 ......
CF1039D You Are Given a Tree
CF1039D You Are Given a Tree 更好的阅读体验 一种神奇套路:对答案根分,根分的依据是链的长度和答案大致是一个成反比的关系。 考虑确定了 \(k\) 怎么做。因为一个点只能在一条链里,所以 dfs 的时候如果能拼成一条链就一定会拼成一条链,不然就把贡献传给父亲继续尝试。 对 ......
Codeforces Round 907 (Div. 2)
Codeforces Round 907 (Div. 2) A. Sorting with Twos 题意: 给一个长度为n的数组,可以做任意次以下操作:选择一个整数m,将1-2m 的数减1。若能使数组变为一个单调递增的数组则输出YES,否则输出NO 分析: 只需要保证2m+1 -2m+1单调递增即 ......
Sasha and Array 题解
Sasha and Array 题目大意 给定一个长为 \(n\) 的序列 \(a\),支持以下操作: \(\forall i \in[l,r],a_i\gets a_i +x\)。 求 \(\left(\sum\limits_{i=l}^{r}F_{a_i}\right)\bmod (10^9+7 ......
CF GYM 104020 G
link 首先,因为 \(w_i\le 10^6\),有点大,所以我们想方设法把他变小一点。 设一个快为 \(w_i=k\times x+r\)。其实,如果我们把他分为 \(x\) 个大小为 \(k\) 的块,然后一个大小为 \(r\) 的块是最优的。因为切成其他的大小的块,我们可以调整成这种切法, ......
[CF576E] Painting Edges
Painting Edges 动态加边和二分图容易想线段树分治,分别维护 k 种颜色的并查集。 不过每条边的存在时间不能确定。 设边 i 的两次操作的时间为 \(x_i,y_i\),那么对于 \(t\in[x_i+1,y_i-1]\) 有两种情况,颜色改变或改色不变。 则我们把每次操作影响的时间放在 ......
第四届辽宁省大学生程序设计竞赛部分题解
2023辽宁省赛 A:欢迎来到辽宁省赛 题目描述 小Z躺在床上看了看表 , 现在是13:30 , 2023辽宁省大学生程序设计竞赛的报名将会在 14:00 截止。 然而不急 , 省赛的参赛队伍还没有向他提交名单。小Z知道 , 只要 3 分钟他就可以完成报名 , 完成汇款。 现在他想知道 , 队伍要在 ......
[ABC326D] ABC Puzzle 题解
题意: 给定整数 \(N\),字符串 \(R,C\),构造满足以下条件的 \(N\times N\) 矩阵: 1.每一行和每一列中 \(A,B,C\) 各有且仅有一个。 2.第 \(i\) 行的第一个字母等于字符串 \(R\) 的第 \(i\) 个字符。 3.第 \(i\) 列的第一个字母等于字符串 ......
CF1025F Disjoint Triangles
虽然我不懂计算几何,但是两个三角形互相进入,感觉很涩啊! —— By 【】 考虑两个互不相交的三角形,寻找一个方式能够不重不漏地统计它们。 容易发现两条不交的线段 \(A_1A_2,B_1B_2\) 之间,必然存在一条直线将 \(A_1A_2,B_1B_2\) 分在直线两端,且与 \(A_1A_2, ......
CF908H New Year and Boolean Bridges
这说明你那破子集卷积不是万能的。 显然题目要求的图 \(G'\) 是弱联通的,考虑给出的图 \(G\) 中两个点 \(i,j\) 之间 \(G_{i,j}\) 的条件转化为: \(G_{i,j}=\mathtt A\),说明 \(i\) 能到 \(j\) 且 \(j\) 能到 \(i\),则 \(i ......
P4067 [SDOI2016] 储能表 题解
[SDOI2016] 储能表 - 洛谷 题目详情 - [SDOI2016] 储能表 - BZOJ by HydroOJ 一道很好的数位 dp 题 不过这题有一个比较有意思的性质:当 \(n,m\) 为 \(2^k\) 的形式时,最终得到的数组对每一行排序后为 \(0 \sim m-1\) 的排列,如 ......
11 月杂题题解
B1031 T3 区间 波神说这很板,破防了。 考虑如何维护区间的并。 离线,然后扫描线,并把询问挂到右端点。 从左往右,考虑加入一条线段的影响。 假设现在加入第 \(i\) 条线段,对于 \(j\leq i\),维护 \(f(j)\) 表示线段 \(j\sim i\) 的并的长度。 某段位置上一次 ......
8VC Venture Cup 2016 - Final Round (CF627)
A. XOR Equation 最低位没有加法进位产生的影响,考虑从低位向高位 dp。 设 \(f_{i,0/1}\) 表示正在考虑第 \(i\) 位,前 \(i-1\) 位都满足限制,有无进位的方案数。 转移的时候枚举这一位两个数分别填 \(a,b\),\(x_i\) 表示 \(x\) 在二进制下 ......
CF484D Kindergarten
CF484D Kindergarten 题目描述: 有一组数,你要把他分成若干连续段。每一段的值,定义为这一段 数中最大值与最小值的差。 求一种分法,使得这若干段的值的和最大。 数据范围: \(N < 10^6\), \(a[i] < 10^9\)。 思路: 仔细手摸几组数据,你会发现,我们将原序列 ......