带星号的表示 vp。
\(*\) CF Round 601 Div.1
做出 A 和 B1。
B2. Send Boxes to Alice (Hard Version)
考虑 \(a\) 的前缀和数列 \(S\),在 \(a\) 中移动一个数,相当于在 \(S\) 中单点 \(\pm 1\)。并且 \(S_n\) 一定是不变的,且最终的公约数一定是 \(S_n\) 的约数。显然只需要枚举所有质数 \(p\mid S_n\)。并且“所有 \(S_i\) 都是 \(p\) 的倍数”与“所有 \(a_i\) 都是 \(p\) 的倍数”是等价的。
所以,显然答案就是 \(\sum_{i=1}^{n-1} \min(S_i\bmod p,p-(S_i\bmod p))\),并且也可以保证 \(S_i\) 单调不减。时间复杂度 \(\mathcal{O}(n\omega(n))\)。
\(*\) CF Round 604 Div.1
做出 A,B,赛后五分钟做出 C。
B. Beautiful Sequence
首先将所有 \(0,2\) 按顺序排起来,得到 \(00\dots0022\dots22\) 这样的序列,然后有两种情况:
- 第一个 \(1\) 或 \(3\) 插入在开头;
- 第一个 \(1\) 或 \(3\) 插入在开头的后面一个位置。
分类讨论这两种情况,然后检查是否符合要求。
代码:https://codeforces.com/contest/1264/submission/157810494。
C. Beautiful Mirrors with queries
假如没有修改,设 \(f_i\) 为顺利通过 \(i\) 所需的期望步数,那么 \(f_i=p_i(f_{i-1}+1)+(1-p_i)(f_{i-1}+f_i+1)\)。解得 \(f_i=\frac{f_{i-1}+1}{p_i}\),也即 \(f_i=\sum_{k=1}^i (\prod_{j=k}^i p_j)^{-1}\)。通过一点预处理,就能 \(\mathcal{O}(1)\) 求出通过一段区间的期望步数。
所以用 std::set
维护即可。
\(*\) CF Round 733 (Div.1 + Div.2)
做出 A ~ D,赛后做出 E。
D. Secret Santa
一开始写了个基环树 dp,还写错了。
首先,设 \(a\) 中不同的数字有 \(k\) 种,答案恰好可以取到 \(k\)。
设答案是 \(p_1,p_2,\dots,p_n\),我们钦定任意 \(k\) 个位置 \(i_1,i_2,\dots,i_k\),使得 \(a_{i_1},a_{i_2},\dots,a_{i_k}\) 两两不等,并使得这些位置的 \(p_{i_x}=a_{i_x}\)。记 \(b_1,b_2,\dots,b_{n-k}\) 表示此时还没确定 \(p\) 的位置,\(c_1,c_2,\dots,c_{n-k}\) 表示此时还没被使用的位置。
然后有两种情况:
- 假如 \(k=n-1\) 且 \(b_1=c_1\),那么除 \(b_1\) 以外的所有元素形成了一个环,需要略微调整这个环使得 \(b_1\) 被 fulfilled。
- 否则,这里有一种有趣的做法:随机打乱 \(b_1,b_2,\dots,b_{n-k}\),如果 \(\forall i,b_i\neq c_i\) 的话,就停止,否则再次打乱。这个过程期望只需要做 \(e\approx 3\) 次。
E. Minimax
分五种情况讨论。吐了。
Edu Round 129
做出 A ~ D。
\(*\) CF Round 606 Div.1
做出 ABC。
C. Beautiful Rectangle
设序列中 \(x\) 的出现次数是 \(c_x\),有一个结论:设矩形大小为 \(h\times w\) 且 \(hw=n\),假如 \(\max\limits_x \{c_x\}\le \min(h,w)\),那么序列中的所有数都可以放在这个矩形中。
这是因为,在最坏形况下,所有数的出现次数都等于 \(\min(h,w)\)。不妨设 \(h<w\),那么考虑如下形式的构造即可:
\[\begin{matrix} 1 & 2 & \dots & w-2 & w-1 & w\\ 2 & 3 & \dots & w-1 & w & 1\\ 3 & 4 & \dots & w & 1 & 2\\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ \end{matrix} \]假如有一些数的出现次数 \(<\min(h,w)\),那么可以钦定每 \(\min(h,w)\) 个为一组,并认为每组内的数相同。
所以枚举 \(h\times w\) 并找到 \(h\) 和 \(w\) 最接近的情况,对于 \(h\times w\) 最大、且所有数都可以放进去的方案,按照上面的方法构造即可。
代码。
\(*\) CF Round 609 Div.1
做出 A。
B. Domino for Young
将杨表黑白染色,可以发现一个多米诺骨牌恰好覆盖一个黑格和一个白格。设黑格的数量是 \(c_1\),白格的数量是 \(c_2\),答案的上界就是 \(\min(c_1,c_2)\)。
将相邻的黑格和白格连边,然后做二分图最大匹配。假如存在一个黑格 \(u\) 和一个白格 \(v\) 没有匹配,我们将二分图上 \(u\to v\) 的路径上的边全部取反,即可让它们匹配。所以答案就是 \(\min(c_1,c_2)\)。
CF Round 795 Div.2
做出 A ~ D。
E. Number of Groups
用并查集维护连通块。按照右端点从小到大处理每个线段。可以发现,对于每个连通块,我们只需要记录其中右端点最大的一个红色线段和一个蓝色线段。用两个 std::multiset
维护。
对于每一条线段,在 multiset 上二分找到所有与它有交的线段,然后逐一合并这些线段所在的连通块即可。注意区分 std::set
和 std::multiset
。
代码。
CF Round 800 Div.1
做出 AB。
C. Keshi in Search of AmShZ
我为啥想不到。我为啥想不到。我为啥想不到。
设 \(D_u\) 为 \(u\to n\) 在最优策略下需要的天数,那么 \(D_u\) 就是没被 block 掉的 \((u,v)\) 的 \(\max D_v\),加上被 block 掉的个数加一。
将所有边的方向反转然后 Dijkstra。开始时所有边都被 block 掉,每次从堆中取出一个点 \(u\),并更新所有与 \(u\) 相连的 \(v\) 的答案。
假如固定一个点 \(u\) 并考虑 \(D_u\) 是如何被更新的,因为 Dijkstra 的过程中,取出的点的 \(D\) 单调不减,所以当前的 \(\max D_v\) 就是最新被取出的这个点的 \(D\)。对于那些没有被取出的边,它们一定会被 block。
代码。
CF Round 818 Div.2
做出 A ~ E。
Edu Round 135
做出 A ~ E。Performance 达到了 2500,并且上了 Master,可喜可贺。
CF Round 821 Div.2
做出 A ~ D2,Performance 2277。
E. Conveyor
考虑一组询问 \((t,x,y)\):我们算出有多少个时间 \(t'\le t\) 使得在 \(t'\) 时间 \((x,y)\) 上有 slime,设这个数是 \(f(t,x,y)\)。假如 \(f(t,x,y)=f(t-1,x,y)\) 则答案为 Yes,否则为 No。
考虑这个 \(f(t,x,y)\) 怎么算。注意到任意两个 slime 都不可能重合,且前 \(\max(t-x-y+1,0)\) 个 slime 都有到达 \((x,y)\) 的可能性,因此在 \((0,0)\) 处放 \(\max(t-x-y+1,0)\) 个 slime,并 DP 算出有多少个到达了 \((x,y)\) 即可。
CF Round 822 Div.2
做出 A ~ E,Performance 2313。
E. Rectangular Congruence
假如我们构造出了一个矩阵 \(A\),它除了对角线的限制不一定满足以外,其他限制均满足,那么对于所有 \(i\),把第 \(i\) 行整体加上 \(b_i-A_{i,i}\) 就可以让 \(A\) 满足对角线的限制。
而满足限制的 \(A\) 是好构造的,例如 \(A_{i,j}=ij\bmod n\)。
F. Zeros and Ones
我终于学会数位 DP 的写法了,感动。
稍微推一下就可以得到,答案就是 \([0,m)\) 中整数 \(x\) 的个数,使得 \(\operatorname{popcount}(x)\not \equiv \operatorname{popcount}(x+n)\pmod 2\)。我们设 \(f_{i,j,k,lim}\) 表示考虑 \(x\) 的最低的 \(i\) 位,当前 \((\operatorname{popcount}(x)-\operatorname{popcount}(x+n))\bmod 2\) 的值是 \(j\),计算 \(x+n\) 时从 \((i-1)\) 位到 \(i\) 位的进位是 \(k\),\([x\ge m]\) 的真假是 \(lim\) 的 \(x\) 的个数。这样就可以转移了,时间复杂度 \(O(t\log n)\)。
f[0][0][0][1] = 1;
For(i, 0, B - 2) {
int ncur = (n >> i) & 1, mcur = (m >> i) & 1;
For(j, 0, 1) For(k, 0, 1) For(lim, 0, 1) {
For(x, 0, 1) f[i + 1][j ^ ncur ^ k][x + ncur + k > 1][x == mcur ? lim : (x > mcur)] += f[i][j][k][lim];
}
}
cout << f[B - 1][1][0][0] + f[B - 1][1][1][0] << '\n';
标签:dots,比赛,记录,所有,CF,CodeForces,做出,Div.1,Round
From: https://www.cnblogs.com/alan-zhao-2007/p/codeforces-contest.html