[ICPC2014 WF] Surveillance

断环，然后复制一倍转化为序列问题，可以倍增。

https://www.luogu.com.cn/record/60927918

[CERC2013] Captain Obvious and the Rabbit-Man

构造多项式 \(A(x)=\prod(x-F_i)\)，考虑等式 \(\sum a_iF_iA(F_i)=0\) 的左边，展开它就做完了。

https://www.luogu.com.cn/record/60939504

[CERC2014] Virus synthesis

当 \(S\) 有偶回文子串时，可以先构造它的一半然后用操作 2 补全另一半再用操作 1 补全剩下的。于是在回文自动机上转移 dp 即可。

https://www.luogu.com.cn/record/60953431

[NEERC2015] Landscape Improved

枚举最高点在哪里，然后二分它可以搭多高，判断时可以用倍增求出他左右两边第一个不需要垫的位置。

https://www.luogu.com.cn/record/60979650

[CERC2015] Greenhouse Growth

发现一段连续的相等的 \(h\) 会一起变，可以考虑维护这些连续段。对于两个相邻的连续段，可以快速地计算出它们合并的时间。于是按照时间顺序依次合并即可，每次合并两段时注意重新计算它与相邻段的合并时间。

https://www.luogu.com.cn/record/60988923

[ICPC2015 WF]Qanat

相邻两个排土口中点左边的土都从左出，右边同理。列出式子来后拉格朗日乘子就好了。

https://www.luogu.com.cn/record/60979549

[ICPC2016 WF] Longest Rivers

计算一个节点时，肯定将它到根的链上的边都给为它，计它此时的长度为 \(l\)。对于不在这条链上的节点，贪心地考虑它到它父亲的这条边：如果存在一个儿子流向它的长度已经 \(>l\)，就给这个儿子；否则给最短的一个。

考虑计算 \(f_u\) 表示分配完 \(u\) 子树内以及到父亲的边时 \(u\) 子树内的最大长度的最小值。将 \(f_u>l\) 的点都染成黑色，那么该点答案就为黑点连通块的不在那条链上的叶子个数 +1。

于是按照每个叶子的 \(l\) 降序排序，顺次将一些点染黑，用树状数组维护下叶子个数即可。

https://www.luogu.com.cn/record/61048238

[CERC2017] Embedding Enumeration

计 \(f_u\) 表示将 \(u\) 的子树铺在网格中且 \(u\) 在左上角的方案数，转移的话想清楚就不难了。

https://www.luogu.com.cn/record/61053190

[NEERC2015] Binary vs Decimal

发现如果一个数合法，那么它的后缀也合法，于是可以每次往前加一个 0/1 进行 bfs。答案可以有 160+ 位，需要高精度。

https://www.luogu.com.cn/record/61057069

CF1599F Mars

可以通过区间的和、长度、公差来确定整个等差数列。比较两个集合大小是否相等可以比较它们 \(k\) 次方和，而一个等差数列的 \(k\) 次方和容易 \(O(k)\) 计算。

https://codeforces.com/contest/1599/submission/133306282

CF1599A Weights

对于一个升序数组，如果将它左右交替放那么每放一个天平都会切换。于是设 \(S\) 有 \(k\) 个切换的位置，那么第一个就放第 \(k+1\) 大的砝码，接下来每切换一次就放一个更大的在另一边。不切换时就将较小的 \(n-k\) 个砝码从大到小，第一个放在第 \(S\) 的第一个字符的另一边，每放一个就换一边。容易证明这样是合法的。

https://codeforces.com/contest/1599/submission/133307766

【集训队作业2018】购物

对每个特殊区域，计算从左/上进和右/下出的方案数，相邻两个区域和自己区域内部的转移都可以 FFT，而起点和终点的方案是经典组合数求和问题。

https://uoj.ac/submission/513360