P4762 [CERC2014]Virus synthesis
Analysis
建立 PAM，考虑以回文串作为转移阶段，则一个状态的前驱是它的半串的所有回文子串，直接转移肯定是不行的，考虑分步优化。注意到子串一定是半串的前缀的后缀，而前缀的后缀为该串在回文树上的祖先结点，前缀为自动机结构中的所有前驱，所以可以在自动机上 DP，如果使用线段树处理祖先问题可以做到单 \(\log\)，而如果直接从祖先往叶子推就可以线性了。
Solution
注意我们只会选最长的回文后缀，所以可以没必要处理树上问题。
P1393 Mivik 的标题
Analysis
一个简单的想法是枚举终点然后拼一个回文串，但是可能回文串会提前结束。所以设 \(f_i\) 表示恰好在 \(i\) 结束的答案，枚举所有 border 并强制在 border 处结束，直接枚举是平方的，使用分治 NTT 可以做到 \(\mathcal{O}(n\log^2 n)\)。
Solution
求所有 border 处的和可以考虑 border 的性质：可以分解成 \(\log\) 个等差数列，那么记录每个公差的答案就好了。
P8360 [SNOI2022] 军队
Analysis
分块+并查集就好了，但是写挂+自带 \(8\) 倍常数，寄了。
Solution
一个优化常数和空间的做法是：对于每个块单独处理询问，这样可以省去对每个块记录信息的时间和空间。
CF1605F PalindORme
Analysis
考虑怎么判断，发现首尾一定是相同的数，并且它们数位为 \(1\) 的部分以后就不用考虑了，所以可以把剩下的数推平然后找相等的数。
这样计数 \(a\) 是简单的，考虑建立一个 \(a,b\) 之间的双射，但是都没有适合 DP 的形态。
Solution
神仙。
观察判断的过程可以发现任意不合法串都包含了恰好一个合法串（如果我们要求奇数串的中间位置一定被包含）。
可以拿这个建立一个合法串到不合法串的映射，即不合法串可以通过合法串拼上一个字符串得到。可以拿这个做一个容斥：设 \(f_{i,j}\) 表示长度为 \(i\)，恰好有 \(j\) 个位置有数的合法串，转移方程：
\[f_{i,j}=g_{i,j}-\sum_{x<i}\sum_{y\leq j}\binom{i}{x}\binom{j}{y}f_{i,j}2^{(n-i)j}h_{i-x,j-y} \]\(g_{i,j}\) 表示所有的序列，\(h_{i,j}\) 表示 \(i\) 个数选位数为 \(j\) 个的不同正整数的方案数，不难使用容斥计算。
P8361 [SNOI2022] 倍增
Analysis
不会。
Solution
打个表，考虑一些特殊的构造能否得到有效的推广。
考虑 \(B=3k-1\) 的解，发现有 \(n=2\) 的解，不难写出式子。
考虑 \(B=3k-1,n=3\) 的解，发现可以通过 \(n=2\) 中间拼一个 \(B-1\) 得到。然后推广可以发现找到一组解之后找到一个进位位置之后插入一堆 \(B-1\) 归纳出来 \(n+1\)。所以只要找到最小解就好了。
然后就比较离谱了，注意有快速搜的方法，然后猜想答案不会很大，把跑得慢的拿出来打表就好了。
P6966 [NEERC2016]Cactus Construction
Analysis
紧急施工。
考虑链怎么做：可以把链尾设为和其它点不同的颜色，然后每次拼上一个点。
考虑树怎么做，把子树根设为不同颜色即可。
考虑仙人掌怎么做，可以建立圆方树，在圆点处需要处理两条边的连接，在方点处需要把儿子连成一条链，不难维护。
LOJ2398「JOISC 2017 Day 3」自然公园
Analysis
考虑链的做法，有一个随机做法，就是每次随机撒点。还有一个做法是每次找到一个点，然后二分求出它到 \(0\) 的路径上的最大值这样我们找到了一个新点，不断寻找即可还原所有链，复杂度是 \(\mathcal{O}(n\log n)\) 的。
考虑树的做法，可以沿用上面的做法还原一条链。
图不会。
Solution
图其实也可以沿用上面的做法，维护一个联通块，每次查找一个和原联通块相邻的点，相邻可以仍然采用二分求出一个点到联通块的瓶颈路。
找到一个相邻的点之后，我们需要找到和它相邻的所有边，考虑一条一条边还原，一个想法是仍然沿用上面的做法，每次找到和它相连的编号最小的点。但是有一个问题，就是我们需要对每个点都进行一次询问。解决的办法是我们给点重新编号，使得联通块内这些点联通，使用 bfs 序或者 dfs 序都可以。找到一条边之后，我们递归到每个联通块继续寻找，由于需要判断一个联通块有没有边，所以需要额外的一次询问，而这个询问不超过这条边的度数，也就是 \(7m\)。
需要注意的是我们仍然需要将整条链都还原，仍然可以沿用上面的做法。
代码鸽了。
Conclusion
我神秘般地卡在了对于一个图找相邻联通块的部分，其实使用我已经发现了的处理技巧是可以做出来的，但是还是没做出来/kk。难点的话我感觉搜出一棵生成树并沿用以前的方法找到一个相邻点还是比较巧妙的。
CF1299E So Mean
Analysis
考虑一些特殊的操作，发现 \(k=2\) 可以分奇数和偶数，\(k=3\) 多花几次也可以得到模三的等价类。因为 \(n\) 是偶数考虑了下 \(n/2\)，发现可以问出一对 \((x,y)\) 使得 \(y=n/2+x\)。然后就不会了。
Solution
考虑一些特殊的操作，\(k=n-1\) 可以找到 \(1\) 和 \(n\) 的位置，进一步，\(k=n-t\) 可以找到 \(t\) 和 \(n-t+1\)。于是我们得到了一个平方做法。
注意到我们没有充分利用模运算的性质，考虑问出每个数模 \(3,5,7,8\) 的具体值，对于 \(3\) 可以问出一个 \(1,2,3\) 然后选两个数问，对于 \(5\) 可以问出 \(1,2,3,4,5\)。但是 \(8\) 的操作次数就有点寄了，不过我们可以问出 \(2\) 的余数后然后问出 \(4\) 的余数，进而求出 \(8\) 的余数。使用 CRT 合并即可。
代码鸽了。
Conclusion
感觉要逐步有这样的思想：不断考察平凡的情况以得到新的构造方法和处理问题的工具，然后不断推广处理更为复杂的情况。在做的过程中要意识到当前工具的局限性，学会放弃，少走一些弯路，多尝试新的想法。
P6541 [WC2018]即时战略
Analysis
有一个显然的点分治询问做法，但是复杂度平方对数。
Solution
考虑一个动态点分树做法。每次把一个点接到它的原有的父亲上面，如果插入它会使得整棵点分树不平衡，也就是一棵子树超过了它父亲的 \(\alpha\) 倍，那么就直接重构整个联通块，这样复杂度是正确的。
代码仍然鸽，如果出题人不缝那个链的部分分我可能就写了。
P6908 [ICPC2015 WF]Evolution in Parallel
Analysis
找到一个偏序集的二链覆盖。有经典的 DP 技术，但是需要处理 \(w(i,j)\) 表示 \(i\) 是否被 \(j\) 偏序，这个至少是三方的。
Solution
考虑贪心做这个决策过程，但是会存在一些问题，比如一个元素可以加入两条链中的任意一个，我们没法快速决策，此时可以利用一个贪心技术：延迟决策。我们把当前元素压入一条缓存链，等到需要考虑的时候再解决它。如果当前加入一条元素，它能选择的链是唯一的，那么我们把它加入这条链，并把缓存区的元素加入另一条链。如果可以选择两个，那么如果能将它插入缓存区末尾就插进去，否则它与缓存链必然存在于两条不同的链中，随便放都行。
这样我们就解决了决策的问题。
Conclusion
记住这个延迟决策的技巧，贪心可以强行决策然后反悔，这是类似费用流的思路，也可以暂时不决策，等到限制越来越强的时候再做出选择。
CF1764E Doremy's Number Line
Analysis
首先可以发现 \(p_1\) 一定最后，然后对于任意时刻，可以染色的部分都是一个前缀，我们需要最大化这个前缀。换句话说，问题为：重新排列 \(a,b\) 并考虑一个变量 \(t\)，每次执行 \(t\gets \max(a_i,\min(a_i,t)+b_i,t)\)，最大化最后 \(t\) 的值。
不满足邻项交换的性质，考虑将 \(a\) 排序，但是错了。
Solution
考虑将 \(a\) 排序的做法哪里错了：发现第一个元素是影响问题的，因为第一个元素的权值只能取 \(a_i\)。我们考虑枚举第一个元素是哪个然后执行贪心做法，这样做是平方的。
然后是比较智慧的地方，观察到每个点作为开头的情况，发现所有过程的后缀是差不多的。对于点 \(i\)，特殊的地方在于 \(i\) 作为开头之后，所有 \(x,a_x\leq a_i\) 的贡献只可能是 \(a_x+b_x\)，于是我们的转移就有了一个阶段，每次对于一个点作为开头的情况，只需要，考虑 \(a_x+b_x\) 的前缀 \(\max\)，加入贡献之后就可以以当前位置为起点往后面推。具体地，维护一个 \(ans\)，每次可以进行操作或者加入前缀最大值，扫一遍过去即可得到答案，复杂度线性。
zxy 的做法好像是倒着做，本质也差不多。
CF1764F Doremy's Experimental Tree
Analysis
我纯纯憨憨。
根据一道题的经验我们可以找到一个叶子，如果考虑剥叶子的话，我们无法判断剩下的点是否为叶子。考虑另外一个处理技巧，也就是维护一个联通块，但是判断一个点是否为另外一个点的邻边是困难的。
上面的过程完全可以花更少的时间，因为几乎没有前途。
考虑我们最开始确定一条边的方法，也就是考虑 \(f_{x,x}\) 与 \(f_{x,y}\) 的差，考虑一个对称的问题，也就是 \(f_{y,y}\) 与 \(f_{x,y}\) 的差，发现两个差加起来恰好是 \(n\) 倍的边权。推广到多个点仍然是成立的，所以我们掌握了询问一条路径的长度的方法。跑最小生成树就好了。
P8362 [SNOI2022] 数位
Analysis
憨憨了。只会数位 DP 构造 \(a\)，得到的做法大多是 \(\mathcal{O}(nk^t),t\geq 4\) 的。
Solution
数位 DP 显然是没有前途的，考虑对合法的 \(S\) 计数合法的 \(a\) 的方案数，相当于对所有合法的 \(S\) 计数：
\[\sum_{S}\sum_{i=0}^k(-1)^k\binom{k}{i}\binom{S-k(L-1)-(R-L+1)i}{k-1} \]需要满足组合数上标非负。考虑 DP 构造合法的 \(S\)，则我们相当于要求一个下降幂的和，转成普通幂然后用第一类斯特林数转化回去。普通幂的话只需要处理在状态里面加一个 \(x\)，用二项式定理展开即可。
Conclusion
比较有迷惑性，很容易想到数位构造 \(a\)，防止陷进去的方法就是在最开始就建立起对问题的整体感知，先理解问题的整体结构再寻找突破口。
P6630 [ZJOI2020] 传统艺能
Analysis
开始考虑设 \(f_{i,j}\) 表示 \(i\) 时刻 \(j\) 的概率，本来准备强行做转移，但是各个变量之间都不是独立的啊。
然后想到观察区间的影响，发现两个叠起来的区间相当于操作三个区间，然后想到倒流，这样标记就不是动态的了，但是一个区间下推的时候需要考虑它的子树里面有没有标记，有的话就要继续下推，不好处理。
Solution
期望线性性拆开贡献，所以可以考虑从单个元素寻找突破口。观察可以发现一个元素被打上标记有两种情况：一种是它自己在区间定位中，一种是它的兄弟在区间定位中，而它的祖先中存在标记，进一步可以发现对于单个点我们只需要关注它祖先中是否有标记和它是否有标记即可，于是可以设 \(f_i\) 表示 \(i\) 时刻它有，\(g_i\) 表示祖先有，\(h_i\) 表示都有的方案，不难使用矩阵转移。
Conclusion
老老实实做观察吧。
P6864 [RC-03] 记忆
Analysis
考虑没有撤销怎么做，可以建立树并维护 \(\dbinom{deg_i}{2}\) 的和。考虑维护的过程，要么将答案加上 \(deg_u\)，要么新建结点 \(u\) 并重置 \(deg_u\)。
考虑怎么加速操作，发现答案的维护可以利用矩阵刻画，则在时间轴上维护矩阵乘积即可，复杂度一个 \(\log\)。
Solution
简化问题并引入合适的工具刻画。
[AGC012C] Tautonym Puzzle
Solution
考虑一些特殊的序列，首先是全 \(a\) 序列，这样可以构造出 \(2^{|s|}-1\)。
考虑另一种情况，就是我们保证一个字符最多出现 \(2\) 次，那么先把每个字符都放一次，在后面从小到大添加数，发现如果放前面方案数 \(+1\)，放后面方案数 \(\times 2\)，做二进制拆分即可。
Conclusion
这种普通的构造复杂模型的问题都有共同的方法：考虑特殊的情况，通过加强题目限制来简化问题，引出合理的构造。
标签：记录,一个,可以,Solution,Analysis,做法,考虑 From： https://www.cnblogs.com/yllcm/p/17162762.html