2026.11.2

P15133 [ROIR 2026] 最后的滑动窗口问题

对 \(u\) 维护 \(L_u,R_u\) 表示左边第一个小于等于 \(a_u\) 的位置加 \(1\)，右边第一个小于 \(a_u\) 的位置减 \(1\)。

考虑 \(u\) 对 \((l,k)\) 的贡献。显然，贡献为：对 \(i\in [L_u,u]\)，\(k\in [u-i+1,R_u-i+1]\) 的 \((l,k)\) 产生 \(a_u\) 的贡献。

以 \(l\) 为横坐标，\(k\) 为纵坐标。贡献可以看作是一个平行四边形。

考虑把平行四边形补成矩形，再除去两个三角形的贡献。也就是：

  1. 对以 \((L_u,1)\) 为左下角，\((u,R_u-L_u+1)\) 为右上角的矩形中每个点增加 \(a_u\) 的贡献。
  2. 对由 \((L_u,1),(L_u,u-L_u),(u-1,1)\) 构成的直角三角形中每个点减少 \(a_u\) 的贡献（可能不存在）。
  3. 对由 \((L_u+1,R_u-L_u+1),(u,R_u-L_u+1),(u,R_u-u+2)\) 构成的直角三角形中每个点减少 \(a_u\) 的贡献（可能不存在）。

将询问拆成对 \(l\) 的前缀查询。然后对 \(k\) 扫描线。

第二类可以看作是对 \(x \le l \le y-k\) 的 \((l,k)\) 做加法操作。此时贡献形如 \(v \times |[x,y-k]\cap [1,p]|\)，其中 \(v\) 为加法操作的值，\([1,p]\) 为一个查询前缀。有 \(|[x,y-k]\cap [1,p]| = \min(y-k,p) - \min(x-1,p)\)（这里要排除 \(x > y-k\) 的情况，这个相当于每个 \((x,y)\) 都有一个存在时间）。后者直接树状数组，前者讨论大小：

  1. \(y \ge p+k\)。贡献为 \(p\)。
  2. \(y < p+k\)。贡献为 \(y-k\)。

也是树状数组维护。

第三类同理可以看作对 \(y-k\le l \le x\) 的 \((l,k)\) 做加法操作。同样拆成 \(\min(x,p) - \min(y-k-1,p)\)。对后者讨论大小。

时间复杂度 \(O(n\log n)\)。

P15088 [UOI 2025 II Stage] Digital Game

注意到 \(n \ge 2|\sum|\) 时一定不能战胜 Us。

考虑证明 \(n = 2|\sum |,n = 2|\sum|+1\) 时不行，\(n > 2|\sum|+1\) 的情况一定在不断删两个数的过程中变成这两个之一。

  1. \(n = 2|\sum|\)。
    1. 所有数均出现 \(2\) 次。那么后手跟着先手删，一定可以达到 \(n = 2|\sum| =2\) 的局面。此时 Us 赢。
    2. 存在一个数出现至少 \(3\) 次。如果先手删出现 \(2\) 次的，后手就跟着删；如果先手删出现 \(1\) 次的，后手就删出现至少 \(3\) 次的；如果先手删出现至少 \(3\) 次的，后手就删出现 \(1\) 次的。这样一轮之后依旧满足 \(n = 2|\sum|\)。此时 Us 赢。
  2. \(n = 2|\sum|+1\)。
    1. 存在数出现 \(1\) 次。先手或后手一定会有一个删它。之后仍然满足 \(n = 2|\sum|+1\)。
    2. 所有数出现至少 \(2\) 次。此时一定存在一个数出现奇数次。出现奇数次的数数量要么不变，要么减少 \(1\)，最后在 \(n=3\) 时一定出现两个相同的数相邻。此时 Us 赢。

对于 \(n \le 19\) 的情况，状压即可。时间复杂度 \(O(Tn2^n)\)。

P9393 紫丁香

拆位，看每一位能不能是 \(1\)。

相当于给定集合 \(S\)，问能否在若干次操作后使得 \(S\) 内所有二进制为均为 \(1\)。

倒着推。把 \(S\) 外的二进制位看成 \(?\)，即通配符。

考虑一个状态 \(t\) 可以被哪些状态 \(s\) 通过 \(T\) 推出来。分情况讨论：

  1. \(T_i = 0\)。此时要求 \(t_i \ne 1\)。\(s_i = ?\)。
  2. \(T_i = 1\)。此时要求 \(t_i \ne 0\)。\(s_i = ?\)。
  3. \(T_i = -\)。此时要求 \(t_i = s_i\)。

相当于只要 \(T\) 和 \(t\) 匹配（除开 \(T_i = -\) 的部分），\(s\) 就相当于 \(t\) 将所有 \(T_i \ne -\) 的二进制位变成统配符。

因为初始 \(S_i\in \{?,1\}\)，所以 \(T_i = 1\) 的要求自然满足了。

那么操作相当于，每次选择一个 \(T\)，要求不存在 \(T_i =0\land t_i =1\)。然后将所有 \(T_i = 1\) 的二进制为对应 \(t_i\) 改成通配符。问操作若干次后能否与初始二进制数匹配。

那么维护 \(g(S)\) 为满足 \(\not \exist i\in S, T_{x,i} = 0\) 的 \(\{i| T_{x,i}=-\}\) 交集。定义 \(f(S)\) 表示如果初始时只有 \(i\in S\) 的 \(i\) 满足 \(t_i = 1\)，操作若干次后 \(t_i = 1\) 的 \(i\) 构成的集合。那么转移为：\(f(S) = f(g(S))\)。特别的，若 \(g(S) = S\)，则 \(f(S) = S\)。

这样判定给定的集合 \(S\) 是否合法，就可以直接看 \(f(S)\) 与初始二进制数是否匹配了。

维护 \(g(S)\) 相当于是一个高维后缀与，\(f(S)\) 的转移是 \(O(1)\) 的，判定合法也是 \(O(1)\) 的。

整体时间复杂度 \(O(n+m2^m+qm)\)。

P8702 [蓝桥杯 2019 国 B] 燃烧权杖

记 \(X = \lceil\frac{x}{10}\rceil,Y = \lceil\frac{y}{10}\rceil\)。

显然，士兵是没有用的，因为攻击士兵对二元组 \((X,Y)\) 不产生影响。

问题变成每次等概率将 \(X\) 或 \(Y\) 减少 \(1\)。问 \(Y\) 在 \(X\) 之前减到 \(0\) 的概率。

设 \(Y\) 减到 \(0\) 时操作了 \(n\) 次。那么满足 \(n < X+Y\)，概率为 \(\frac{\binom{n-1}{Y-1}}{2^n}\)。

那么答案就是 \(\sum\limits_{n=(Y-1)}^{X+(Y-1)}\frac{\binom{n}{(Y-1)}}{2^{n+1}}\)。这个也可以写成 \(\frac{1}{2^{X+(Y-1)}}\sum\limits_{i=0}^{X-1}\binom{X+(Y-1)}{i}\)。相当于取到 \(Y\) 操作到 \(0\) 的时刻，前面对应一种操作，后面无论怎么取都是合法的，与概率和为 \(1\)。

记 \(n = X+(Y-1),m = X-1\)。问题变成求 \(\frac{1}{2^n}\sum\limits_{i=0}^{m}\binom{n}{i}\)。

\(\binom{n}{m}\bmod p = \prod\binom{n_i}{m_i}\bmod p\)，其中 \(n_{1\sim k},m_{1\sim k}\) 分别为 \(n,m\) 的 \(p\) 进制表示。

那么用数位 DP 就就可以了。时间复杂度 \(O(Tp\log_p x)\)。

2026.11.3

CF1601D Difficult Mountain

先去掉那些 \(s_i < d\) 的人，因为他们一定无法成功登山，且把他们放最后对其他人不产生影响。

再去掉 \(a_i < d\) 的人，把他们放最前面一定不劣。

将剩下的人按 \(a\) 升序排序，\(a\) 相同按 \(s\) 降序排序。

记成功登山且改变了难度的人依次为 \(q_{1\sim k}\)。满足 \(d < a_{q_1}。那么一个简单的想法是：既然其它人不改变难度，为了让他们尽可能能成功登山，就应该排在第一个 \(a_{q_i} > a_x\) 的人 \(q_i\) 之后，\(q_{i+1}\) 之前。

即顺序应该是：\(q_1,[1,q_{1}-1],q_2,[q_{1}+1,q_2-1],q_3,\dots,q_k,[q_{k-1}+1,q_k-1],[q_k+1,n]\)。因为 \(q_k\) 是最后一个改变了难度的人，所以钦定 \(i\in [q_k+1,n]\) 均未成功登山。

定义状态函数 \(f_i\) 为考虑完 \([1,i]\) 中的人，且 \(i\) 是最后一个成功登山的人时，成功登山人数最大值。令 \(a_0 = d\)。

转移为：\(f_i =\max\limits_{j=0}^{i-1}(f_j +1+ \sum\limits_{k=j+1}^{i-1}[s_k \ge a_i])[s_i \ge a_j]\)。

初始化 \(f_{0}=0\)，答案为 \(\max\limits_{i=0}^{n}f_i + \Delta\)。其中 \(\Delta\) 为 \(a_i < d\) 的人产生的贡献。

直接线段树维护就行了。\(\sum [s_k \ge a_i]\) 相当于是对每个 \(k\) 有个存在时间区间，在这个区间内会额外对 \(j < k\) 产生 \(1\) 的贡献。

时间复杂度 \(O(n\log n)\)。

QOJ6842 Popcount 单词

对 \([0,2^{30}-1]\) 建 Trie（从高位往低位）。一个叶子的权值为从根走到它过程中，向右走的次数奇偶性。

显然，叶子的权值恰好就是 \(\text{popc}(x)\bmod 2\) 的结果。

对于区间 \([l,r]\)，可以拆成 \(O(\log V)\) 个完整子树。

不难发现，如果记从下往上第 \(i\) 层（不包括叶子），从左往右第一个子树为 \(S_i\)，那么有 \(S_1 = 01,S_i = S_{i-1}+\text{rev}(S_{i-1})\)。且第 \(i\) 层中所有子树均能表示成 \(S_i\) 或 \(\text{rev}(S_{i})\)。

对模式串建 AC 自动机。维护 \(nxt(u,i,0/1)\) 表示从点 \(u\) 开始，在 AC 自动机中走完 \(S_i\) 或 \(\text{rev}(S_i)\) 后到达的点。有：

  1. \(nxt(u,i,0) = nxt(nxt(u,i-1,0),i-1,1)\)。
  2. \(nxt(u,i,1) = nxt(nxt(u,i-1,1),i-1,0)\)。

初始状态：

  1. \(nxt(u,0,0) = out(u,0)\)。
  2. \(nxt(u,0,1) = out(u,1)\)。

那么对于给定的 \(n\) 个区间 \([l_i,r_i]\)，每个都拆成 \(O(\log V)\) 个子树后从左往右遍历，就可以得到形如对从 \(u\) 开始，在 AC 自动机中走 \(S_i\) 或 \(\text{rev}(S_i)\)，并对中途经过的每个点 \(v\)，将 fail 树上 \(v\) 到根路径权值加 \(1\) 的操作。

维护 \(tag(u,i,0/1)\) 表示从点 \(u\)​ 开始，在 AC 自动机中走 \(S_i\) 或 \(\text{rev}(S_i)\)，并对中途经过的每个点 \(v\)，将 fail 树上 \(v\) 到根路径权值加 \(tag(u,i,0/1)\)。

考虑标记下传。有：

  1. \(tag(u,i-1,0)\gets tag(u,i,0),tag(nxt(u,i-1,0),i-1,1)\gets tag(u,i,0)\)。
  2. \(tag(u,i-1,1)\gets tag(u,i,1),tag(nxt(u,i-1,1),i-1,0)\gets tag(u,i,1)\)。

时间复杂度 \(O((n+\sum |p_i|)\log V)\)。

QOJ1429 击中

二分答案。

记 \(s_i\) 为前缀和。那么要求形如：

  1. \(s_{-\infin} \ge 0\)。
  2. \(s_i \ge s_{i-1}\)。
  3. \(1\le s_{r_i} - s_{l_i-1}\le x\)。

差分约束连边：

  1. \((i-1)\to i\)，边权为 \(0\)。
  2. \(r_i\to (l_i-1)\)，边权为 \(-x\)。
  3. \((l_i-1)\to r_i\)，边权为 \(1\)。

直接跑是不是就可以了。卡卡能过。

P15925 [TOPC 2023] Introversion

将颜色分成 \(3\) 类，分别是出现过 \(0,1,2\) 次。记它们的数量分别为 \(A,B,C\)。

容斥，记 \(G(x,y)\) 为钦定有 \(x\) 对相邻位置是第 \(1\) 类颜色且颜色相同，有 \(y\) 对相邻位置是第 \(2\) 类颜色且颜色相同的方案数。

那么答案为：\(\sum\limits_{x\ge 0}^{}\sum\limits_{y\ge 0}^{} (-1)^{x+y}G(x,y)\frac{(2A-2x + B-y)!}{2^{A-x}}\)。

定义 \(g_i(x,y)\) 为考虑完位置 \([1,i]\) 的方案数。转移为：

  1. \(g_i(x,y)\gets g_{i-1}(x,y)\)。
  2. 若 \(x_i=0,x_{i-1}=0\)。\(g_i(x+1,y)\gets g_{i-2}(x,y)\times (A - x)\)。
  3. 若 \(x_i = 0,x_{i-1}\ne 0\) 或 \(x_{i}\ne 0,x_{i-1}=0\) 且非 \(0\) 的那个颜色是第 \(2\) 类。\(g_i(x,y+1)\gets g_{i-2}(x,y)\)。

时间复杂度 \(O(Tn^3)\)。

​

P8885 「JEOI-R1」子序列

对于一个字符串的不同子串数量，转移为：

\[\begin{aligned}\\ f_{i,s_i} &= f_{i-1,0}+f_{i-1,1}+1\\ f_{i,s_i \oplus 1} &= f_{i-1,s_i\oplus 1} \end{aligned} \]

只要 \((f_{|s|,0}+f_{|s|,1})\bmod 2=0\) 就说明这个子串 \(s\) 是好的。

将 \(f_{i,j}\) 对 \(2\) 取模，有：

\[\begin{aligned}\\ f_{i,s_i} = f_{i-1,0}\oplus f_{i-1,1}\oplus 1\\ f_{i,s_i\oplus 1} = f_{i-1,s_i\oplus 1}\\ \end{aligned} \]

那么就可以用两个 \(01\) 来表示状态 \((f_{0},f_{1})\) 了。

把它看成一个两位的二进制数，用十进制表示成 \(0\sim 2\)（显然，状态 \(3\) 永远不会存在）。记 \(\text{nxt}(x,0/1)\) 表示在状态 \(x\) 的基础上再转移字符 \(0/1\) 后得到的状态。

维护状态函数 \(g_{i,S,0/1}\) 表示考虑完 \(s[:i]\)，且有奇数个后缀 \(s[j:i]\) 的状态 \((f_0,f_1)\) 集合为 \(S\)，其子串 \(s[j:k]\) 中满足 \(f_0\oplus f_1 = 0\) 的有偶数或奇数个的方案数。

对 \(s_i\) 分情况讨论：

  1. \(s_i = 0\)。\(g_{i,S',(c + |S' \cap \{0\}|)\bmod 2}\gets g_{i-1,S,c}\)。其中 \(S'\) 为 \(\{\text{nxt}(x,0)|x\in S\}\) 并将 \(2\) 加入（如果不在集合中）或删除（如果在集合中）后得到的集合。
  2. \(s_i = 1\)。\(g_{i,S',(c + |S' \cap \{0\}|)\bmod 2}\gets g_{i-1,S,c}\)。其中 \(S'\) 为 \(\{\text{nxt}(x,0)|x\in S\}\) 并将 \(1\) 加入（如果不在集合中）或删除（如果在集合中）后得到的集合。

初始化 \(g_{0,\emptyset,0}=1\)。答案即为 \(\sum\limits_{S}g_{|s|, S,1}\)。

再压缩状态，将 \((S,c)\) 用一个五位的二进制数表示（最低位是 \(c\)）。记 \(\text{Nxt}(x,0/1)\) 表示在状态 \(x\) 的基础上再转移字符 \(0/1\) 后得到的状态。那么转移方程可以写成：

\[\begin{aligned}\\ g_{i,\text{Nxt}(x,0)}\gets g_{i-1,x}[s_i \ne 1]\\ g_{i,\text{Nxt}(x,1)}\gets g_{i-1,x}[s_i\ne 0] \end{aligned} \]

初始化 \(g_{0,0}=1\)。答案为 \(\sum\limits_{x\bmod 2 = 1}^{}g_{|s|,x}\)。

对于原问题，将转移写成矩阵的形式。放猫树上询问做到 \(O(\omega ^3 n\log n + q\omega ^3),\omega = 16\)。注意到转移矩阵只有 \(O(\omega)\) 个非 \(0\) 值，所以矩阵乘法可以做到 \(O(\omega^2)\)。整体复杂度 \(O(\omega^2 n\log n + q\omega^2)\)。

P15146 [SWERC 2025] LFS

首先 \(f(t)\) 就是字符串 \(t\) 中出现次数最多的字符。

求答案考虑枚举 \(\text{LFS}(t)\) 中包含的一个字符 \(c\)，给所有 \(c\) 出现的位置同时向左右拓展。直到某个时刻拓展后得到的字符串不一样为止。

显然，拓展次数是 \(O(|\sum |)\) 的。

对于相邻两个字符 \(c\)，维护 \(L_i,R_i\) 表示第 \(i-1\) 和 \(i\) 个字符 \(c\)，能向左向右拓展到最长长度（和 \(|\sum|\) 取较小值）。这个暴力是 \(O(n|\sum|)\) 的。

询问时枚举字符 \(c\) 后就是一个区间 \(\min\)。用 st 表做到 \(O(n|\sum| +n\log n + q|\sum|)\)。

P15316 [VKOSHP 2025] Strange Sum

记 \(W(l,r) = \sum\limits_{l \le L \le R \le r}^{} w_{L,R}\)。

从小到大枚举 \(v\)，记 \(b_i = [a_i \ge v]\)。设 \(b\) 中 \(1\) 构成的连续段为 \([l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]\)。贡献 \(g(v) = \sum\limits_{i=1}^{k}W(l_i,r_i)\)。

那么 \(f(a) = \sum\limits_{v=1}^{+\infin}g(v)\)。

把某个 \(v\) 贡献的一个由 \(1\) 构成的连续段 \([l,r]\) 看成消耗 \(r - l + 1\) 的代价获得 \(W(l,r)\) 的贡献。

贡献可以直接写成 \(\sum\limits_{1\le l\le r \le n}^{}W(l,r)\cdot c(l,r)\)，其中 \(\sum\limits_{1\le l \le r\le n}^{}c(l,r) = x\)。因为 \(w_{l,r}\ge 1\)，所以对于 \(a < b < c < d\)，有 \(W(b,c)+W(a,d) > W(a,c) + W(b,d)\)，最优解一定不会出现相交的情况。

记 \(v_i = \max\limits_{r-l+1=i}^{}W(l,r)\)。问题变成给定 \(v_{1\sim n}\)，对于所有满足 \(\sum\limits_{i=1}^{n}c_i = x\) 的非负整数数组 \(c\)，求 \(\sum\limits_{i=1}^{n}c_i\cdot v_i\) 的最大值。

这个是简单的，先选性价比最大的那个，在背包剩余体积不超过 \(n^2\) 时再跑完全背包就行了。

时间复杂度 \(O(tn^3)\)。

P15110 Silent End

注意到每个人都至少被评价了一次，所以对于初始状态中 \(w\) 最小的那条评价 \((u,v,w)\)，一定满足 \(a_v = w +1\)。因为如果 \(a_v = w - 1\)，说明 \(a_u < a_v\)。而 \(u\) 被评价的 \(w'\) 一定满足 \(w’ \ge w\)，所以不可能存在这样的情况。

那么从小到大枚举 \(w\) 即可。

时间复杂度 \(O(m\log m)\)。

P15173 [SWERC 2021] Drone Photo

注意到对于任意一个合法的矩形，都能找到两个直角三角形，使得直角顶点的值恰好处于另外两个顶点值之间（如果将这 \(4\) 个值离散化，那么这两个三角形分别就是以 \(2,3\) 为直角顶点构成的直角三角形）。且不合法的矩形一定找不到这样的直角三角形。

那么直接对这个三角形计数就行了。答案即为三角形数量的一半。

枚举直角顶点为 \((i,j)\)。相当于在第 \(i\) 行找一个比 \(a_{i,j}\) 大的点，第 \(j\) 列找一个比 \(a_{i,j}\) 小的点或者在第 \(i\) 行找一个比 \(a_{i,j}\) 小的点，第 \(j\) 列找一个比 \(a_{i,j}\) 大的点。

那么按照值从大到小加入点。维护 \(f_{i},g_i\) 表示第 \(i\) 行，第 \(i\) 列已经被加入的点数量即可。

时间复杂度 \(O(n^2)\)。