CF1310C
CF616F
CF1065G
CF1536F. Omkar and Akmar *2600
题意
Alice 和 Bob 在一个 \(n\) 个格子的环上玩游戏，环上的格子编号为 \(1\sim n\)。
每一轮中，玩家可选择一个空格子填入字母 A 或 B，同时要求不能存在两个相邻的格子内的字母相同。若没有合法操作，则游戏结束，当前玩家失败。
假设 Alice 和 Bob 每局游戏两个人都按最优策略行动，问有多少种可能的不同游戏。两种游戏不同，当且仅当回合数不同，或者对于某个回合，放置的字母或单元格编号不同。答案对 \(10^9+7\) 取模。
\(n\leq 10^6\)。
题解
核心思想：枚举最后局面，计算每个最后局面对答案的贡献。
首先，两个玩家肯定是能操作就操作，因此最后局面肯定不能继续操作。
那么最后局面一定是一个 ABAB 交替的环上序列，中间穿插若干不相邻的空位。
因为这是环上 ABAB 交替的序列，所以最后填上数的位置个数必定为偶数，因此后手必胜。
当最后局面确定时，两个玩家可以随便操作。因为这相当于有若干个石子，每次操作取走恰好一个石子的简单博弈问题。
假设我们最后确定的局面有 \(i\) 个空格，那么这个局面的操作方案书就是 \((n-i)!\)。
我们枚举空格个数，然后计算满足条件的局面个数。再乘上操作方案数。
当空格个数确定时，由于要求空格不能相邻，因此考虑插板，为了方便插板，我们假设环上一开始只有 ABAB...，然后把环从第一次操作的地方断开，对于断开的链，每个位置的后面可以选择放不放空格。
因此，空格个数为 \(i\) 时，总方案数为 \(2\times n\times \binom{n-i}{i}\times (n-i-1)!\)。
乘 \(2\) 是因为 AB 可以互换，乘 \(n\) 是因为这是有标号环，需要枚举断开位置的标号。
空格个数一定与 \(n\) 奇偶相同，最后答案为 \(\sum\limits_{i=n\bmod 2}^{\lfloor \frac{n}{2}\rfloor} \left(2\times n\times \binom{n-i}{i}\times (n-i-1)!\right)\)。
提交记录
2025/9/7 NOIP 模拟赛 T4 *????
题意
求 \(n\) 个点的有标号无根树的直径之和。
\(n\leq 500\)。
题解
核心思想：以所有直径的交点/边为中心。
令 \(f_{i,j}\) 表示 \(i\) 个点编号为 \(1\sim i\)，深度不超过 \(j\) 的有标号有根树的数量。
令 \(g_{i,j}\) 表示 \(i\) 个点编号为 \(1\sim i\)，深度不超过 \(j\) 的有标号叶向森林（即 \(f\) 去掉根）数量。
如果所有直径交于一边，即直径长度为 \(2k+1\)，那么枚举两边点的个数 \(x,n-x\)，答案为 \(\sum\limits_{x=1}^{n} (f_{x,k}-f_{x,k-1})\times (f_{n-x,k}-f_{n-x,k-1})\times \binom{n}{x}\div 2\)，除以 \(2\) 的原因是交边两侧是无序的。
但是模数不质，且常数不允许我们再存一个 \(2\) 因子，我们不能除以二，考虑强制让 \(1\) 在左侧，即 \(\sum\limits_{x=1}^{n} (f_{x,k}-f_{x,k-1})\times (f_{n-x,k}-f_{n-x,k-1})\times \binom{n-1}{x-1}\)。
如果所有直径交于一点，即直径长度为 \(2k\)，那么这个点所有子树至少有 \(2\) 个深度等于 \(k\)，容斥，答案为 \(n\times \left( g_{n-1,k}-g_{n-1,k-1}-\sum\limits_{x=1}^{n-1} (f_{x,k}-f_{x,k-1})\times g_{n-1-x,k-1}\times \binom{n-1}{x} \right)\)。
考虑如何求 \(f\)，显然有 \(f_{i,j}=g_{i-1,j-1}\times i\)。
考虑如何求 \(g\)，有 \(g_{i,j}=\sum\limits_{k=1}^{i} g_{i-k,j}\times f_{k,j}\times \binom{i-1}{k-1}\)。
解释一下 \(g\) 的转移，有一个错误的想法是 \(g_{i,j}=\sum\limits_{k=1}^{i} g_{i-k,j}\times f_{k,j}\times \color{red}\binom{i}{k}\)，但是这样算，子树是有序的，因此会算重。
考虑把子树按照一定顺序排序，并有序的加入这些子树，由于我们在实时分配编号，因此考虑按子树内的最小值降序排序，然后每次强制让 \(1\) 出现在新的子树里，即 \(g_{i,j}=\sum\limits_{k=1}^{i} g_{i-k,j}\times f_{k,j}\times \binom{i-1}{k-1}\)。
初始时 \(f_{0,i}=g_{0,i}=1\)。
提交记录
CF1038F. Wrap Around *2900
题意
给定一个字符串 \(s\)，字符集为 \(\{0,1\}\)。
求有多少长度为 \(n\) 的字符串 \(t\)，满足以 \(t\) 为循环节的无限循环字符串包含 \(s\)。
\(1\le|s|\le n\le 40\)。
题解
\(s\) 在无限循环的 \(t\) 中出现，等价于 \(s\) 在 \(t^2\) 中出现。
考虑建立 KMP 自动机，在自动机上 DP。
但是直接对 \(t^2\) 的结构做 DP 会导致有后效性。
考虑 DP 为什么无法处理 \(t^2\) 的情况，因为正常 KMP 自动机上 DP 只能处理往后加入一个字符，而维护 \(t^2\) 要求我们往中间插入字符。
考虑把 DP 改成只往后加字符的情况。只往后加字符，一种想法是假设 \(t\) 在 KMP 自动机的结束状态确定，然后往后加第二个 \(t\)。
时间充裕，因此可以直接枚举 \(t\) 在自动机上最后的节点 \(p\)，令 \(f_{i,j,k}\) 表示 \(|t|=i\)，\(t\) 在自动机上走到了 \(j\)，\(t^2\) 在自动机上走到了 \(k\)，初值令 \(f_{0,0,p}=1\) 即可。
时间复杂度 \(O(n^4)\)。
提交记录
CF587F. Duff is Mad *3000
题意
给定 \(n\) 个字符串 \(s_1…s_n\)。定义 \(f_y (x)\) 表示 \(s_x\) 在 \(s_y\) 中出现的次数。
\(q\) 次询问，每次给定 \(l,r,k\)，求 \(\sum\limits_{i=l}^{r} f_k (i)\)。
\(n, q, \sum_{i=1}^n |s_i| \leq 10^5\)。
题解
*所有复杂度认为 \(n,q,|s_i|\) 同阶。
搬到 ACAM 上，发现问题可以转化为如下形式：
- 给定 \(n\) 个点集，保证点集大小之和不超过 \(10^5\)，每次询问给定 \(l,r,k\)，求编号在 \([l,r]\) 的点中，子树内含有第 \(k\) 个点集中点的个数之和。
直接做很难做，考虑反过来，变成把编号在 \([l,r]\) 的点的子树加一，然后求第 \(k\) 个点集的权值和。
然后如果点集大小为 \(1\)，就可以直接做了。
保证点集大小之和不超过 \(10^5\)，可以根号分治，点集大小不超过 \(B\) 的直接暴力，复杂度 \(O(nB\log n)\)，点集大小大于 \(B\) 的点集不超过 \(\frac{n}{B}\) 个，提前预处理每个点进行子树加对这些点集的贡献，然后维护 \(O(\frac{n}{B})\) 个 BIT 一起扫描线，复杂度 \(O(\frac{n^2}{B})\)。
令 \(nB\log n=\frac{n^2}{B}\)，即 \(B=\sqrt{\frac{n}{\log n}}\)，此时复杂度为 \(O(n\sqrt{n \log n})\)。
但是由于 \(O(\frac{n^2}{B})\) 的空间复杂度无法接受，因此最后决定令 \(B=10^{2.5}=316\)，此时当 \(n,q,|s|=100000\) 时，时间复杂度为 \(O(n\sqrt{n}\log n)\)。
提交记录
CF1400F. x-prime Substrings *2800
题意
给定一个整数 \(x\) 和一个只包含数字 \(1\) 到 \(9\) 的字符串 \(s\)。设 \(f(l, r)\) 表示子串 \(s[l..r]\) 的数字之和。
我们称子串 \(s[l_1..r_1]\) 为 \(x\)-prime，当且仅当：
- \(f(l_1, r_1) = x\)；
- 不存在 \(l_2, r_2\) 满足：
- \(l_1 \le l_2 \le r_2 \le r_1\)；
- \(f(l_2, r_2) \neq x\)；
- \(x\) 能被 \(f(l_2, r_2)\) 整除。
你可以从字符串中删除一些字符。每删除一个字符，字符串会被分成两部分并直接拼接，顺序不变。
请问，最少需要删除多少个字符，才能使字符串中不存在 \(x\)-prime 子串？如果原字符串中本就不存在 \(x\)-prime 子串，则输出 \(0\)。
\(1\leq |s|\leq 1000\)，\(1\leq x\leq 20\)。
题解
考虑要求一些子串不能出现，即多模匹配，搬到 ACAM 上考虑。
\(x\leq 20\)，发现 \(x\)-prime 字符串总数不会太多，最多的时候是 \(x=19\)，此时所有 \(x\)-prime 字符串建出的 ACAM 大小为 \(4852\)。
因此暴力建出 ACAM 后跑 DP 即可，\(dp_{i,j}\) 表示前 \(i\) 个字符走到 ACAM 的 \(j\) 号点最小要删去几个字符，转移显然。
提交记录
CF2045E. Narrower Passageway *2700
题意
有一个 \(2\) 行 \(N\) 列的网格。我们用 \((r, c)\) 表示网格中第 \(r\) 行第 \(c\) 列的格子。每天会安排一个力量值为 \(P_{r, c}\) 的士兵驻守在 \((r, c)\) 位置上。
每列都有 \(50\%\) 的概率被雾气笼罩。定义连通区域 \([u, v]\)（\(u \leq v\)）为从第 \(u\) 列到第 \(v\) 列连续且无雾的列。
连通区域 \([u, v]\) 的力量可以这样计算。设 \(m_1\) 和 \(m_2\) 分别为该区域内第一行和第二行士兵力量的最大值。具体来说，对于 \(r \in \{1, 2\}\)，有 \(m_r = \max (P_{r, u}, P_{r, u + 1}, \dots, P_{r, v})\)。如果 \(m_1 = m_2\)，则该区域的力量是 \(0\)；否则，力量为 \(\min (m_1, m_2)\)。
一个工作日的总力量定义为所有连通区域力量的总和。请计算在任意一天部署的期望总力量。
\(1\leq N\leq 10^5\)。
题解
硬讨论也能做，但是有更简单的做法。
变换一下贡献计算形式，对于一个区间，令其贡献为 \(m1+m2-m1[m1=\max(m1,m2)]-m2[m2=\max(m1,m2)]\)。
所有区间 \(m1\)、\(m2\) 的和都是好求的，\(m1[m1=\max(m1,m2)]\)、\(m2[m2=\max(m1,m2)]\) 只需要在单调栈算区间时，规定当前数不小于该区间所对另一行的所有数即可。
提交记录
NOIP 模拟 T3 *????
题意
比较难以描述……
题解
建立笛卡尔树，问题转化为选 \(k\) 个叶子并删除其到根链，最大化删除点权值和。
树形DP，令 \(f_{i,j}\) 表示子树 \(i\) 内选择 \(j\) 个叶子的答案。
有 \(f_{u,j}=w_u+\max\limits_{0\leq x\leq j} \{f_{ls_u}{x}+f_{rs_u}{j-x}\}\)。
不好继续优化，考虑维护 \(f\) 的差分数组，那么贪心地，\(f_u\) 的差分数组就是把 \(f_{ls_u},f_{rs_u}\) 的差分数组从大到小归并，再把第一项加上 \(w_u\)。
贪心的正确性在于，总和一定，要让 \(f\) 最优肯定先选择增量大的叶子。
因此每个点维护一个 set 表示这个点 \(f\) 的差分数组，然后启发式合并即可。
提交记录
CF150E. Freezing with Style *3000
题意
给定一颗带边权的树，求一条边数在 \([L,R]\) 之间的路径，并使得路径上边权的中位数最大。输出一条可行路径的两个端点。
\(n\leq 10^5\)。
题解
二分答案 \(Mid\)，将 \(\geq Mid\) 的边都赋值为 \(1\)，其余边赋值为 \(-1\)，点分治求最大权值和路径检查其是否 \(\geq 0\) 即可。
点分治中需要使用单调队列代替线段树，并按照子树大小或深度从小到大遍历保证单调队列复杂度，还要进行一些必要的剪枝（找到一条 \(\geq 0\) 的路径后立即退出）。
提交记录
AT_arc072_d [ARC072F] Dam 紫
题意
你负责管理一个最多能储存 \(L\) 升水的水库。一开始，水库是空的。接下来 \(n\) 天，第 \(i\) 天早上，有 \(v\) 升 \(t_i\) ℃ 的水会流进来；每天晚上，你可以决定要放多少水，但你必须保证第二天水不会溢出。水不会蒸发，温度也和流进水之外的因素无关。\(v_1\) 升 \(t_1\) ℃ 的水与 \(v_2\) 升 \(t_2\) ℃ 的水混合后的温度为 \(\dfrac {t_1v_1+t_2v_2}{v_1+v_2}\)。对于第 \(i (i \in [1,n] \cap \mathbb N)\) 天，你需要求出最后水库是满的的情况下能达到的最高水温。不同日期的答案相互独立。
\(1 \le n \le 5 \times 10^5\)。
题解
考虑一个贪心，如果 \(i+1\) 时刻加入水的水温比 \(i\) 时刻冷，那么 \(i\) 时刻一定选择不放水，以提高 \(i+1\) 时刻的水温。即使要放水，也是先加入 \(i+1\) 时刻的水，再一起放，这样剩余水温一定不会变差。
那么，我们把所有相邻温度递减的操作合并成一个操作，重复这个过程直到操作满足温度递增。
之后，我们肯定是能放水就放水，但是要保证询问时水池内水的体积等于 \(L\)。手动模拟一下，发现被放掉的水不可能在流回来，流回来也不会更优。因此询问可以等价成：指定体积的滑动窗口，求体积乘以温度的和，单调队列即可。
提交记录
P11283 「GFOI Round 2」Turtle and Nediam 紫
题意
对一个元素互不相同的长度 \(\ge 3\) 的正整数序列 \(a\)，定义 \(a\) 的“肿胃数（nediam）”\(f(a)\) 为：
- 当 \(|a| = 3\) 时，\(f(a)\) 为 \(a\) 的中位数；
- 当 \(|a| > 3\) 时，取 \(a\) 的任意一个长度为 \(3\) 的子段 \([a_i, a_{i + 1}, a_{i + 2}]\)，记这个子段的中位数为 \(x\)，\(a\) 删掉 \(x\) 后的序列为 \(b\)，\(f(a)\) 为所有 \(b\) 中 \(f(b)\) 的最大值。
乌龟给你一个 \(1 \sim n\) 的排列 \(p_1, p_2, \ldots, p_n\) 和 \(m\) 次询问，每次询问给定 \(l, r\)，你需要求出 \([p_l, p_{l + 1}, \ldots, p_r]\) 的“肿胃数（nediam）”，即 \(f([p_l, p_{l + 1}, \ldots, p_r])\)。
\(n\leq 10^6\)，\(m\leq 5\times 10^6\)。
题解
第一反应是找次大值，但这是错的。考虑寻找最大值可能成为答案的区间，因为次大值本质上是原序列某个子区间的最大值。
先找出全局最大值 \(a_x=mx\)，显然 \(mx\) 不能成为答案，也不会被删除。并且 \(mx\) 会把数列分为两部分。
称 \([1,x)\) 为左侧序列，\((x,n]\) 为右侧序列。
只对左侧序列讨论，右侧序列与左侧序列类似。
考虑左侧序列的最大值 \(a_i\) 能否成为答案，为了验证这件事，首先要观察一些删除数的性质：
- 对于序列的子串 \(a_{l\sim r}\)，满足 \(a_p(l\leq p\leq r)\) 是最小值且 \(a_q(l\leq q\leq r)\) 是最大值，那么一定可以把该子序列删到只剩 \(a_p\) 和 \(a_q\)。证明显然。
- 对于序列的子串 \(a_{l\sim r}\)，满足 \(a_p(l\leq p\leq r)\) 是最小值且 \(a_q(l\leq q\leq r)\) 是最大值，如果最后只能保留两个数字，那么这两个数字一定是 \(a_p\) 和 \(a_q\)。证明显然。
为了方便讨论，我们记 \(a_y\) 为 \([1,x)\) 的最小值，\(a_z\) 为 \((x,n]\) 的最小值。
根据性质，为了保留 \(a_i\)，我们可以且必须先把序列删到只剩下 \(a_{i/y},a_{y/i},(a_r),a_x,a_z\)，因为 \([y,x]\) 最多保留两个，\([x,n]\) 最多保留两个。注意 \(i,y\) 顺序不确定（\(a_r\) 的定义将在 \(y<i\) 的讨论中解释）。
如果 \(y<i\)，即 \(a_y,a_i,a_r,a_x,a_z\)，\(a_r\) 表示 \([i,x]\) 的最小值，那么如果 \(a_z>a_r\)，\(a_i\) 可以成为答案，操作步骤为 \(y,i,r,x,z\to y,i,r,x\to i,r,x 或 y,i,x\)（这里用下标代替值简写）；否则为了保留 \(a_i\)， \(a_r\) 一定会被删除，\(a_r\) 被删除后无论下一步如何操作都会删掉 \(a_i\)。
如果 \(y>i\)，即 \(a_i,a_y,a_x,a_z\)，删掉 \(a_y,a_x,a_z\) 的中位数即可。
因此 \(a_i\) 能成为答案的充要条件是 \(y>i\)。
我们发现 \(y\) 把左侧区间又分为了两部分，我们记 \([1,y)\) 的最大值为 \(a_p\)，\((y,x)\) 的最大值为 \(a_q\)。
那么 \(a_p\) 一定可以作为答案，当 \(a_q<a_z\) 时 \(a_q\) 也可以成为答案。
特判 \(a_y,a_z\)，这两个数的较大值也能成为答案。
右侧是一样的，需要实现的功能是静态 RMQ，使用 ST 表即可。
upd 我们发现刚刚推理有误。Hack 1 4 2 5 6 3，答案为 \(4\)。
原因是，\((y,x)\) 中可能存在一个数，满足这个数能作为答案但不是 \((x,y)\) 的最大值。
因此正确做法是找出最靠右的 \(w\)，满足 \(a_w<a_z\)，然后用 \((y,w)\) 的最大值更新答案。
搞一个单调栈单独维护这个东西。
提交记录
P6913 [ICPC 2015 WF] Tile Cutting 紫
题意
原题面不好描述，这里省掉一步转化。
令 \(f(x)=|\{(a,b,c,d)|a,b,c,d\in \N\land ad+bc=x\}|\)，有 \(n\) 次询问，每次给定 \(l,r\)，求 \(\max\limits_{i=l}^{r} f(i)\)。
题解
记 \(d(x)\) 表示 \(x\) 的因数个数。
考虑根号分治，设 \(B=\sqrt n\)。
记 \(t_{x,y}=\sum\limits_{i=1}^{n} [i\bmod x=y]\times d(i)\ \big(x,y\leq B\big)\)，\(g_{n,k}=\sum\limits_{x\geq 0} d(n-kx)\)。
\(g\) 需要重复利用以节省空间，注意特殊处理 \(n<B\) 的情况。
我们可以在 \(O(n\sqrt n)\) 的时间复杂度内求出所有 \(f\)，之后使用 ST 表查最值即可。
提交记录
CF2013F2 Game in Tree (Hard Version) *3500
题意
Alice 和 Bob 在一棵 \(n\) 个节点的树上玩游戏，规则如下：双方轮流移动，爱丽丝先手。每位玩家在自己的回合中，必须移动到一个未被访问过（无论自己或对手）的相邻节点上。第一个无法移动的玩家输掉游戏。
爱丽丝初始位于 \(1\) 号节点，你需要对于给定简单路径 \(u\to v\)（一定不穿过 \(1\)）上的每个节点 \(c\) 判断：若 Bob 初始位于 \(c\)，谁将获胜。
玩家的初始位置也被视为访问过的节点。
\(n\leq 2\times 10^5\)。
题解
令 \(dep_{u}\) 表示 \(u\) 的深度，\(dep_{1}=0\)，\(length_{u}\) 表示 \(u\) 去掉 \(1\to c\) 的点后子树下的最大深度。
对于点 \(c\)，Alice 获胜的充要条件是：
对于这种复杂的式子，考虑放缩，以缩小 \(u\) 的范围。
对于一个拐点 \(u\)，它能使 Alice 获胜的必要条件是 \(dep_{u}+length_{u}-1>dep_{c}-dep_{u}-1\)。
即 \(2\times dep_{u}+length_u>dep_c\)。
由于 \(dep_c\) 是常量，\(\sum length_{u}\leq n\)，考虑根号分治。
当 \(length_{u}<B\) 时，\(dep_u\) 的范围极差为 \(O(B)\) 级别。
当 \(length_u\geq B\) 时，\(u\) 的个数时 \(O(\frac{n}{B})\) 级别。
令 \(B=\sqrt n\) 即可，时间复杂度 \(O(n\sqrt n)\)。
对路径上每个点求 \(length\) 还是有一些细节的。
代码没调完QwQ。
——打造C++ IDE 续)
