Cu 傻逼 来写自己最后一个赛季的第一篇博客啊。
1.CF1225G To Make 1
直接 dp 复杂度寄了啊，考虑找点性质。
有解的必要条件就是存在一组 \(x_i\) 使得 \(\sum \frac{a_i}{k^{x_i}}=1\) 对吧，其中 \(x_i\) 可以看作是一个数在合并过程中被除的次数。
这个其实就是充分的啊。考虑设 \(M\) 是 \(x_i\) 的最大值，那一定至少存在两个 \(x_i=M\) 啊，否则和不可能是 \(1\) 。然后把这俩合并，归纳下去就好了。
所以就转化成找 \(x\) ，就很 trivial 了。
2.AGC032D Rotation Sort
考虑这个区间左/移，实际上可以看成是一个数的移动啊。
先考虑 \(A=B\) 怎么办啊，那就是让移动次数尽量少，那有些数就在站桩，这些桩分成若干段，剩下的数移到对应的位置啊。这个桩还要构成上升子序列。那这个就是求 LIS 。
\(A,B\) 不一样咋个搞啊，考虑中间某个数，左右的桩是 \(l,r\) 的话，如果 \(x<l\) 就往左移，\(x>r\) 就往右移，这是显然；如果存在 \(l<x<r\) ，那让 \(x\) 一起站桩明显更优啊。
就 dp 算算，trivial 了。
3.CF1523F Favorite Game
就首先有个简单 dp 啊，就是 \(f_{S,i,j}\) 分别表示传送门集合，所在的点，当前完成的任务数，那这个太爆了，考虑优化。
如果你站在某个传送门上，那因为这是传送门，所以你不关心你在哪个传送门，就是 \(f_{S,j}\) 表示：传送门集合，完成任务数，值为最小时间。
如果你站在某个任务点上，那这个时间是固定的啊，所以你只关心完成任务数，就是 \(g_{S,j}\) 表示：传送门集合，当前所在任务，值为最大任务数。
啊这个又做完了，互相转移一下就好了啊。
4.ARC113F Social Distance
这个期望先拆成 \(\int_{0}^{\infty}P(X\geq a)\,da\) 啊，这个相当于是 \(y_i\) 范围在 \([x_{i-1},x_i-(i-1)a]\) ,然后需要 \(y_i\le y_{i+1}\) 啊。
固定 \(a\) 的话，你按值域做个扫描线，设 \(f_{i,j}\) 表示到第 \(i\) 段，有 \(j\) 个数已填的概率。转移就是枚举有多少数在当前填了啊。这是 \(O(n^3)\) 的。
然后 \(a\) 没有固定啊，但只要每个分界点大小关系相同，答案就是个关于 \(a\) 的多项式啊，\(a\) 就可以分成 \(O(n^2)\) 段，每段内算出来个多项式积分一下就好了。
把维护的 dp 值换成这个多项式就行了啊。然后复杂度就是 \(O(n^6)\) 的捏。
5.P7295 [USACO21JAN] Paint by Letters P
就是逼数学题啊。就这种平面图的联通块个数，有个欧拉公式啊，就是说 \(F-V+E=C+1\) 啊，\(F\) 是点数，\(E\) 是边数，\(V\) 是区域数，\(C\) 是联通块数啊。
来看这个题，就转化成求子矩阵的图构成的区域数啊。
这个就相对好做了：先把整张图的所有区域求出来，对每个区域随便标记一个块。查询的时候先求个二维前缀和；再减掉不合法的情况啊，那这些不合法的区域它们一定跨过了子矩阵的边界。
所以就枚举边界的每个块块，减掉它所在区域的贡献即可，注意不要减重了哟，复杂度 \(O(nm+nq+mq)\) 。
6.AGC058F Authentic Tree DP
你妈的想到了是有组合意义结果没想到这么逆天的构造啊。
考虑如果除的是 \(n-1\) 答案就是 \(1\) 了啊，为什么呢，这个实际上可以当成是，每次随机选个边删掉，然后两个子树分别做。让整个过程整体一点，就是确定一个删边的排列啊。
但现在除的是 \(n\) 啊怎么办呢。删的是边，但 \(n\) 是点数。如果除的是 \(2n-1\) ，那其实我们把每个边也看成点，这个“边点” 与两个端点相连，就 over 了。
就相当于我们这个排列需要每个边点在两个端点之前出现。容一容，树形 dp 一下就搞完了。
但你他妈的除的是 \(n\) 啊。如果我们让总点数在模意义下也是 \(n\) 是不是其实也可以？
现在就是神来之笔啊，真没想到啊：我们在每个“边点”下面接 \(mod-1\) 个虚点就 ok 了。复杂度 \(O(n^2)\) 。
标签：这个,传送门,复杂度,距离,就是,考虑,杂题,CSP,dp From： https://www.cnblogs.com/cwhfy/p/17608407.html