我也不知道我在总集什么但总之 2026 题目总集

CF573D Bear and Cavalry

总之我只会 $O(nq)$。将 $w$ 和 $h$ 分别排序，存一下每个战士对应的马，每次修改直接交换。每次询问从前到后统计答案，只需要这一个对应，然后左右两个交叉对应，然后三个对应，这几种情况取最大就行。

CF838D Airplane Arrangements

方案数也可以转成概率乘总方案数。 我们将问题转换为每个人随机指定一个位置并开始走，求最后合法的概率。那这样仍然是求解困难的，我们可以将其想象成在一个长度为 $n$ 的环上顺时针或逆时针走，那就可以在 $1$ 与 $n$ 之间加入一个虚点表示无解。

则问题转为统计给一个 $n+1$ 的环分配 $m$ 个人任意走最后使得 $n+1$ 没有被占据的概率，一个位置被占据的概率为 $\frac{m}{n+1}$，可以得到答案发生的概率为 $\frac{n+1-m}{n+1}$，乘以方案数 $(2 \times (n+1))^m$ 即可。

CF1814D Balancing Weapons

有一说一，富文本编辑器写得真爽

首先，此问题一定有解，且答案的上界显然为 $n$。答案要更优，一定有一把枪的 $p_i$ 是不变的。去枚举这个不变的，则其他 $p_j$ 都要向这个 $p_i$ 调整。此时对于其它的每把枪，$p_j$ 只会调整为以下值：

• 不变。
• 变为不超过 $p_i$ 且为 $f_j$ 倍数的最大值。
• 变为超过 $p_i$ 且为 $f_j$ 倍数的最小值。

因此，可能的取值数量为 $O(n)$。将取值排序，使用双指针维护极差不超过 $k$ 的极大区间，检查包含的枪械种类数是否为 $n$ 即可。

以后可以分讨出所有情况，方案总数有时候是很好弄的。

CF938F Erasing Substrings

字典序最优化问题可以考虑逐位贪心。

我们假设 $dp_{i,j}$ 表示现在枚举到了答案第 $i$ 个字符，然后我们已经用掉了二进制 $j$ 的段。

我们发现这个题最有趣的一点是，你状压之后每个 dp 的位置可以恰好对应一个状态。我们只需要做 $i$ 轮，每一轮对 $dp_{i,j}$ 的 $0/1$ 去求值就好了。

我们发现，$dp_{i,j}$ 为 $1$ 当且仅当存在一个 $dp_{i-1,?}$ 可以转移且 $a_{i+j}$ 为可以转移到的位置的字典序最小值。

然后我们考虑去用 SOSdp 对 $dp_{i-1,0 \sim 2^k-1}$ 去拉可能，然后挨个判断即可。

CF135E Weak Subsequence

性质是，最长的弱串是一个前缀或后缀，反证法可证明。$[1,i]$ 是最长弱串的一个必要性质是，$s_i$ 在 $(i,n]$ 中出现且 $(i,n]$ 中无重复字符。分讨，要么减掉算重算多的部分，要么将必要性转为充要性。

由最长弱串的必要性可以想到，枚举 $s$ 前后缀无重复字符的长度为 $i$，钦定这样的前后缀一定有一个紧挨着最长弱串。讨论即可。

CF1055F Tree and XOR

树上路径异或要差分，这样的话路径异或就转成了两点异或，这个问题就转换到了序列上。

异或还要想到 0/1Trie。 将所有数插入 0/1Trie，考虑贪心地从高位到低位考虑答案，因为只要高位较大，低位就不用考虑了。接下来对于每个位，决策往 $0$ 走还是往 $1$ 走就解决了。

CF1879F Last Man Standing

TBD.

CF1943D2 Counting Is Fun (Hard Version)

如果没有 $l<r$ 的限制一定有解，于是我们考虑这个条件到底带来了什么性质。

显然，如果存在 $i$ 满足 $a_i > a_{i-1} + a_{i+1}$，则必定无解。

计数 $a_i \geq a_{i-1} - a_{i-2}$，一个做法是设 $f_{i,x,y}$ 表示前 $i$ 个位置中位置 $i$ 是 $x$ 且 $i-1$ 是 $y$ 的方案数，过不了。继续找性质，发现一个重要性质：不合法的位置不会相邻。所以我们可以直接从 $i-2$ 转移而不用考虑 $i-3$，设 $f_{i,j}$ 表示考虑到第 $i$ 个数，末尾是 $j$。

$$f_{i,j} \gets \sum f_{i-1} - \sum_{x=0} f_{i-2,x} \times (k-j-x)$$

CF1942G Bessie and Cards

首先，“抽 $1$ 张”卡是无用的，我们可以忽略掉。其次打法也不重要，抽到就可以打。特殊卡可以看成“抽 $0$ 卡”。

$0$ 张和 $2$ 张可以分别看成 $+1$ 和 $-1$，容易想到括号序列，然后初始有 $5$ 次。括号序列可以转化为格路计数。

记 $f(x,y)$ 表示抽了 $x$ 张 $0$，$y$ 张 $2$ 的方案数，转化为每次向上或向右走一格，也就是从 $(0,4)$ 走到 $(x,y+4)$ 且不跨越 $y=x$，不合法的方案等价于走到 $(y+5,x-1)$，得到 $f(x,y) = \binom{x+y}{y} - \binom{x+y}{y+5}$。

对于正好选了 $x+5$ 张 $0$ 和 $x$ 张 $2$ 的情况，因为最后一次一定是 $0$，直接去除最后一次的贡献，等价于从 $(0,4)$ 走到 $(x+4,x+4)$，对答案的贡献为 $f(x+4,x) \times \binom{x+5}{x} \times \binom{a+c-2 \times x}{a-x}$。

类似地，对于全抽完的情况，贡献是 $f(a+5,c) \times \binom{a+5}{5}$。

最后全部加起来，除以总方案数 $\binom{a+c+5}{a,c,5}$。

CF1852C Ina of the Mountain

TBD.

CF1990E2 Catch the Mole(Hard Version)

TBD.

CF1917F Construct Tree

做法大概是找几条性质，有点复杂。

首先给 $l$ 从小到大排序。

• 性质 1：如果序列最大的两个值的和大于 $d$（即 $l_n + l_{n - 1} > d$），则一定无解。
  证明：一定存在一条跨过这两条边的路径，使得这条路径的和大于 $d$。
• 性质 2：如果存在 $l$ 的一个子集 $S$，使得 $S$ 的和为 $d$，并且 $l$ 的最大值在 $S$ 集合内（即存在 $S \subseteq l,\sum\limits_{i \in S} l_i = d,n \in S$），则一定有解。
  证明：可以构造一条长为 $|S|$ 的链，然后把 $(1,2)$ 的边权设为 $l_n$，其他没有用到的边都一定有 $l_i \leq 1_n$，直接把这些边连在结点 $2$ 上即可，这些边无论怎么与已放的边组合都不会使得直径变得更大。
• 性质 3：如果存在 $l$ 的两个互不相交的子集 $s1,d2$ 使得这两个子集的和都不小于 $l_n$，并且 $s1,s2$ 的和恰好为 $d$（即存在 $s1 \subseteq l,s2 \subseteq l,s1 \cap s2 = \varnothing,(\sum\limits_{i \in s1} l_i) \geq l_n,(\sum\limits_{i \in s2} l_i) \geq l_n,(\sum\limits_{i \in s1} l_i)+(\sum\limits_{i \in s2} l_i) = d$），则一定有解。
  证明：可以同上构造一条链，然后找到一个点 $u$，使得左端点到 $u$ 的边权和为 $\sum\limits_{i \in s1} l_i$，把剩下的边挂在 $u$ 上即可。

对于性质 2，直接 $O(nd)$ 跑一个背包即可。
对于性质 3，设 $dp(i,j)$ 表示第一个集合和为 $i$，第二个集合和为 $j$ 是否可以得到，也可以直接跑背包，这样做是 $nd ^ 2$ 的，由于状态是 $01$，可以直接用 $bitset$ 优化，这样时间复杂度是 $O(\frac{nd ^ 2}{w})$ 的，可以通过。

CF1363F Rotating Substrings

TBD.

CF1626F A Random Code Problem

TBD.

CF1767E Algebra Flash

TBD.

CF1858E2 Rollbacks (Hard Version)

TBD.

CF1393E2 Twilight and Ancient Scroll (harder version)

Unaccepted.

CF1809G Prediction

TBD.

CF1949J Amanda the Amoeba

TBD.

CF794E Choosing Carrot

TBD.

CF1107F Vasya and Endless Credits

TBD.

CF1863G Swaps

TBD.

CF1906B Button Pressing

TBD.

CF1893D Colorful Constructive

TBD.

CF1392G Omkar and Pies

Unaccepted.

CF1731F Function Sum

TBD.

CF1834F Typewriter

我们先考虑单次答案求的到底是什么。根据题意，往右移动是无代价的，而往左移则需要 $1$ 的代价。

那单次答案就是需要往左移动的元素个数。

$$Ans = \sum_{i=1}^{n} [p_{i} < i]$$

接下来我们引入移动与翻转操作。有个很妙的点是，加上这两种操作，排列也只有 $2 \times n$ 种情况，我们完全可以预处理出来，后面维护一个偏移量和一个翻转标志，最后只需 $O(1)$ 查询答案。下述偏移量均为向右移动时的偏移量。

先来看没翻转的情况。显然，我们只需要算出一个元素对答案的哪些区间有所贡献。

设 $v$ 表示当前元素 $p_{i}$，我们希望它对答案有贡献，即要求它的值小于它的新位置。

$$v < new\_pos \implies new\_pos \in [v + 1, n]$$

这样的有效位置有 $n-(v+1)+1$ 也就是 $n-v$ 个。

贡献开始的偏移量就是 $v$ 这个元素移到 $v+1$ 这个位置需要的步数，注意考虑循环。

$$S = (v + 1 - i + n) \pmod n$$

这一块不用写树状数组什么的，维护答案数组的差分数组，每次直接在端点加减即可，最后做前缀和。注意判一下，如果贡献区间的右端点 $r \ge n$ 了，那需要把溢出的一部分放到左边去。

翻转过来也是一样的。

对于移动操作，算新的偏移量就可以。注意第三个操作，更新翻转标志以后，偏移量也是随之变化了的，具体的式子写在下面了。

$$offset = (n - offset) \pmod n$$

复杂度线性。

CF1788F XOR, Tree, and Queries

TBD.

CF1827D Two Centroids

TBD.

CF1422E Minlexes

TBD.

CF1949D Funny or Scary?

TBD.

CF1842F Tenzing and Tree

TBD.

CF989E A Trance of Nightfall

Unaccepted.

CF1421E Swedish Heroes

TBD.

CF1799G Count Voting

TBD.

CF1808E3 Minibuses on Venus (hard version)

Unaccepted.

CF1956E2 Nene vs. Monsters (Hard Version)

TBD.

CF1814F Communication Towers

TBD.

CF627D Preorder Test

TBD.

CF1906C Cursed Game

肯定不能瞎构造，最好的方法就是直接找到哪些地方有孔。这个其实很好找，输出一个仅在 $(3,3)$ 为 $1$ 的矩阵就行了。

知道哪些地方有孔以后就好针对性构造了。我们可以直接对每个 $(i,j)$ 算一下目前答案，如果不合法，我们去修正坐标字典序最大的一个孔，这样由于后面的格子在前面的窗口对应更靠后的孔坐标（超越了最大孔），就绝对不会破坏已经修好的前面窗口的奇偶性。

所以单次会有两个询问，绰绰有余。

这个做法在 $n = 3$ 的时候不太行，特判掉随机化一下，容易证明期望询问次数也是 $2$。

CF1835B Lottery

TBD.

CF1762F Good Pairs

TBD.

CF1487F Ones

TBD.

CF1775F Laboratory on Pluto

TBD.

CF1884E Hard Design

Unaccepted.

CF1758F Decent Division

Unaccepted.

CF1019D Large Triangle

TBD.

CF888F Connecting Vertices

TBD.

CF1763F Edge Queries

TBD.

CF1764H Doremy’s Paint 2

Unaccepted.

CF1028F Make Symmetrical

TBD.

CF1178F2 Long Colorful Strip

TBD.

CF1753D The Beach

TBD.

CF2181G Greta’s Game

TBD.

CF2030F Orangutan Approved Subarrays

TBD.

CF2107F2 Cycling (Hard Version)

超出我的知识范围了。

CF2181E Elevator Against Humanity

Unaccepted.

CF1837F Editorial for Two

TBD.

CF1661F Teleporters

Unaccepted.

CF1374E2 Reading Books (hard version)

Unaccepted.

CF2176E Remove at the lowest cost

Unaccepted.

CF1771F Hossam and Range Minimum Query

奇偶性往两个方向想，一个是 bitset，一个是异或哈希。

板子题，将每个数赋一个随机 hash 值，主席树上二分。

CF1870F Lazy Numbers

Unaccepted.

CF1082F Speed Dial

Unaccepted.

CF1874C Jellyfish and EVA

设 $f_u$ 为最优情况下 $u$ 走到 $n$ 的概率。

显然从 $n$ 开始倒推，再设 $p_{u \to v}$ 表示 $u$ 到 $v$ 的概率，我们显然有如下式子。

$$f_u = \sum_{(u,v) \in E} f_v \times p_{u \to v}$$

$p_{u \to v}$ 还能再拆。贪心地，对于一个节点的所有出边，优先选概率大的。设 $g_{i,j}$ 表示在一个出度为 $i$ 的点走第 $j$ 优点的概率。

$g$ 显然是可以预处理的，于是就做完了。具体地，初始条件为 $g_{i,1} = \frac{1}{i}$，其他情况下我肯定选最优边，根据对方选的边，得到转移 $g_{i,j} = g_{i-2,j-1} \times \frac{i-j}{i} + g_{i-2,j-2} \times \frac{j-2}{i}$。