题解 - 2024 十一月做题记录

01

Vjudge 没做，但是感觉挺难的。

Luogu P5607 [Ynoi2013] 无力回天 NOI2017

察觉到奇偶性的关键，尝试把偶数个数的线性基建出来，发现刚好是差分数组的线性基。奇数个数的情况就是随便多插一个数进去算。

*Codeforces 1320D Reachable Strings

没写，但应该等价。

直接考虑最小表示，类似于把 11 拖到最前面，后面的 1 都是形单影只，而且这种情况下 0 连续段长度（广义）不变。所以把所有 11 删掉，直接比哈希值就可以了。另一种理解方法：相邻 0 的距离的奇偶性不变，维护这个东西的哈希值，注意头加一个 0 尾加一个 0。

02

A 串串游戏（string）

遇到字典序，直接逐位考虑。逐位枚举，记一个子序列自动机即可。

B 最长上升子序列（lis）

逐个间隔考虑，上面的每层都是 $2$ 的次幂，最后一层要拉出来讨论，可能以最后一层或倒数第二层为本位。

C 墙（wall）

逐位考虑贡献，发现类似于左边点乘右边，不好做，所以考虑从另一维入手，即值域。（等于转大于应该是显然的。）把式子推清楚就很好写了。

11.29 补题完毕。

D 有理数（number）

手动通分肯定是要的。逐个质因子讨论对乘积的贡献，发现如果两个数对这个质因子的最大次数不等，只能取小的，对最大次数相等的情况会有额外贡献，枚举额外贡献（注意范围）开 map 即可。时间：能过。

03

ZR 十连，跟没打一样，无法集中精力。不想说话。

04

AGC002E Candy Piles

观察，发现每个 1 都会从边界往内延伸一条斜线，即可。

Codeforces 1930H Interactive Mex Tree

神了，dfs 序有两个：入栈序和出栈序。【如何高级地理解出栈序呢。】

Codeforces 1819D Misha and Apples

枚举最后一次删空，后面的不能再删空是容易判的，当前点能被删空判定法是枚举上一次删空，讨论中间的前驱情况，然后这个点是有单调性的。

05

A 序列 (sequence)

尺取，实际表现中正常 gcd 快于 $O(1)$ gcd，菜。

D 牛仔 (nz)

考虑算贡献，也就是钦定一个区间，算有多少个序列。

如果模式串是牛仔序列，则整个串都是。

如果模式串并非两两不同，则左右是独立的，从中间往两边分别 DP（更简洁！），做点乘即可。

否则左右不独立，考虑从左往右 DP，每次都加上贡献，贡献除以一个系数，并且如同其它 DP 一样更新。

C 长者 (young)

我不会枚举，我不会搜索。

XOR-MST 的框架都是类似的。讨论左右两个联通块的连边，转为计算连边大于等于某个数的方案数，直接搜索即可。

B 道路（road）

二分。每个点都会连一个后缀，只要这个图可以成为一个欧拉回路（除了后缀连边可以任意重边）即可（有点像是，哈密顿回路转欧拉回路）。

06

越来越理解不了，各种理解不了。

A 纵使日薄西山

两个两个枚举，FWT。既然是降难度，然后值域比较小，就是扑空的次数很少，暴力即可。

B 即便看不到未来

这怎么会得了的？

考虑减量。考虑三维最小的位置，然后贪心删掉一个最小代价的。

C 此时此刻的光辉

随便写一个状压搜索，逐位加，用平衡说明复杂度正确。

*D 盼君勿忘

观察不难，剩下就是硬推组合和式，然后树上启发式算增量。不太想做。

07

A 飞翔（fly）

可以直接算边权。

B 子序列们（sub）

区间 DP，以最终存活为分界点。

C 钙绿（probability）

记得超乎其外，做好预处理。

*D 动态树（tree）

根号重构。可以做长剖或转二维上 KD-Tree。

Luogu P9846 [ICPC2021 Nanjing R] Paimon’s Tree

08

QOJ 9132 Painting Fences

发现只关心一个黑矩形扩展为全局。这边界讨论真够阴间的。

QOJ 9167 Coprime Array

质因数分解后讨论。答案很小。

Codeforces 1479C Continuous City

二进制拆分。

Codeforces 1994H Fortnite

解除怨念，但不知道怎么造这个题。

对于题目询问的进一步刻画：每次询问一个 $p$ 进制数 $\bmod m$ 的结果，这个 $p$ 进制数满足最高位及以下每位取值都在 $[1,26]$。

首先我们会得到 $p$，询问 aa 即可得到 $p+1$，恰好 $p+1<m$。

假设我们问了 $A\bmod m=a$（$A$ 表示字符串，同时表示 $p$ 进制数），可以得到 $m|(A-a)$——但这并没有意义，因为我们只剩一次了。

这一次可以获得另一组 $B\bmod m = b$。如果这个 $B$ 满足一些性质，那么 $m$ 可以非常快求出来，我们要非常非常快。

关键想法：我们不考虑除法，考虑减法，比如 $(A-a)-(B-b)=m$，意思就是两个相邻的 $m$ 的倍数差为 $m$。

所需要的条件是 $A-a-m\le B<A-a$，由于 $m>a$，即 $m\ge a+1$，则 $A-a-m\le A-2a-1$。那么只要 $[A-2a-1, A-a-1]$ 有至少一个可以询问的 $B$ 就可以了，无论取最小的还是最大的都可以。令 $A$ 为 zzzzzzzz 即可。

09

A ti

从循环位移的角度刻画。

B tii

分数考虑转斜率……

C tiii

找到一种单调性，发现是速度，有序 DP。

*D tiv

把图形拆开成 LCA 处的邻域和其余每个点的 $d$ 层儿子，第一部分点分治，第二部分 dsu on tree，扫描线。

10

现在打十连都不太认真。但是这一把的确是很难。

A 种花

单调栈。

其他的目前都不会。

11

ARC106E Medals

二分答案，用 Hall 定理，做高维前缀和。

*Codeforces 1342F Make It Ascending

状压，把状态的一维和答案交换，因为具有单调性。之所以没过是因为，我没有较小的常数因子。【数据删除】。【数据删除】。【数据删除】。

12

A 定向越野（walk）

猜一个结论，发现是对的……

B 字符串（str）

扫描线容易想到，KMP 过程中维护左端点集合：这个东西可以扩展，蛮有细节的。办法就是先加入自身，跳 next 删单点，右移一位就把 next 右移一位的删除同态加入。以后不乱写 KMP 了呜呜呜，border 就直接用 KMP 的写法多简洁。

C 数数（count）

摩尔投票的人数是可以扩展的。

D 逃脱（esc）/ USACO18JAN Cow at Large P

思路感觉其实不难。刻画一下条件然后直接点分治就好了。留意这里是【距离最近的叶子】，不在乎任何子树关系。

ARC125F Tree Degree Subset Sum

首先我们发现它是一个二元卷积，那完蛋了。

我们发现 $y-x$ 固定时，$x$ 是一个区间。？？？然后就做完了，这个背包改一下多重背包然后直接跑就行了。

13

A 数的拆分 (number) / Luogu P8778 [蓝桥杯 2022 省 A] 数的拆分

Powerful Number 性质，发现筛到 $V^{\frac{1}{5}}$ 为止，质因数仅四个，性质仍然优良。

B 括号序列 (bracket) / LibreOJ 6043 「雅礼集训 2017 Day7」蛐蛐国的修墙方案

我们发现把二元环贪心掉，剩下爆搜，跑得够快。

C 数据结构 (struct) / UOJ 637 【美团杯2021】A. 数据结构

扫描线。难点在于想到算贡献，然后快速刻画条件：比如说 $x$ 不出现，就是把所有的 $x$ 包含了，并且不包含任何一个 $x-1$。后面一个条件直接拿相邻的同色数讨论就可以了。

D 构造数组 (array) / Luogu P8863 「KDOI-03」构造数组

首先我们发现它是一个 $n$ 元卷积，那完蛋了。

对每种数讨论。假设当前的状态是操作序列有若干个 $0$/$1$/$2$（假设我知道现在总共有多少个数，那只要知道一个就全知道了），然后我们认为它们已经填进去了！然后要填某个数直接枚举一下组合数一下就可以了。注意组合数细节。

14

Luogu P6377 [PA2010] Termites / P3210 [HNOI2010] 取石头游戏

什么时候才会做博弈论题？什么时候才会动脑筋？

我们没有任何入手点，除了数组本身。然后我们发现，如果它有良好的单调性，我们会做。所以考虑不单调的部分。比如说，单峰：我们发现峰左右两个点一定是同一个人取的，所以可以缩，所有都会变成单谷。但是对于只有单边能选的连续段，在里面还会有一串递增，这一串递增长度为偶的时候大家都不想取，只有最后只剩它们了才会取（奇的时候把外面的端点删掉就一样了）。代码实现上，用栈做，维护两人的差值。

Luogu P9346 无可奈何花落去

第一次不好算，但是凋零的状态好办，所以让每个凋零的时刻都有 $1$ 的贡献，背包一下。

Luogu P8820 [CSP-S 2022] 数据传输

既然是静态，考虑倍增，算 $(\min, +)$ 矩阵乘积。注意 $k=3$ 可以经过路径外的点。在 LCA 处要讨论一下。

*QOJ 9562 欧伊昔

考虑推广 FWT，直接可以做到 $O(9^n)$。取众数用容斥，其它的同行同列两格可以合并，就可 $O(6^n)$。拉丁方就挑一行循环一下。但是大家的常数较小，我不说话了。

15

A 数字（number）

数位 DP 板子。注意 $n=0$！！！挂 T1 这辈子有了。

B 加训（train）

手动讨论一下，发现只关心左边的 R 和右边的 L，个数可以算，前缀和一下即可。

C 排序（sort）

显然是按前缀最大值归并。每次会把一个块劈开，平均每个根要 $O(1)$ 获取。细节上注意以前切过一刀的地方以后也跳不过去。

D 改造（modification）

Reverse LIS 改，考虑以终为始，什么样的序列给什么样的 $k$ 贡献，关心的是取出来的子序列的连续段数。注意钦定最左段和最右段是否被选，若不被选则下一段必被选，否则不优。什么时候才能场切反悔贪心……

16

So hard。

*A 书架（book）/ Codeforces 802C Heidi and Library (hard)

认为书是一股流，并没有被丢掉，只是被放在旁边。

*B 序列（seq）

没听懂。好像可以序列分治。

*C 异或（xor）

对线性空间计数，就是对最简线性基计数。DP 还没想明白。

*D 颜色（color）/ AtCoder nikkei2019_qual_f Jewels

神秘反悔贪心。

晚上打了 ABC，但是很简单，可惜的是吃了两发罚时，失败。

17

ARC 187，D 晚开是策略大失败。

A Add and Swap

在 B 后切出，真是笨完了。

考虑对一个点连续做两次操作，相当于给它和它后面一位同时 $+k$，所以只做这种事情可以把除了最后一位以外的做到不降。

假设对最后一位往前移偶数位，直到前面单调不降，后面全体加一些 $k$ 即可。如果到了第二位，还不是单调不降，做一次。还是不行，那就是无解。反正我不会。

B Sum of CC

这个简单一点。考察两个点不联通的情况。假设从左到右可以用几个极小正方形覆盖所有点，那么这些正方形互不联通。所以直接考虑每个断点左右会不会分隔开即可。

*C 1 Loop Bubble Sort

好像是刻画成前缀最大值数量相关，然后不会了。

D Many Easy Optimizations

这个赛时会了，但是写不动。

对每个右端点维护最大的左端点，每次加入一个数是区间取 $\min$，维护连续段即可，事实上只要在起点维护即可。11.20 补题完毕。

*E Replace Triplets

没研究，不会。

18

AGC009D Uninity

神了。首先发现要求最大深度最小的点分树，但先不要直接把点分治糊上去……

把点分树上深度记在每个点上，对这个东西的约束是：任意两个相等的点路径上必然有至少一个数比它们大。然后乖乖地随便找个根做树上 DP 即可。

ARC139D Priority Queue 2

这我哪会啊？？考虑对于排名相关，就画横线，大于小于分为 01 再做。这题一样，这样刻画就行了。

Luogu P8173 [CEOI2021] Newspapers

服了。阴间分讨，阴间构造性思维。

首先有环不行，感觉是对的嘛。然后我们构造一个链的答案，这个我也不太会，反正就是 $2\sim n-1$ 再 $n-1\sim 2$。

接下来很神。考虑以链为本位，往外面挂点，发现挂的点深度超过 $2$ 就会无解，反正我构造不出来。

然后把直径取出来做一做就好了。

19

A 战队分配（team）

正负拆贡献，感觉挺灵机一动的。

B 货车运输（cargo）

容易想到钦定一个有序。另一个，我们关注前面还有几位没填和目前总和，即得 DP。

C 甜果（sugar）

转概率。看起来是内向基环树，但把确定的点拎出来发现只是剖成几棵树。对于一个深度的答案是确定的，注意不能瞎猜，打个表就好了。

*D 打平就能出线！（qualify）

什么？二分、分类讨论，想必是 T1 难度吧！什么？怎么赛时最高分 10 分？

Luogu P6105 [Ynoi2010] y-fast trie

原来的想法可以，就是把 $<C$ 和 $\ge C$ 的分开来讨论，然后对一个点 $x$ 同时在 $C-1-x$ 的位置记录，然后就是一个可以合并的东西。卡空间，所以平衡树。卡常，所以不可以无旋 Treap，Splay 直接过了。

20

喜欢 ty round，每次都有濒死的感受。

A 迷宫（maze）

大家好，我们卡常。

有 $O(nmk)$ 做法，但不想恶心自己。

B 玩具(toy)

比 T1 简单。从左往右，每种移动都是贪心做最远。

C 权重(weight)

点分治/dsu on tree，用 01-Trie 统计。清空不用递归，直接赋总和与根为空！

D 周长(perimeter) / ARC063F すぬけ君の塗り絵 2

分治是好想的，单调栈，同时搞搞区间加全局查最值。但是我们发现除去显然的下界，答案必然过横竖两条中线之一……妈呀……

现在是任何数据结构都可以干掉我了。我完了。

Luogu P8866 [NOIP2022] 喵了个喵

昨晚做到今天。

$k=2n-2$ 早就会了。对于多出来的一个，你可以考虑一些灵活一点的方法，连带后面的内容一起考虑进来。假设我们放到空栈，接下来一定要有新的空栈，就是一个在栈底的，它的上面被消了。如果下一个在栈底的不能被顶消，就干脆把当前放到它上面，然后底消。（自己做的时候多讨论了次数是否为 $0$ 的 case，但是不用，因为偶数次都会自己抵消，借鉴了 HF zzh 老师才知道。）代码细节很多，我写了一个结构维护所有栈的信息，然后用 extract() 和 append() 来临时取走/加入某个栈，用 push() 和 eliminate() 做顶消和底消。但是这个东西不能和 bel[] 同时维护，所以很细。

21

拜谢原创题领域大神 yukimianyan。

A Soso 的期望并查集（exsodsu）

（带权）并查集模拟，使用期望的线性性。

B Soso 的模法矩阵（modmat）

变进制数模板题。或者根据模数的倍数关系想到。

C Soso 的排列（soperme）

排列是变进制数，所以考虑数位 DP，逐位跳，从低到高位再从高到低位。

D 走路（walk）/ QOJ 8557 Goldberg Machine

不带修：P7831。知道了欧拉环游序的结论，对每个点都有一个时间戳，单次修改是区间时间戳 $\pm 1$，然后查询可以二分，分块做到 $O(n\sqrt{n\log n})$，注意到块内值域较小。

被 VJudge 猜结论虐杀了。

QOJ 9453 Graph Generator

倒着想，正着做。

QOJ 7866 / Gym 104891J Teleportation

关键是想到交换一二操作顺序，注意到第一步必走的细节。

QOJ 9135 Teleports

区间 DP，同层做最短路。

22

Codeforces 1458D Flip and Reverse

这能独立做出来是没想到的。把每个数换成 $-1$ 的次幂，发现这个操作刚好是这样折线图的 reverse。一次 reverse 中边的种类不变，只在乎后面还是否存在，要逐位贪心，认为找一条欧拉路径即可。

这里以上是独立解答。

QOJ 7861 / Gym 104891E Inverse Topological Sort

发现关键是最后一个卡脖子的数，认为这样子拼起来的图可以就是可以，不行就是无解。注意 check 同时检查最大最小序列是否相同……

QOJ 9246 Dominating Point

这个手玩没想到，就是假设 $p$ 两步内到不了 $q$，则 $\forall x, p\to x\implies q\to x$，这是一个非常好的性质，然后就可以按出度排序做。

QOJ 8517 Interesting Paths

这个好题。考虑把贡献只记在一条边上，就会有一些边不给算，发现你从 $1$ 开始搞一棵不到达 $n$ 的生成树即可，所以答案只和 $n,m$ 有关，注意把 $1$ 不可达或不可达 $n$ 的删掉。

QOJ 9141 Array Spread

这个是神题。处理分数除了设数、斜率以外的方法：钦定最小值为 $1$，最大值不超过此值。二分，可以有理数逼近，也可以发现分母分子不超过连续段个数，然后直接在 Farey 序列上二分。

Codeforces 1290D Coffee Varieties (hard version)

我们发现 $k$ 为块长是不可以的，所以选取 $\frac{k}{2}$……

剩下的就是考虑每次处理一对很浪费，考虑做最小链覆盖，一个好的写法是做成欧拉回路。

23

NOIP 模拟

A 旅游高手（expert）/ Luogu P9373 「DROI」Round 2 构造与取模

小数模大数值不变。

B 桜树街道（sakura）

树上笛卡尔树。

C 朱雀湖（lake）/ QOJ 8211 Enumerating Substrings

一点也不简单的计数。

发现模式串 border 至多有 1 个，所以可以容斥。系数是：

$$f_i=\begin{cases}0, &i\le 0;\\ i-\sum_{i-k< j< i}f_j, &i> 0;\end{cases}$$

得到 $f_i=\lceil \frac{i}{k} \rceil$。

注意模式串的总数不是随便填，所以算无 border 的时候容斥要留意。

*D 小情侣（lovers）/ Luogu P5211 [ZJOI2017] 字符串

Significant Suffix 板子题。关键结论：$\forall A,B\in \textrm{SS}, |A|<|B|\implies A\in \textrm{border}(B)\land 2|A|<|B|$。哈希用 $O(\sqrt N)-O(1)$。

Codeforces 2039 CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)

A Shohag Loves Mod

输出值域是长度的两倍，考虑 $2i-1$。

B Shohag Loves Strings

发现我们更关心字符是否重复。越短的字符串似乎更容易找，手玩一下，发现 aa 和 abc 两种就可以覆盖所有可能的情况了。

C1 Shohag Loves XOR (Easy Version)

要求 $x\oplus y\le \lfloor\frac{\min(x,y)}{2}\rfloor$，所以枚举一下 $y\le\min (m,2x)$。

C2 Shohag Loves XOR (Hard Version)

喜欢恶心人。

枚举 $x\oplus y$，逐个 check。根据 $x-y\le x\oplus y\le x+y$ 发现 $x\oplus y$ 较小的时候总是满足，不一定满足的在一个区间，枚举。注意判定的条件！！！！！不能两种都算上了，手动讨论一下。

D Shohag Loves GCD

从倍数关系必须满足入手，最容易不为 $\gcd$ 的办法就是比它们都大，毕竟还要字典序最大，发现这时已构造完了。

E Shohag Loves Inversions

从第一次出现逆序对数 $\ge 2$ 开始，如果不插在末尾，逆序对数就会单调递增。而这之前都是 01 串，手动模拟一下。枚举第一次逆序对数 $\ge 2$ 情景的时间。出现注意末尾多次插入的情况！

F1 Shohag Loves Counting (Easy Version) / F2 Shohag Loves Counting (Hard Version)

莫反好题啊！另写题解。11.25 完成补题。

*G Shohag Loves Pebae

没看，不会。

*H1 Cool Swap Walk (Easy Version) / H2 Cool Swap Walk (Hard Version)

感觉不好写，但是看起来很炫酷。

赛时只注意到是边界有交的一些 reverse，然后感觉很麻烦。但是完全可以把 reverse 更严格，是因为我们发现每次都会把第一个移到最后，而剩余的是边界无交的，所以可以干脆做成是否邻项交换。然后我们使用奇偶排序，这我哪会啊。就是第一次交换 12、34……，第二次交换 23、45……，再下一次又是 12、34……，太深奥了。这样可以 H1。

H2 就要求折半，因为上面这个东西是提前钦定 $a_1$ 最小，每次还要复位，所以很低效。所以考虑干脆就着这样做，让这个排列就一直做轮换。认为小于半数的是 A 类，大于等于的是 B 类，在前一半只排 A 类，后一半只排 B 类。还有很多细节，暂且投降。

25

Luogu P5610 [Ynoi2013] 大学 / P3987 我永远喜欢珂朵莉~

暴力除的次数很少，注意是不考虑除以 $1$ 的情况！！！（写之前先留意一下自己的结论对不对。于是可以干脆不记录这个因数。）考虑对每个 $x$ 维护它的所有倍数然后二分查找。发现很难做删掉因子，所以惰性删除！！！

一个关键卡常：链式前向星寻址过于底效，摊平的时候不可以逐条链访问！对每位记录一个 bel[]。

还有一个：并查集的 find() 虽然是递归，但是写 inline 会快很多。

26

A 珠子（bead）

欧拉反演。

B 机器人（robot）

换成两个函数的差，然后分奇偶，离散化，差分前缀和。

C 树（tree）

赛时做不出来，太幽默了。

部分分提示拆项，DP 状态是闲置黑点数和闲置白点数。有三类，每个点先把儿子都跑完再做。

*D 钻石岛（island）

大致思路：考虑底面只有 6 种状态，画一下发现类似于走一个欧拉回路/路径，一条边来回走可以刻画一下，最后拆两维解同余不定方程，整一整，嗯。

27

会做 0 道计数题，那我完蛋了。

*QOJ 5367 递增树列

观察不难，树上二维卷积还有抽象组合数，我该怎么办？？？

*QOJ 9650 链覆盖

EGF。我该怎么办？？？

*QOJ 9561 树数叔术

观察不到，我该怎么办？？？

记录一下这个观察：0 肯定只有一个。1 手模一下发现也不得不只有一个。这时候手模多一个！发现 2 可以在 0 到 1 路径上任意放，在其他地方最多放一个。所以结论是这样的：每个数至少有一个，在比他小的虚树上可以随便放，在外面最多放一个。

然后咋写啊？？？

28

A 冒泡（pop）

手玩得到结论。喜报：n >> 1 | 1 不等于 (n >> 1) + 1。

B 山路 (road)

找最短路和不同色的次短路。也可以理解为最段路树上对于跨越两棵根的子树的横叉边计算贡献。

C 机器 (machine)

感觉是好题。赛时所有必要的观察都做了，但是没想到 DP，真是无语。

以 B 为本位考虑，希望尽量多地做 RRB，如果不巧不得不做 RBB 就会 $+1$ 花费，如果要做奇偶切换就不得不做一次 RB。也就是可以刻画一个方案的花费了。另一个很有用、也可以给出 DP 提示的「有序性」条件是：以终点奇偶性分组，每组内部的起点有序。这个显然。然后我们可以 DP！！！$f_{i,j}$ 表示偶数/奇数分别匹配了多少个，最小花费。构造方案有点麻烦，有两种较为简易的解决办法，但注意麻烦之处都是碰到了起点终点相同的状况。第一种办法让终点代替起点先走，然后起点再代替终点，这是等效的；另一种办法是如果有奇偶转换把它最先做，这样根据有序性以后都不会遇到这种情况。

Luogu P9527 [JOISC2022] 洒水器

拆邻域技巧。

D 旅行 (tour)

用这个办法，树剖线段树是显然的，每个点上的 tag 种类数非常少，就可以在线了。

29

Luogu P3750 [六省联考 2017] 分手是祝愿

首先发现一下结果和过程是双射，复原，然后推式子，用差分处理。

Luogu P9968 [THUPC 2024 初赛] 二进制

用链表和一些可删堆模拟，每次只考虑同一长度就很快。记得数组要够大，满 2 的次幂。

Luogu P3426 [POI2005] SZA-Template

从 fail 树上考虑：是 $n$ 的祖先，且子树内相邻数差最大不超过自己。

感觉，这种归纳方式很没有道理，不适合复习。