壹

1110

Following Arrows

先分析 \(1\times m\) 的网格，考虑全是 \(L\) 的情况。

由于到某个点时，前面的点一定都指向它，所以每个格子本质独立。

考虑 \(n\times m\) 的网格，可变为存在唯一一条到终点的合法路径，某个格子的另种走法为走到之前的某个点。

构造类蛇形，发现最大步数满足题目条件，由于每个点的贡献独立（选反方向会有贡献），直接背包即可。小范围特判。

Heuristic Knapsack

对 \(w\) 排序，考虑 \(Alice\) 选的一定是 \(w\) 的一个前缀，再对 \(v\) 排序，不满足的贪心用未确定的数来满足限制。

Chain Prefix Rank (Hard Version)

广义串并联图。缩二度点能得到一条边。

每条边记录点数、方案数。

分别考虑二度点的合并和重边的合并。

Pointless Machine

先算 \(1 \~\ n\) 再算 \(n \~\ 1\) ，能得到每个点的度数。

然后剥叶子。

注意三叉比二叉更优。

PalindromePalindrome

Items

令 \(B=m/n\) ，将每个数减去 \(B\)，每个数的范围 \([-B,n-B]\) 。

最后可以倍增处理。

Little, Cyan, Fish!

二维分块，块内散块单算，直线与直线的贡献用 \(FFT\) 计算。

1111

Interesting Counting Problem

好题。

首先可以得到一个 \(O(n^2m)\) 的按 \(dfs\) 序的dp考虑每个点是否填 \(0\) ，如果不是 \(0\) ，那么可以直接用前缀和将卷积优化到 \(O(m)\) ，否则相当于对于当前位的每个儿子做一个类似的子问题，这样 dp 复杂度严格是 \(O(m\sum size)\) 的。

考虑优化，发现 \(dfs\) 序的dp是可以根据 \(dfs\) 划分成多个互不影响的部分的，根据这个性质可以用启发式合并继承重儿子的dp，时间复杂度 \(O(nmlogn)\) 。

20251112

Increment or XOR

拆分为按位考虑，异或是不进位加法， \(+1\) 会带来 \(+1\) 的贡献，设转态 \(f_{i,u,0/1,0/1}\) 表示考虑到前 \(i\) ，且进位不会超过 \(i\) ,起始状态为 \(s\) 或全 \(0\)，经过的操作集合的奇偶性为 \(u\) 终止状态为 \(t\) 或全 \(1\) 所需要的最小代价。

对于第 \(i-1\) 位到 \(i\) 位的转移，考虑 \(i-1\) 位进位和不进位的贡献，进位的贡献可以用最短路优化。

20251113

背包 pack

注意到数据范围 \(100\) 和 \(10^9\) ，鉴定为矩阵快速幂。

重载 \(+\) 和 \(\times\) ，通过转移式和矩阵乘法的转移，逆推运算，\(\times\) 表示的是将两个背包结合，\(+\) 表示的是不同方案取一个 \(max\) 。

满足矩阵快速幂的必要条件是 \(+\) 和 \(\times\) 都要满足结合律，且要满足 \(\times\) 对 \(+\) 的分配律。

20251114（贪心专练）

春节十二响

考虑两条链和菊花。

直接合并当前点的所有链，两两之间，按排名合并。

Skyscape

结论：一个排列 b 是好的，当且仅当 a 中的顺序对在 b 中也是顺序对。

必要性：a 中的顺序对不可能变成逆序对。

充分性：尝试证明 a 序列的中的逆序对可以在一次操作内变成顺序对。从 \(1\) 开始依次遍历每个逆序对，在满足上面结论时，分套一下是可以直接操作的。

Iris and Adjacent Products

翻转证明贪心决策的正确性。

从贪心决策得到满足条件关于个数的充要条件。

Doubles Horseback Wrestling

一个点能匹配就一定会被匹配。

考虑一种顺序去匹配点，先匹配难匹配的点。

匹配条件为 \(l_1+l_2\le s\le r_1+r_2\) ，对于枚举到目前的 \(l_1,r_1\) ，有如下条件：

\[l_2\le s-l_1\\ s-r_1\le r_2 \]

发现当 \(l_1\) 从大到小时，\(l_2\) 一定满足一个增集关系，那么每次选 \(r\) 最劣的就行了，用 \(set\) 维护可选区间。

20251117

比赛

首先可以注意到分 \(k\) 组一定是按 \(mod\ \ k\) 不同分的，否则包含一定可以交换。

变成只有一组的问题。dp转化一下，得到一个很凸包的条件，线段树预处理。

20251124

度与好

区间加1，全局取min，全局求min，线段树合并。

两个有序操作，不是很好标记永久化，考虑直接打标记，当合并的两个节点中，有一个节点没有儿子时，这个子树内的值都是相同的，对于另一个节点，贡献就变成了区间加，直接加到标记上就行了。

Relay Jump

对于所有可以到的转态，用一种相同的势能去定义。

感受一下，当前操作点应该是一个系数，其他点是一个系数，直接考虑一次转移，把系数解出来。

最终发现势能为:

\[(\sum_{j\neq i}P_j)-P_i \]

The Echoes of Chronos

注意到在一个环上，一定是一半走一个方向，另一半走另一个方向，那么一种划分的答案就是环长减去中间换方向的那段长，最小的划分代价就是环长减去最长段长度。

回滚莫队。

Leo

首先，需要去掉前面的一串空串，用 \(or\) 。

\[a_i=a_i | a_{i+1} | a_{i+1} \]

若是 \(a_i=*\) 则 \(a_i=a_{i+1}\) ，否则不变。

现在前面一段相同的都是第一个出现的颜色。记当前串为 \(S\) 。

此时再进行前缀 \(and\) ，除第一段外，其余都变成了 \(*\) 。

此时再与 \(S\) 差位 \(or\) 可以得到除第一段后一个与 \(S\) 不同，其余都相同的串，记作 \(T\)。

最后在将 \(S、T\) 从左到右从上到下异或，就得到最后出现的颜色了。

20251127

[CERC 2024] Anthem

分析在 \(T\) 上走的性质，两侧是回文串，中间是双回文串。

咕咕嘎嘎。

注意到，以 \(i\) 为右端点的回文串可以由 \(i-1\) 为右端点的回文串 \(check\) 一下再加上长度为一的回文串得来。

Fliper

先用隔板当点，连边，考虑环。

在把环的编号当点，原来的点当边，每个环连出去的边意味着这个环上的点，两个环连边，表示两个环共用一个点。

对于只在一个环中出现的点，建一个虚点与环连边。

问题变成了边染色。

要求环长 \(\%8==0\) ，跑两次欧拉回路。

[EC Final 2019] Permutation

根据笛卡尔树的结构划分子问题。