题解 - 2024 九月做题记录

18

Cplus。

• A：分析（猜）性质，分类讨论，计数，容斥。（明明可以 DP 却写了二项式反演。）
• B：乱搞：二分、有理数逼近。正解：扫描线思想，在连续域上 DP：折线维护、凸包。记得处理“空”的情况。
• *C：线段树分治，太高了。

19

SWERC 2016（QOJ Contest 406/Codeforces Gym 101174），with 深海狂鲨 & yukimianyan. 9 题，余 IJ 未场切。

A Within Arm’s Reach

写了笨蛋的模拟退火。

• 不要偷懒写差分数组，写绝对角度。
• 做修改时正负都要做。

正解是发现两条臂可以解决很多状态，然后在对应的线段上二分，拿三角函数解出来就可以了。

B Briding Eve

把每个点化成一次函数，找交点，分类讨论后离散化，做前缀加或后缀加，然后求全局最值。

E Passwords

AC 自动机 DP 套路题。注意不要想当然地用差分统计……

F Performance Review

写了愚蠢的启发式合并。其实结合 dfs 序二维数点一下就可以了。

G Cairo Corridor

队友写了线段树分治，来生成每个点被删的所有情况。事实上似乎可以缩二度点，然后讨论：

• 只有至多 $4$ 个点度数为 $1$。
• 只有至多 $6$ 个点度数不小于 $3$。（？？？）

I The White Rabbit Pocket Watch

高斯消元后直接最短路即可。之所以没做出来是忽略了：“you’ll be able to find how long it takes you.”要读题。

J Risky Lottery

抽象迭代思维。

发现最终状态下，选每一个数字能赢的概率相同。否则，就有一个人可以改进自己的策略了（赌最大的概率）。

所以考虑迭代。每次算出每个数字能赢的概率，如果高于平均数就把选择它的概率调高，否则调低。

可是为啥退火跑不出来？不太懂。但是这个迭代……真是服了。

dfs 得写快点，不然跑不动。

*C, D, H, K

听说不难，不看了。

Codeforces 1762D GCD Queries

直接考虑 $n=3$ 的情景。

20

Codeforces 1416E Split

扫描线 DP。DP 和 set 维护区间集有代码细节，留意负域。

Luogu P7831 [CCO2021] Travelling Merchant

以终为始，从大到小转移。高妙图论。

Luogu P1587 [NOI2016] 循环之美

有序化简莫反，杜教筛。找到递归关系。一题多解哦。

21

ZR NOIP 10 连 day 4。

A 朔望

可以 unsigned long long 高精度。但是乘积的模等于模的乘积的模。

B 随机

欧拉回路构造。好像可以找规律。

C 游走

简单数数。树边要开两倍！！！。

*D 网络

结论是：重心必然在 dfs 序的中心往上跳的路径上（带权就是带权中心）。其实就是发现向下跳会做，但是不好维护，所以觉得在树上就应该向上跳。但是 dfs 序应用太神秘。

然后想要查询联通块内每个点到定点的距离。这里用容斥的想法，是全部点到它的距离减去联通块以外的到它的距离，然后子树内的逐个处理有可接受的均摊。

怎么线段树分治 $\log^2$ 跑不过 $2\times 10^5$ 呢？

QOJ 8781 Element-Wise Comparison

非常高妙的 bitset 使用。考虑拆解条件，发现是若干个条件的与，然后找到相同的下标，在题意下可以做不带删双指针（即尺取）。

22

ARC 184。

A Appraiser

交互。提取“相同”的优势。

*B, C, D, E

全部不会。菜。B 是：状压 DP，但是赛场上失败，以为可以构造呢。

23

Cplus。A：单元答案使用二分，但是可以暴力枚举；B：简单数概率，但是不要想当然暴力；C：晦涩的贪心使用，构造，小心正负边界；D：线段树题，不要忘记 $-1$。

Luogu P3266 [JLOI2015] 骗我呢

关键是注意到格路计数。看到范围扭曲的简单 DP 式考虑。然后反射容斥，记得输入不要写反。

Luogu P5068 [Ynoi2015] 我回来了

调和级数暴力，主客转换，对线段树每个节点做一个 vector 作为 tag。写了快读要用。

Luogu P4690 [Ynoi2016] 镜中的昆虫

元素种类数转 (pre[i],i) 的数点。CDQ 分治。读好题目范围，不要写着 $10^9$ 开了 $10^5$。

Codeforces 1458E Nim Shortcuts / 1866I Imagination Castle

模拟 DP/nim 游戏。好诡异的 set 使用。

另外的规划：发现很多时候主要是计数（包括动态规划）、数据结构和树会出的比较难，所以主要是这两个方面。字符串，不好说会不会考，但要做几个题。至于写挂的情况，感觉是大脑要清楚，逻辑要完整，然后可以自信点放松点，找找状态看吧。蔡队是补题怪物吧……

24

Zhengrui，省选难度，严重挂分，被 T2 拖后腿。

A 1410 超简单题

子序列自动机，DAG 上类重剖。

记得开 long long！！

B 1411 更简单题

读题（这题面并不好）。发现想要做很多次循环卷积（那就老老实实尝试去做啊），既然浮点数：猜测概率会越来越均匀（或分块），减免操作。

能写 TLE 不要写没有道理的 WA，比如省去高次项。阴间题不能太耗时间。

C 1412 最简单题

猜测结论/化简条件，拟阵贪心（其实就是感觉它非常贪心，然后看能不能类最小生成树算法）。

贪心学艺不精。好题好题，可看可看。

Codeforces 1987E Wonderful Tree

简单题。贪心，递推。

Codeforces 1548B Integers Have Friends

尺取记得清空问题。（也可以 Sparse Table 二分。）

Codeforces 1495E Qingshan and Daniel

很有意思的如简单题。分析性质，发现有一边会全部死掉，然后顺下来一个一个耗即可。

25

Cplus，也是 Becoder 公益赛，NOIP 难度，T3 想挂了，没对拍但稳定性尚可，所以可能要经常打比赛才有感觉。

A 多线并行（multi）

简明的贪心。

B 空当接球（ball）/ QOJ 1963 Squid Game 大力加强

非常神秘的构造题，好题好题。致敬喵了个喵。

首先由奇偶性想到二进制，想要把最低位往上推，但是这样要做非常多次（$O(n\log nm)$）。感觉非常宽松，然后由二进制要想到 01 Trie！加（减）运算由低到高位的 01 Trie 维护，然后做一点自底向上的贪心最低匹配（AGC018F）。然后就对了，嗯嗯（你发现势能增长飞快，复杂度几乎线性）。

然后发现化简完后还不够小，不能满足题目条件，还有 $O(\log nm)$ 个数，超过了 $2$ 个。所以必须跳出二进制的框架。考虑把最小值一直变小（怎么想到的？），能稳定实现这个的运算是模运算，所以尝试构造一下模运算的写法，那就非常好了。

C 列序号括（bracket）

冷知识，两只 $\log$ 可以通过 $10^6$，跑得也很快。好的好的。

题解做法：既然是括号序列题，一般从内括号到外括号有单调的决策，所以发现外括号删里面必全删。以为从括号序列变为树，结果发现就是要在序列上面做（？）。从后往前，倍增维护。

其实，用树分析到单调栈的结构就可以倒着做，尝试加入大还是不加入大，更为简易呢。但是要讨论最后没有不合法右括号的后缀，容易想挂。

D 可爱路径（path）/ QOJ 5034 >.<

最短路套 AC 自动机。但是发现一个出边会被走很多次，所以发现其实不用走很多次：就是有一些边大家都会走，发现大家都会走的边就是不考虑其他前缀后走的边，然后这些边只走一遍就可以了。大概分析一下，发现怎么写都是对的，吧（就是，你即便以后的支线有效边都不要也没关系，反正边长不变）。非常好的优化思维。

Kilonova 2797 Triunghi

等腰直角三角形转分治，对这种类滑动窗口但是不好删的询问做一下尺取。

如果不要 $\log$，按照 $k\times k$ 分成矩阵块，所谓“关键点”，然后针对斜线预处理就可以，感觉精细的。

26

Zhengrui，毛营，打得不太舒服。B 题在结束前 5min 发现读错题，说明做打比赛程序上还是要先把题目都仔细看一遍。

A Easy Win

用 SG 函数把要求的转化为 $\oplus (a_i \bmod x)$，转成 $a_i-x\lfloor\frac{a_i}{x}\rfloor$，猜想调和计数枚举每个区间，至此都是简单的。

想要做区间查询 $a_i-x$ 的异或和。并不好做，所以由 $\oplus$ 想到每位的独立性，逐位枚举。观察在值域线段上，对于一个 $x$，$y-x$ 在第 $d$ 位上的分布是以 $2^d$ 为周期的纹路，所以可以用这种纹路做前缀和，然后特殊地处理边界。实在是想象学。

B Cells Blocking

无路可走，首先猜想和割点有关。接下来的步骤就比较想象学。顺便有一个基本原则：从左上到右下的路径长为 $n+m-1$。

考虑极左下和极右上的两条路径（下文命名为 $L$ 和 $R$），可以发现所有可能的路径都被夹在中间。所以割点是这两条路的交。要割两个点。首先至少有一个在 $L$ 上（其实对任意一条合法路径都符合，但是这么钦定比较方便找另一个点），枚举这一个，命名为 $P$。$P$ 为割点的情况简易处理，只讨论 $P$ 非割点。然后在新图找新的 $L$（$R$ 是没变），然后继续做割一个点的情形。现在的焦点来到如何快速找到新的 $L$ 和 $R$ 的交。

既然 $P$ 被 ban，当走到 $P$ 的这个步数，就要走到另一个合法的点 $P'$，其余的都没有关系。处理出对于每个点作为 $P'$ 时的答案，然后就只要找出 $P'$ 即可。既然是第二左下，那就刚好是同步数的斜线上 $P$ 的后继。

C Giant Penguin

当换根、深度这些要素感觉到，就要考虑点分治，这个没啥问题。（感觉英文译名更符合其实质呢，centroid decomposition。）

对于非树边，强行把与之相关的 $k$ 个点拎出来（取任意一端即可），这样子如果要跨越子树，要么经过重心，要么经过特殊点。

预处理就是把特殊点和重心拿出来都跑 BFS。带修就是上点分树在特殊点和重心上更新。

魔改点分治。实质是：把图剖成几个子图，把跨越的拎出来（好像更像猫树分治），发现总是经过有限个关键点。

写代码上，一个是不要写错求重心，一个是可以多用给子树染色的办法判定对面的点是否在当前子树内，防止奇怪的事情发生。

27

Luogu P3295 [SCOI2016] 萌萌哒

神题。

并查集是容易想到的。直接逐位合并并查集复杂度很高，但是询问次数却很少。所以考虑把大区间拆成一些子区间的与，最后要回答询问时再集体 pushdown。这里其实用 Sparse Table 即可，线段树不好做。那也有另外一个视角就是用倍增理解这个过程。

ZR 2925 逆序对(inversion)

非常好 Bijection Proof。

写了题解。

28

Cplus 联测。

A a

题目名字就是这个，我能怎么办。

手推，感觉到有简单规律，做完。

B b

模拟 DP，发现变化量不大。注意 -INF。

*C c / Codeforces 407D Largest Submatrix 3

看到矩形，三次方复杂度，想到枚举三条边。然后就有大力递推，就是从三维的邻项推过来（但是可以非常牛地压到只有两维数组）。（？？？妈呀。可能就是，你感觉东西非常多，不容易直接算，而且可复用，所以想要递推。）

但是我们三次方数组被卡真是太厉害了。感觉是，有序枚举，要会。这不是我们，CSP-S 2022 T1？怎么我现在不会这种题。

C 可能小于 B，呃呃。

D d / ARC118E Avoid Permutations

对于严格的“一个都没有”限制，考虑容斥。大小为 $n$ 的子集系数为 $(-1)^{n}$，在 DP 中做这个转移。

我们容斥。

写了题解。

29

Cplus 省选难度，打的很顺利。

AGC 068，一道题都不会。

A 铲雪

我们 $998244353$ 能做 NTT 模数，性质太好了。费马小定理，然后直接线段树和树状数组维护。

B 抽卡

DP，关于状态的互推：迭代 60 次即可。不过精准高效的做法是按值域分段，然后解方程。

C 樟 / Aizu 2993 Invariant Tree

非常好 prufer 序列数数。

写了题解。

30

Cplus 联测，打得不太好。

A 人机识别（iamhuman）

简单构造，由 $\log$ 函数的凸性即可。还没想更深入的思考，关于出现循环的字符串。

*B 字符画（picture）

灵感大王图形构造。对于 $n=300$ 要特殊的图形。

*C 能量（energy）

还未仔细研究，大体是维护 DP，寻找凸性。

*D 最小生成树（mst）

从最小生成树到 Kruskal 重构树，在其上动态 DP 即可。这个东西可以被认为是树的“等效链”。