CF/AtC乱做记录 | zjc's blog

每50题就开个新文章。

马上也快退役了，干点自己想干的事吧，别太功利了。

早就想开这个记录了，碍于之前学校各种各样的题单让我没时间做（其实时间是颓没的）。

现在感觉做啥都也无所谓了，开始记录吧！

本博客就简单记录一下，就记个大体思路。

1.CF1773G Game of Questions *2800

很神的状压DP啊，发现人数不多遂想到状压一下人数，设 $dp_S$ 表示场上只剩状态为 $S$ 的人，然后Genie赢的概率。

难点在于转移，我们并不知道有哪些问题之前被问过，但是状压问题的话就太夸张了。注意到一个性质，一个问题问几遍都和问一遍等价。这个性质看上去很显然，但却是转移的关键所在。设 $w_{S,T}$ 表示从能让状态 $S$ 变成状态 $T$ 的问题个数。预处理出 $w$ 再DP即可。

2.CF1775F Laboratory on Pluto *2500

牛的数学题，感觉真不错。第一问是简单的，一边取成 $\sqrt{n}$ 就是最小值。虽然我不是很会证，但你要枚举根号做好像也能过。

主要是这个第二问的数数就比较困难，考虑连通块的形式，就是一个矩形四缺口这种感觉，但是缺口一定是阶梯状的，就意味着求的是拆分数，可以dp求解。求完了一个角上的方案数就背包一下就行了。这题牛就牛在单步似乎都很好想，合在一起就有点困难了，但也其实还好，我自己做的时候就是拆分数那里有点不会，可以看看 P1025 srf的那篇DP题解，学一下k部拆分数的DP求法，感觉挺妙的。

3.AGC045A Xor Battle *2000

很有趣的一道博弈论题目。还好开了题解，不然死都不会做。考虑从后往前枚举，设集合 $S_i$ 表示从 $i$ 开始走，有哪些数能使0赢。考虑使用线性基进行转移即可。

4.AGC043D Merge Triplets *2700

非常秀的DP题，考虑答案的形状。答案排列按下降段划分每一段都不会超过二，而且长为1的段一定比2的多。

此乃本题第一秀。于是我们设计出状态 $dp_{i,j}$ 表示填到了第 $i$ 个位置长为1的段比长为2的段多了 $j$ 个的方案数。

考虑转移，观察排列，按照偏序关系建出一棵外向树，用数拓扑序的方式进行DP，此乃二秀。

5.ARC093E Bichrome Spanning Tree *2500

非常牛的数数题。考虑原图的最小生成树，如果mst都比 $x$ 大，那肯定是没有方案的。如果mst和 $x$ 一样大。那就意味着能够成mst的边必有异色，这个是好数的。另外一种困难些，考虑钦定一条边在权为 $x$ 的生成树中，那他这棵生成树是包含它的最小生成树，必定与一棵原图的最小生成树有交，构成最小生成树的边一定同色，这样数数就方便了许多。

6.ABC279G At Most 2 Colors *2400

牛的DP题，考虑状态设计，设 $dp_{i , 1/2}$ 表示填到 $i$ 这个位置时，最后 $k-1$ 个位置有几种不同颜色，$k-1$ 这个地方设计的有点巧妙，我也是这个地方想不到。如果光设计个 $k$,那么 $i - k$ 这个位置填啥又跟 $i$ 这个位置填啥没关系，会影响转移，换成 $k-1$ 就不会了。关键是求答案时答案对吗？看看自己的方程，是不是同时保证了后k个也只有两个颜色了呢。

7.CF1385G Columns Swaps *2300

2-sat 板子，无需多言

8.ABC281G Farthest City *2300

看你想不想的到BFS树结构，想到了就是一道简单DP。

9.CF1657E Star MST *2200

找到边权之间的偏序关系，有一个跟上一题类似的DP。

10.ARC103F Distance Sums *2800

妙妙构造题，非常的神奇。一看一个没思路。观察一下，发现d值最大的一定是某个叶子，d值最小的一定是重心。

然后就考虑从叶子开始向上构造推测父亲是谁（钦定重心为根）。类似换根DP去转移然后二分推出父亲即可。

11.ARC006D Median Pyramid Hard * 3000

人才题。考虑二分？为什么要考虑这个？或许是因为中位数题好多都要二分。二分什么？二分答案。我们将大于二分出来的东西的数都看作是1其他看作是0，那么只需要关注顶部数的01情况，而这取决于最靠近中间的相同数对是0还是1，于是做完了。

12.CF1659E AND-MEX Walk *2200

考虑答案的范围，容易发现答案只有可能是0,1,2，分别使用并查集判断一下即可。

13.CF1473E Minimum Path *2400

模拟赛原题，有点牛的。要求的式子很有最短路的感觉，式子的本质是抽出一条最长的换上一条最短的。

OK，比较美妙的一步来了。要想用最短路去求解，那么必须把后面那一坨塞进 $\sum$ 里面去。

刚刚想了式子的本质，现在扩展一下，任选两条边，用一条去换另一条的最小值，此时茅塞顿开，这个问题就可以用分层图最短路进行求解了。

14.ARC127E Priority Queue *2700

比较感性的一个题。正难则反，考虑计算被删除的集合的方案数，容易发现每个删除位置都有取值范围，而且还有一个奇奇怪怪的性质，每一次删的数都可以是离该次删除最接近的1，这样不会影响方案数，交换法不难证明。此时上文的取值范围也可以用类似于括号配对的方法求出来。既然集合计数那我就钦定一下数列是单调递增的，同时发现如果单增数列能取到，单增数列的排列也能取，反之同理，于是乎DP即可。

感性就感性在每个性质看上去好像很显然证起来还是有一些困难的。

15.ARC180D Division into 3 *2700

放在任务里面吃灰的，今天终于给他做了。算是一种套路题吧？观察到区间最大值一定会被取到，分类讨论一下在哪个段。

在A/C段中就用扫描线算答案，在B中就只让AC取左右端点各一个，这题也就完了。感觉还是很神奇，从一个显然的性质推导出来整个做法

16.CF335F Buy One, Get One Free *3000

反悔贪心神仙题，反悔策略怎么想出来的，大概率是用归纳法。显然是把序列从大到小排个序，同样代价的物品就分为一组，按组进行考虑。维护一个小根堆记录当前白嫖的东西的价值，每次先算出当前这一轮一开始就可以白嫖多少个，先不忙压入小根堆避免造成影响。剩下的东西就考虑是买好还是不买好，按反悔贪心策略执行即可（不想细说了，毕竟不是题解）。

17.CF516D Drazil and Morning Exercise *2800

询问次数只有50，考虑使用大于 O(n) 复杂度的东西执行单次询问。

思考怎么样才能使联通块的计算更加方便，钦定一个根，枚举联通块的根。

然后呢，要是联通块的 max，min 的差值求起来方便就更好了。

不妨让他随层数单调，如何实现，以f最小的点为根即可，每次询问树上差分。

18.ARC167C MST on Line++ *2400

考虑数每个 $a_i$ 在 MST 中的出现次数。容易发现 $a_i$ 的顺序与答案没啥关系。接下来的一步比较神秘，考虑一个子问题，如果只能选小于等于 $a_i$ 的边，最多能选多少条，把每个排列的答案加起来，记为 $f_i$，那么 $ans=\sum_{i=1}^{n} a_i \times f_i$，组合求 $f_i$ 即可。

19.ARC123D Inc, Dec - Decomposition *2100

简单题啊，居然有自己能很快做出来的题，尝试构造 $b,c$，这是简单的，感性理解一下，然后三分一下偏差值就是答案了。

三分可以理解正确性，但是为什么想我那样构造就是答案了呢，其他的构造方法对吗？感觉很奇怪啊。

20.CF1270H Number of Components *3300

先发现一个性质：如果 $l$ 和 $r$ 在一个联通块内，那么 $[l , r]$ 就都在一个联通块内，证明是容易的。

发现了这个性质之后，我们只需要求 $i$ 和 $i + 1$ 是否在一个联通块内。具体的判断方式是 $\min_{j=1} ^{i} a_j \ge max_{j=i+1}^{n} a_j$。记 $w=max_{j=i+1}^{n} a_j$，把数组内大于 $w$ 的设为 $1$，否则设为 $0$。如果 $i$ 和 $i + 1$ 不在同一联通块内那么二进制序列会长成 $11…100…0$ 这个样子，对于每个w维护一下10段的个数即可。

21.CF1548E Gregor and the Two Painters *3400

可以说是一种套路题吧，数网格联通块通用方法就是选个主元，去数有多少个主元，转化成求解偏序问题即可。

注意主元和联通块要有双射关系，不然就假了。这个方法也可以做 SCCPC2024 A 虽然那个题有更简单的方法。

22.CF1656G Cycle Palindrome *3200

先考虑构造一组满足回文的排列，再考虑交换相同值的位置使得在同一个环中。

然后再四个四个地换，判一下就行。正确性证明是困难的，不证了。

23.ARC156D Xor Sum 5 *2600

记一个牛逼结论：若组合数 $\binom{n}{m}$ 是奇数，那么在二进制下，m是n的子集

推论：$\binom{n}{c1,c2,c3…ck}$为奇数，那么c是n的某一子集的一组二进制划分

我们就记 $c_i$ 表示第 $i$ 个数的出现次数，当他的sum有贡献时，他就是上文的推论。

所以发现最多40个 $c_i$ 是非零的，于是乎就可以DP了。

24.ABC271G Access Counter * 2300

很难不想到矩阵快速幂，但是问题在于我怎么构造矩阵，这是本题的难点。

首先是容易设计出基本DP的， $dp_{i,j}=\sum_{k=1}^{24}dp_{i-1,k}\times calc(k,j)$

calc通过一些基本数列手段可以是可以处理出来的，然后挂到矩阵这题也就结束了。

25.CF1042E Vasya and Magic Matrix *2300

朴素的期望DP，好像期望DP都是倒着的，大概就是从终状态转移到始状态的意思。

矩阵的壳是个幌子，根本无需在意，把每个东西单拎出来按权排序后DP即可。

26.CF1552E Colors and Intervals *2300

牛的构造题，先观察到每次选的两个点之间一定没有和它们同色的点，不然一定不优。

每个东西被覆盖的次数限制很奇怪，考虑它的意义是什么。看见分母的 $k-1$ 不难联想到同一颜色的段数，那么考虑按段的编号分类，每个段就选限制个颜色即可。

27.CF1635F Closest Pair *2800

结论题，设 $L_i$ 表示 $i$ 左边第一个 $w$ 小于等于 i的点，$R_i$ 同理。

那么答案就在 $[L_i,i],[i,R_i]$ 中。转化为二维数点问题即可。

28.CF1868C Travel Plan *2400

式子题，考虑对于满二叉树怎么做，会了这个就把原数拆成 $logn$ 个满二叉树即可。

具体的，枚举最大值，记 $ans_i$ 表示最大值 $\le i$ 的答案，那么最后答案就是 $\sum_{i=1}^{m}i\times (ans_i - ans_{i-1})$

对于具体的转移不多赘述，主要就是记两个东西，一个表示这个子树所有东西到根的答案和子树内所以东西的填法的和。

29.CF599E Sandy and Nuts *2600

困难的，状态想错了导致举步维艰，想到状态之后这题并不困难，主要是处理限制的时候要稍微注意一下细节。状态是 $dp_{i,S}$ 表示以 $i$ 为根的子树内的点集为 $S$ 的合法方案数。方程就是 $dp_{i,S}=\sum_{T\in S} dp_{u,T}\times dp_{i , S\oplus T}$。使用钦定技巧避免算重。

30.CF623D Birthday *2700

难点解析：揣测出题人。

为啥不让你求模意义下的答案，精度误差为啥允许开这么大，样例解释为啥没有计算过程？有没有种可能，真实值根本算不出来？

想到这里这题大概也就迎刃而解了，计算k轮猜到答案的概率。直接做不好做，考虑容斥进行计算。具体的，计算在最多 $k$ 轮的时候结束的概率。要是知道每个人被猜到几次的话就很容易算概率了。列出式子，每一步贪心即可。收敛速度较快，计算 $3e5$ 次即可通过此题。

31.CF407D Largest Submatrix 3 *2700

不难想到 $O(n^4)$ 暴力，枚举行的上下界，对列跑双指针。这个算法难以优化，更换枚举次序。枚举左右界再枚举下边界，类似于区间DP得去转移答案。（子矩阵背景的题目从来没有自己做出来过，呜呜呜）

32.CF1844G Tree Weight *3000

牛逼题目，这辈子没见过这么秀的。

首先容易把 $d_i$ 拆成 $dep_i + dep_{i + 1} - 2 \times dep_{lca(i,i+1)}$

然后就会发现这个东西非常不优美，要是能够拆出来的东西少带点变量就好了，因为 $dep_1$ 我们是知道的，他就是0。少带点变量就会使得这个式子可以递推了！注意到lca前面有个系数2，对等式两边取个2的模这个东西就没了！ 然后我们就可以考虑按二进制位进行递推了。具体的，设 $ans_{i,j}\equiv dep_{i} \mod 2^j$。那么有 $ans_{i,j}={(d(i-1,i)-ans_{i-1,j}+2\times ans_{lca(i-1,i),j-1})} \mod 2^j$最后判一下-1即可。注意力惊人的人可以独立做出来，可惜我不是。

33.CF1762D GCD Queries *2100

似乎是比较容易的。其实无非就是就是让你每两次操作排除一个非零的数。按顺序遍历配合上指针优化再加上简单的分讨即可。

34.CF1406E Deleting Numbers *2600

非常厉害的交互！有点人类智慧的感觉。

首先是容易想到一个每个质数操作两次在log一下的方法，算算发现操作次数会超。

考虑优化。显然对于上述做法而言，质数这个点是不会变的，那能不能让没啥用每个质数只操作1次呢。

可以的，我们依次对每个质数操作B，然后计算出理论答案，要是不一样的话我们就check一下它的幂次。

可是这样对于最小的质数而言，我们就没法求了。所以每过根号次操作就做一遍 A 1。要是有出入就把块内所有东西都判一遍即可。

35.CF1033E Hidden Bipartite Graph *2800

也是非常厉害的交互！更加的人类智慧！

积累一种不一样的判二分图的trick：图中抽一棵生成树，看一下奇数层的点之间有没有连边，偶数层之间有没有连边。

对于这个题而言我们可以先用 $2nlogn$ 次询问分治的去问出一棵生成树来。然后我们再在奇偶层之间随机分治看看有没连边。很巧妙的是这个随机分治，每次把点集大小除以二而且每一层期望操作次数只有两次，非常聪明啊！

36.CF1863G Swaps *2800

套路题？容易想到 $a_i$ 向 $i$ 连条边。然后观察一次操作带来的影响，发现一次操作带来一个自环。同时可以构建出一个双射：能生成的序列可以这样构成：如果 $i$ 的入边被操作过，那么这个位置就是 $i$，否则就是一条未被标记的出边指向的点权，这是容易计数的，注意在联通块为环时特殊处理一下即可。

37.JOISC2015 F 合鍵

非常好题目，让我认识到自己的不足：对于奇怪的模型就失去了分析的能力。

容易想到 把 $l,r$ 拆开一起排序，分讨每一段的贡献情况，然后DP统计贡献即可。

38.ABC373G No Cross Matching *2400

场上的时候有种流子的感觉，但是不会建模。现在会了神秘贪心。

非常厉害的转化，相交线段可以通过交换变得不相交，这会使得总距离变短，那么我们是需要让总距离最短即可，按照冒泡排序模拟即可。

39.Yahoo Programming Contest 2019 Odd Subrectangles *2600

容易想到转化为异或为1。考虑现在已经选出了一些行，那些列符合答案，记第 $i$ 列的异或和为 $c_i$ ，只要有一个 $c_i$ 等于1，那么这就意味着方案数是 $2^{m-1}$，其他列情况任选，用这一列来调整即可。那么现在思考怎么选行能够使得至少有一个1，把每行当成一个二进制数，这个问题就转化成了怎么选使异或和部位0，为0是简单的，记 $x$ 表示线性基的大小，然后异或和为0的方案数就是 $2^{n - x}$，证明原理和刚才一样。

40.CF513D Constrained Tree *2600

自己的思路是转化成偏序问题后瞎构造，不会证明正确性，也没有实践，来记个题解做法。

大概就是去dfs，dfs(u) 表示 $u$ 是一个叶子时的可行性，然后简单判断几下递归下去是简单的。

41.CF1699E Three Days Grace *2600

这题DP？我咋想到？分析整个删数的过程，容易发现就是分解而已。想到去枚举一个最小值，让最大值最小，考虑 $dp_{i,j}$ 表示分解出来最小的数比 $i$ 大，最大的数最小是多少，发现转移是调和级数级别的，双指针找答案即可。

42.CF547D Mike and Fish *2600

这种染色问题再配上这个网格图背景，很难不让人想到二分图染色。考虑怎么进行染色，有一种很简单的方法是相同横或纵坐标的点两两配对，要是剩一个就不管了，不难证明这是正确的。

43.CF1253F Cheap Robot *2500

感觉是困难的。遇到这种图上多询问的问题就先不要往什么LCT这种东西方面去思考，实在不行再试试，然后考虑对于单个询问怎么做，要求的答案根据什么量推出来，把图上有用的东西再留下来，看看在树上怎么做。这题就这样的，看两个相邻的充电站想要抵达对 $c$ 的限制是什么，化成一个关于c的不等式，然后放在重构树上询问就可以了。

44.CF53E Dead Ends *2500

似乎是简单的，反正我秒了。看见数据范围这样的小，看来是DP状态需要两个状压维，那DP状态就出来了, $dp_{S,T}$ 表示形成的生成树是 $S$ 集合，度为一的点是 $T$ 集合，发现要算重，再回头看看转移方程，是不是方案算了 $popcount(T)$ 次呢？所以除一下就好了。

45.CF1485F Copy or Prefix Sum *2400

容易设计一个 $nV$ 的DP， $f_{i,j}$ 表示填到 $i$ 和为 $j$ 的方案数，列出转移方程然后观察，一个相当于是右移，另一个相当于是上一位所有的和，于是乎用 map 维护一下DP过程即可。

46.ARC059F Unhappy Hacking *2400

难怪是上古ARC，这题放现在最多*1200，小糖DP，不想写了。

47.ARC058F Iroha and Haiku *2500

这个是真的educational啊，启发到我了。重要观察： $A+B+C \le 17$。于是乎考虑状压DP。

$dp_{i,S}$ 表示填到第 $i$ 个数，可组成的后缀和集合为 $S$ 的方案数。最后求答案，正难则反。

48.ARC060F Best Representation *2800

顶级诈骗题，一眼看上去直接傻了。后来突然发现，只要不是一开始就不是周期串或者全相等那么第一问答案就是2，下一个模1e9+7就是个幌子。这下就清楚了，好像也就结束了，kmp看看周期即可。

49.ARC061E Snuke’s Subway Trip *2400

可能是因为建虚点这个trick已经很普遍了吧，所以这题评了个绿，想到建虚点就做完了。

50.ARC157E XXYX Binary Tree *2900

感觉是个傻子题，但是我没做出来，差一个观察。

观察1：可以通过 B 和 C 算出来应该有几个叶子填 Y ,几个非叶子填 Y。

观察2：子树内填非叶子 Y 的数量是个区间， $[0,mx]$

想到这里就是个简单题了，树上背包即可。