好题记录

· · 个人记录

P10363 [PA 2024] Monety (3.5)

考虑判断什么状态是公平的. 先给出结论：

对于一堆硬币 s_1,s_2,\cdots,s_m，设 s_1=s_2=\cdots=s_t,s_t\neq s_{t+1}，给硬币 i\in[1,t] 赋上 1 的权值，给 i\in(t,m] 赋上 2^{t-i} 的权值，那么当且仅当红硬币权值等于蓝硬币权值时，该状态是公平的. 进一步的，若红硬币权值大于蓝硬币的权值，则红方必胜，反之亦然.

考虑证明这个结论.

当红方权值大于蓝方权值时：

现在红方希望保持自己的权值更大. 设权值最小的硬币的权值为 w，那么红方权值减蓝方权值至少为 w. 找到硬币权值为 w 的硬币前面第一个红硬币，取走该硬币，那么红方权值减蓝方权值恰好减少 w，此时红方权值不小于蓝方权值，等蓝方操作完后，红方权值必然大于蓝方权值.

当双方权值相等时：

设权值最小的硬币的权值为 w，那么这样的硬币至少有两个，否则双方权值无法相等. 首先先手操作后至少得使先手权值减后手权值减少 w，并且无论先手如何操作，后手都可以使后手权值减先手权值只减少 w，因此在最优策略下，双方操作完后双方权值依然相等.

接下来考虑计数. 为方便将权值 \times 2^{m-1} 变成整数.

考虑数位 dp. 依次考虑权值为 2^0,2^1,\cdots,2^{m-1} 的硬币. 从小到大枚举 i，加入最小权值为 2^i 的硬币堆，并且在加入时就确定他开头是形如 RR\cdots RB 还是 BB\cdots BR，并把这部分的权值记下来，然后再确定权为 2^i 的硬币的颜色.

设 f_{i,j,k,l} 表示确定了权值大小 <2^i 的硬币，已加入的硬币堆数为 j，权值 \geq 2^{m-2} 的硬币权值和为 k\cdot 2^{m-2}，其余硬币的权值和为 l\cdot 2^i，的方案数. 转移直接枚举权值为 2^i 的红硬币个数即可. 最后需要加入所有硬币颜色相同的硬币堆.

状态数 O(m\times n\times mn\times n)，转移 O(n)，复杂度 O(n^4m^2).

P9109 [PA 2020] Tekstówka (3)

P4528 [CTSC2008] 图腾 (1)

题意：求 1324-1243-1432.

显然每一个是不能分别算的，不然他出成这样干啥

1324-1243-1432

=(1x2x-1423)-(14xx-1423)-(12xx-1234)

=1x2x-14xx-12xx+1234

=1x2x-1xxx+13xx+1234

这几步看上去很对脑电波，但实际上是有办法无脑做的：只需要把能求出来的东西列出来，跑个高斯消元用能求的东西线性表示出需要求的东西，能求的和要求的都可以表示成一个长为 4! 的向量.

首先 1xxx 和 1234 是随便做的，考虑 1x2x 怎么做，13xx 显然就是 1x2x 按 y=x 对称过来.

枚举 2 的位置，最后一个 x 的方案数是容易求的，考虑左边怎么算. 只需要求出满足 p_x<p_y 的方案数减去 123 和 231 的方案数即可. 进一步地，231 可以拆成 xx1-321.

复杂度 O(n\log n).

P8520 [IOI 2021] 喷泉公园 (3)

将所有椅子黑白染色，白椅子只能往左右连，黑椅子只能往上下连.

从上往下，从右往左构造，保持 目前的图的连通性 和 将能连的边连完后的图的连通性 一致.

假设枚举到喷泉 (x,y).

容易证明这样连不会出现一个椅子连两条边的情况.

Qoj1425. Div (2)

将 \sum_i c_ix^{a_i} 乘上 1-x，那么问题变为有多少 x 满足其被 1-x^m 整除.

先将 a_i 模上 m，答案显然不会改变.

设 \sum_ic_ix^{a_i}=\sum_{i=0}^{m-1}b_ix^i.

固定 x，若 b_i\geq x，则可以令 b_{i+1}\leftarrow b_{i+1}+1,b_i\leftarrow b_i-x，若 b_i\leq -x 同理. 最后合法当且仅当 b_i 全为 -x+1 或全为 0 或全为 x-1.

可以发现，每做一次上述操作，\sum |b_i| 就会减 x-1，因此只需做 O(\dfrac nx) 次操作.

因此，对于每个 x，我们维护一个队列，存储 |b_i|\geq x 的 i，每次修改后若 |b_{i+1}|\geq x，则将 i+1 加入队列，不断修改直到队列为空. 用 map 存储 b，复杂度为 O(n\log^2n).

注意到若 b 有连续 \geq \log n 个 0，则可以缩成 =\log n 个 0，故 m 可以缩小到 O(n\log n) 级别（实际上还可以缩到 O(n) 级别）. 这样就不用 map 了. 复杂度 O(n\log n).

Qoj8717. 骰子 (2)

可以发现，这是一个分组的背包问题，背包大小为 m.

我们把一组当做一个多项式 A_i(x)，那么每次询问 [l,r]，就等价于设 F(x)=\prod_{i=l}^rA_i(x)，求 \sum_{i=0}^mb_i[x^i]F(x).

容易想到设前缀积 P_i(x)=\prod_{j=1}^iA_j(x)，那么 F(x)=P_r(x)P_{l-1}^{-1}(x)，这样单次询问复杂度即可降到 O(m^2).

继续考虑优化计算 F(x)，但是无论怎样都逃不了卷积，复杂度顶多降到 O(m\log m).

我们把目光放眼整个要求的式子 \sum_{i=0}^mb_i[x^i]F(x). 我们发现每个询问中 b_i 是固定的，P_r(x) 和 P_{l-1}^{-1}(x) 是不固定的，而我们一直在想办法求 P_r(x) 与 P_{l-1}^{-1}(x) 的积而并没有用到每个询问中 b_i 固定的性质.

设 B(x)=\sum_{i=0}^mb_{n-i}x^i，则 \sum_{i=0}^mb_i[x^i]F(x)=[x^m]B(x)F(x)=[x^m]B(x)P_r(x)P_{l-1}^{-1}(x). 这是三个多项式乘起来求一项的形式. 若是两个多项式乘起来求一项，则可以 O(m) 求解，但若是三个多项式，则我们必须得先将其中两个完整地乘起来. 我们一开始的问题就在于一直在想如何求 P_r(x)P_{l-1}^{-1}(x)，但实际上我们可以先预处理出 B(x)P_r(x)，然后再 O(m) 合并.

总时间复杂度 O(nm^2+qm).

P6499 [COCI 2016/2017 #2] Burza (2.5)

P6700 [PA 2015 Final] Edycja (2)

Uoj889. 【UNR #8】二维抄袭检测 (3.5)

首先有个显然的 O(mq) 做法：枚举 k，直接维护能到的地方，用位运算优化.

考虑使用动态 dp 优化，但是询问的起点不一样，怎么办呢？

求出询问串与矩阵中能到达的最上方的位置的后缀的 lcp，那么在这段范围内，所走过的字符就是最上一行的字符.

使用猫树分治预处理矩阵乘积，并用 SA 预处理 lcp. 复杂度 O(L\log L+n^2m\log m+qn^2).

P9537 [YsOI2023] Qingshan and Daniel 2 (2.5)

设先手有 n 个数，后手有 m 个数.

当 n-2\geq m 时先手必胜，因为先手可以造出至少 n-1 个不相同的数. 同理当 n+1\leq m 时后手必胜.

我们先假设 n>m 时先手必胜，然后尝试找到一些反例.

可以证明反例有且仅有以下三种情况：

第一种显然是后手胜的充分条件，因为第一步就不合法.

考虑第二种，第三种是类似的.

首先证明 2 是后手胜的充分条件.

由于后手不可能造出 \geq td 的数，而先手 <td 的数只有 n-2 个，且后手能造出的数有 n-1 个，故后手总是能操作. 证毕.

考虑证明当 n=m+1 且不满足 1 时，2 是后手胜的必要条件.

首先当后手的最大值 \geq (t+1)d 时，先手显然必胜.

设 d 为先后手所有数的 \gcd，那么我们现在需要证明先手存在 td 为后手胜的必要条件.

首先有一个观察，当先手的数不构成等差数列时，先手至少能造出 n 个数. 因此若先手败，则那个时刻先手的数一定构成等差数列，假设公差为 g，则后手的数一定为 g,2g,\cdots,(n-1)g.

考虑后手的最后一轮操作（由于我们已经把情况 1 判了，故这一轮操作是存在的），由于后手的数为 g,2g,\cdots,(n-1)g，因此后手只能给先手形如 yg 的数. 假设给完先手后先手的数为 x,x+g,x+2g,\cdots,(t+1)d-g,(t+1)d，那也就是说存在 z 满足 x+gz=tg，即 x=(t-z)g，即 \gcd(x,g)=d=g，因此先手存在数 (t+1)d-g=td. 证毕.

考虑计数. 第一种情况直接 bitset 即可，复杂度 O(\dfrac{a^2\ln a}{\omega}). 对于第二三种情况，可以发现我们需要求 O(a\ln a) 次形如 \sum_i\binom si\binom t{i+c} 的东西，这是范德蒙德卷积的形式，可以 O(1) 计算.

Uoj683. 【UR #22】月球车站 (3.5)

设 0 为反面，1 为正面.

考虑当 伏特希望最小化游戏步数，skip 蚤希望最大化游戏步数 时怎么做.

首先一个显然的观察是每个点的入度和出度均为 2（终点除外）.

我们倒着求解. 考虑维护已经确定答案的状态. 每次从这些状态里还未拓展的点中取步数最小的点进行拓展. 假设连向这个点的两个点为 x,y，其中 x,y 的第一个数分别为 0/1. 若 x 是第一次被访问到，那么可以确定 x 的答案；若 y 是第二次被访问到，那么可以确定 y 的答案.

注意到 x,y 仅有第 1 位不同，因此 x,y 要么同时被访问要么同时不被访问. 第一次访问时，仅有 x 需要拓展；第二次访问时，仅有 y 需要拓展. 也就是说每次都恰好拓展一个. 因此所有点可以连成一条链，所有点.

但是有一种特殊情况：当 x,y 第二次被访问到且 y 是全 1 时，此时无法拓展出去，那么未被拓展到的点就是 -1（因为伏特无法走到链上，skip 蚤必能不走到链上）.

实际上通过打表可以发现这种情况其实是不存在的，证明：

我们希望证明对于任意情况，伏特总有办法让游戏结束.

我们称 n 步为一轮. 对于每一轮，伏特先遇到 0 就翻，直到 skip 翻了 1 为止（显然 skip 必翻，否则就结束了），此后伏特不变，这样每一轮当前状态代表的二进制数都会减少. 到最后一定会变成全 0，伏特只需要全翻即可. 证毕.

我们给所有点按照最优情况下的步数重新标号，局面 i 的最优步数为 i. 以下均使用这个标号.

考虑原问题. 由之前的分析可以得出，对于 skip 蚤，他要么从 i 走到 i-1，要么走到 x\pod{x<i-1}；对于伏特，他要么从 i 走到 i-1，要么走到 y\pod{y>i}.

在之前的问题中，skip 蚤在最优情况下一定走到 i-1，我们猜测在该问题也是如此. 即，设 f_i 为局面 i 在最优策略下的期望步数，有 f_i<f_{i+1}.

证明：假设 x>y,f_x>f_y，对于局面 y，skip 蚤每次都选择走到 i-1，这样一定会走到 x，之后再沿用局面 x 的最优策略，这样可以得到 f'_y>f_x>f_y，与 f_y 最优矛盾.

这样我们就成功把转移里的 \max 去掉了. 设 g_i 为 i 到 0 的期望步数，直接解是 O(2^{3n}). 注意到 i 一定会经过 i-1，因此重新设 g_{i} 为 i 到 i-1 的期望步数，那么 g_i 只和 g_{i\sim 2^n-1} 有关，可以直接求出. 复杂度 O(2^n).

Uoj682. 【UR #22】月球铁轨 (2.5)

设 c_i=a_i\oplus b_i，设 F(x,T)=\max_{y\in T}(x\oplus y),G(x,T)=\min_{y\in T}(x\oplus y)，其中 T 是一个 \Bbb F_2 上的线性空间.

那么问题相当于求 F(s_r\oplus s_{l-1},T_{l,r}) 的第 k 小，其中 T_{l,r} 为 c_{l\sim r} 张成的线性空间，s 是 a 的前缀异或和.

考虑 a_i=0 怎么做，利用 前缀线性基 可以轻松解决.

考虑 c_i=0 怎么做，直接把 s 插入到 trie 上然后二分即可.

对一般情况，有结论：F(x\oplus y,T)=F(x,T)\oplus G(y,T). 可以从高位到低位考虑然后归纳证明.

因此 F(s_{l-1}\oplus s_r,T_{l,r})=F(s_{l-1},T_{l,r})\oplus G(s_r,T_{l,r}).

把所有区间按照 T_{l,r} 的秩分成 m 类分别做. 二分答案（逐位确定），把 G(s_r,T_{l,r}) 插入 trie，枚举 l，在 trie 上查询，时间复杂度 O(nm^3)，空间 O(nm). 也可以将 trie 可持久化，然后多树二分，时空复杂度均为 O(nm^2).

上述算法 1 的缺点在于，每次二分都要重新插入一遍 trie；对于算法 2，可以发现在 trie 上二分的过程中，只有当前位是有用的. 因此可以将两者结合，按位确定，每次只插入一位，查询完后立刻把上一位回收，时间 O(nm^2)，空间 O(nm).

Uoj705. 黄忠庆功宴 (3)

首先当 k\leq \sqrt p 时，直接预处理 b_{i}=a_{ik} 的前缀和即可 O(1) 查询，预处理复杂度 O(p\sqrt p).

当 k^{-1}\leq \sqrt p 时，可以将其划分为 k^{-1} 个长为 1 的等差数列，可以 O(\sqrt p) 查询.

考虑将两者结合，若 k=xy^{-1}，其中 1\leq |x|,y\leq \sqrt p，那么预处理出 b_{i}=a_{ix} 的前缀和，可以将其在 b 上划分为 y^{-1} 个长为 1 的等差数列，复杂度 O((p+q)\sqrt p).

考虑证明对于所有 k 均可以找到合法的 x,y. 设可重集 S=\{ky-x\mid 1\leq x,y\leq\sqrt p\}，根据抽屉原理 S 中必有两个重复元素 ky_0-x_0=ky_1-x_1，设 y_0>y_1，则 k=\dfrac{x_0-x_1}{y_0-y_1}.

未命名题目 1 (2)

分析 S 的形态. 首先考虑给定 S 如何找到 T，只需要不断找到 S+T 不能表示出的最小的数 v，将 v 加入 T 即可.

显然若 S 合法，则 T 一定合法.

显然 1 在 S 与 T 中恰好出现一次. 假设 1\in S，设 k=\text{mex}(S)>1，那么有结论：

  1. 若 \lfloor\dfrac ik\rfloor=\lfloor\dfrac jk\rfloor，则 i,j 在 S 中要么同时出现要么同时不出现.

如果能证第一个，那么容易证第二个.

找到最小的 i 满足 k\nmid i 且 i,i-1 恰有一个在 S 中出现. 设 w=k\lfloor\dfrac ik\rfloor，根据 T 的构造方法，显然 T 中 <w 的数都是 k 的倍数.

若 i\in S,i-1\not\in S，那么一旦 i-1 被 v+S 覆盖，则 i 也会被覆盖；若 i-1\in S,i\not\in S，那么由于覆盖 i 时 i-1 和 w+k 至少要被覆盖一个，而 i-1,w+k 已经被覆盖过，因此不合法.

我们用一个长为 nm 的 01 序列 a 表示 S.

考虑这样一个过程：设 k=\text{mex}(S)，当 k>1 时，把所有连续段大小除以 k；当 k=1 时， 设 w=\min(S\setminus\{0\})，把所有不是 w 的倍数的位置删掉. 若 S 合法，则最后 a 只会剩下一个 1.

这个过程可以和 (n,m) 二元组的变换建立双射. 具体地，我们可以选择 k，把 (n,m) 变成 (n/k,m) 或 (n,m/k)，两种变换需要交替进行.

设 f_i 为对 n 进行 i 次除以 k\pod{k>1} 的变换之后变为 1 的方案数，g_i 同理，先不考虑 k>1，由于 \sum x\leq 2\times 10^5，因此可以提取出相同的 x 使用快速幂做到 O(v\sqrt v)，最后二项式反演，可以使用 NTT 优化.

未命名题目 2 (2)

首先可以发现，一定先进行减操作再进行加操作，否则可以调整.

具体来说，若某次操作为 a_{l_1\sim r_1} 加 1，他后面的操作为 a_{l_2\sim r_2} 减 1，那么当 [l_1,r_1],[l_2,r_2] 无交时，可以直接交换；当其中一个包含另一个时，可以拆成两个小区间；否则可以直接把公共部分消掉.

因此，如果我们确定了每个位置被多少个加区间和减区间覆盖，就可以直接判断是否合法并求出代价.

从左往右考虑每个位置被覆盖的次数，设 i-1 被 x 个减区间覆盖，y 个加区间覆盖，那么我们可以选择部分区间延伸到 i.

直接 dp 就可以做到 O(poly(nv)). 考虑哪些 (x,y) 是有用的，有结论：存在 s,x,y,z，满足所有有用的 (x,y) 都可以表示为 (x+c,y+c)\pod{0\leq c\leq z}，且此时的代价为 s+c.

至于这个结论怎么推出来，可以先假设只有 (x,y) 有用，然后不断推出其他有用的 (x,y)，直到不能推出新的为止.

设 s,x,y,z 为前缀 i-1 的信息，考虑推出前缀 i 的信息 s',x',y',z'. 经过简单分讨和贪心可以求出. 大致思路就是按 b_i 是否为 0 分为两类，考虑 c 取 [0,z] 时得到的可能的 (x',y')，把最优的取出来，表示成 (x',y',z') 的形式.

P12558 [UOI 2024] Heroes and Monsters (2.5)

如果确定了 S，那么肯定是 S 与前 |S| 个怪物匹配，剩下的与后 n-|S| 个怪物匹配，并且是小的匹配小的，大的匹配大的.

设 sa_i 为 a 中 \leq i 的数的个数，同理有 sb_i. 设 s_i 为 S 中 \leq i 的个数.

若 i\in S，那么会产生形如 S 中小于等于 i 的数的个数 \leq sb_i 的约束（s_i\leq sb_i）；若 i\not\in S，那么会产生形如 S 中大于 i 的数的个数 \geq sb_i-sa_i 的约束（|S|-s_i\geq sb_i-sa_i）. 由于两个约束同时存在，因此直接做只能做到 O(n^3).

如果约束是给定的，那么是没法做的，但是此题的约束有很好的性质. 首先显然有 s_i\leq |S| 与 |S|-s_i\geq |S|-sa_i 成立. 因此当 |S|\leq sb_i 时，s_i\leq sb_i 的约束弱于 s_i\leq|S|，是没用的；当 |S|>sb_i 时，|S|-s_i\geq sb_i-sa_i 的约束弱于 |S|-s_i\geq |S|-sa_i，是没用的. 即第一种约束只在 sb_i\leq |S| 时有用，第二种约束只在 sb_i>|S| 时有用，两种约束不交，故可以左右两边分别 dp，最后合起来，复杂度 O(n^2).

一个直观的理解方式就是画一个二分图，要求左部点 S 内的数向右部点 1\sim |S| 连边且只向左连，S 以外的数只向右连，那么我们找到分界线 b_{|S|}+0.5，跨过分界线的连边一定合法，故可以分开来 dp.

turing cup 2025 t3 (3.5)

考虑判断 a 是否合法.

建立二分图模型，左部点有 n 个点表示 n 个球队，右部点有 \binom n2 个点表示比赛，对于右部点 (i,j)，我们将他和左部点的 i 和 j 连边流量为 1，左部点与源点间的流量为 a_i，右部点与汇点间的流量为 2，那么合法当且仅当满流.

使用 hall 定理，枚举右部点集合 T=\{(u_i,v_i)\mid 1\leq i\leq k\}，那么设 S=\{u_i\mid 1\leq i\leq k\}\cup\{v_i\mid 1\leq i\leq k\}，则要求 \sum_{x\in S}a_x\geq|T|. 考虑最紧的限制，那么将 a 从小到大排序后，显然存在一个 t，使得 T 包含所有二元组 (i,j)\pod{1\leq i<j\leq t}.

因此 a 合法当且仅当，将 a 排序后，有 \forall 1\leq i\leq n:\sum_{k=1}^ia_k\geq i(i-1).

设 b_i=a_i-2(i-1)，那么上式等价于 \forall 1\leq i\leq n:\sum_{k=1}^ib_k\geq 0.

考虑 l=0 时 r 满足什么条件答案为 0：显然有 \sum_{k=1}^i(r_k-2(k-1))\geq0.

当 r=0 时，可以把 l_i 变成 2(n-1)-l_i，然后用同样的方法判断. 那么合起来呢？事实上，若 l,r 分别满足条件，则合起来也满足条件.

考虑这样一个构造 a 的过程：初始 a_i=l_i，每次选择最小的 a_i 满足 a_i<r_i，让 a_i 加 1，那么最后 a 一定形如，把 (l_i,r_i,a_i) 按照 a_i 从小到大排序后，一段前缀满足 a_i=r_i，一段后缀满足 a_i=l_i，中间一段 a_i=p,p+1，设中间这段为 [L,R].

由于 r 合法，因此 [1,L-1] 合法；由于 l 合法，因此 \forall i\in(R,n]:\sum_{k=i}^n(2(n-1)-l_k-2(n-k))\geq 0，即 \sum_{k=i}^n(l_k-2(k-1))\leq 0，即 \sum_{k=1}^{i-1}(l_k-2(k-1))\geq0，因此 [R,n] 合法.

考虑中间 [L,R) 一段，由于 a_i-2(i-1) 单调递减，故前缀和数组单峰，由于单峰函数极小值在两侧，故中间合法.

因此，我们只需对 l,r 分别求出答案，加起来就是最终答案.

现在我们问题变成，给定 b_i=i(i-1)，你需要支持单点修改 a_i，查询 \max_r(b_r-\sum_{l=1}^ra_l).

线段树分治变成加点. 设 p 为 a 的前缀和数组，初始令 p_i=[i>0]\cdot(+\infty),q=b，那么在 a 中加入 x 相当于 \forall i:p_i=\min(p_i,p_{i-1}+x)，然后查询 \max_i (q_i-p_i). 我们 把视角从 a 切换到 b，那么相当于 \forall i:q_i=\max(q_i,q_{i+1}-x)，查询 \max_i (q_i-a_i). 由于起初只有 a_0 有值，因此等价于查询 q_0.

考虑刻画 q_i=\max(q_i,q_{i+1}-x) 的操作，设 c 为 q 的差分数组，起初 c 单调递增，操作相当于找到 c_i<x\leq c_{i+1} 的 i，将 c_i,c_{i+1} 删掉，替换为 c_i+c_{i+1}-x（特别地，若 x\leq c_1，则把 c_0,c_1 删掉加入 c_0+c_1-x），显然操作后 c 还是递增的（但可能 c_0> c_1）.

直接平衡树维护 c 就可以 O(n\log^2n). 注意到我们只需要知道 c_0，因此在线段树分治的过程中，假设之后需要加入 w 个数，那么只有 c_{0\sim w} 是有用的. 只保留有用的位置，双指针进行修改，复杂度 O(n\log n).

P8176 [CEOI 2021] Wells (2)

P3771 [CTSC2017] 网络 \color{green}\star

P9867 [POI 2021 ~2022R2] kon \color{green}\star

P8192 [USACO22FEB] Paint by Rectangles P \color{green}\star

P6818 [PA 2013] Działka \color{green}\star

P11815 [PA 2019 Final] 领地 / Terytoria \color{green}\star

P4858 [PA 2013] Karty \color{green}\star

P11613 [PA 2016] 覆盖 / Pokrycia \color{green}\star \color{green}\star

P7295 [USACO21JAN] Paint by Letters P \color{green}\star \color{green}\star

P5907 数列求和加强版 / SPOJ MOON4 \color{green}\star

P6817 [PA 2013] Filary \color{green}\star

P9417 [POI 2021/2022 R1] Druk \color{green}\star

P9036 「KDOI-04」挑战 NPC Ⅲ \color{green}\star

P8906 [USACO22DEC] Breakdown P \color{green}\star

P6943 [ICPC 2018 WF] Conquer The World \color{green}\star

P11812 [PA 2015] 精确打击 / Kontrmanifestacja \color{green}\star

P7831 [CCO 2021] Travelling Merchant \color{green}\star

P7481 梦现时刻 \color{green}\star