CF/ATc随机乱做

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

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

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

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

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\) 里面去。

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