23赛季刷题记录

数据统计

总题数	独立解数	独立解率	1a 数	1a 率
32	16	50%	11	34.4%

2023/09/15

• ICPC2022 南京 E

vp 之后补的题，没有 1a 而且 wa 了一万发。

解锁虚数知识点，主要思想其实就是：根据关键点所建的虚数尺寸为 $O(\text{关键点的数量})$，所以如果关键点不多或者加起来不多（比如这题，每次处理 1 层，那么关键点总数就是 $O(n)$ 的），就可以每次根据关键点建虚树再 DP，这样就可以减少每次 DP 的规模，即把本来没必要参与 DP 的点去掉了。

2023/09/19

• （例题）洛谷2522 [HAOI2011] Problem b

题解提示了，没有 1a。

经典老题，没啥好说的，主要是 $\epsilon(gcd(i,j))=\sum_{d|gcd(i,j)}\mu(d)$ 的转化，以及在有 $\sum_{d|gcd(i,j)}$ 的和式时把 $d$ 换到外面，然后对 $i'=i/d$ 和 $j'=j/d$ 求和，这样就可能简化计算。

这题还用到二维数论分块：j=min(n/(n/i),m/(m/i))。

• （例题）洛谷1829 【国家集训队】 Crash的数字表格

题解提示了，没有 1a。

也是经典题了，和上面差不多的思路，关键在于推出两个二维和式后注意到这俩都可以数论分块快速做，然后对比数据范围发现数论分块可过，就这样做。

• （例题）洛谷P3806 【模板】 点分治1

板子题，通过这道题学习了点分治。

点分治的主要功能，用 oiwiki 的话说：“处理大规模的树上路径”，我觉得这个总结非常准确。

点分治其实本质上和序列分治一样的，都是考虑 1. 子树内部的路径 2. 子树每个点到根的路径 3. 子树之间相互的路径，因此处理过程和序列分治也非常像。首先是划分字问题：处理一个子树内部的路径，然后子树内部任意一个位置都可以成为根，因此我们选择树的重心，来使子问题规模缩减的最快，最后只需统计不同子问题之间的贡献就可以得到所有答案。

点分治复杂度正确的关键在于：每个子问题的复杂度是子树大小，每往下分一层，树上所有点都会被访问到一遍，虽然这个操作是 $O(n)$ 的，但由于选的是树的重心，所以至多 log 层后子问题规模就变为 1，因此复杂度总共是 $O(nlogn)$ 的。

• （例题）[SDOI2015]约数个数和

看题解了，1a 了。

关键在于约数个数函数的性质：$d(i\cdot j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$。之后推公式容易，还是经典换顺序

2023/09/20

• （例题）洛谷2664 树上游戏

没看题解！1a 了！

这题还是分治的思路，划分子问题。难点就在于统计子树之间的贡献上。研究答案算式，发现题目求的是每条路径上颜色数的和，那么转而可以转化为统计每个颜色在哪些路径上，有 1 点颜色就产生 1 点贡献，即求和转贡献的思路。

使用一个技巧：把每个颜色分开考虑贡献，顺带还可以顺带注意到一个性质：点到根的路径“有没有一个颜色”这个属性具有截断性，即某个点到根有某个颜色了，那么它的子树都有这个颜色。

于是从上往下遍历，当一个点第一次出现某个颜色时，就可以认为它的子树对子问题中的其他子树都产生了这个子树大小的贡献。但是这样还不太准确，因为其他子树中的点在来的路上可能也出现这个颜色了。但是又注意到对于接受贡献的点，如果它到根的路径中有某个颜色，那么这个颜色对它的贡献就是其他子树的总大小。即如果已经有这个颜色了，那么甭管其他子树是啥样，每人都产生一点贡献。这样就可以在统计答案时设置一个修正值，如果出现了颜色 a，就把其他子树对这个点的总贡献减去其中颜色 a 产生的贡献，再加上其他子树的总大小，就可以修订出当前点获得的准确贡献。

这题还有一个点分治统计子树之间贡献的技巧：设置 dfs2 是贡献函数，dfs3 是统计函数，那么先每个子树 dfs2 一遍求出总贡献，接下来每个子树接受贡献前，先 dfs2 自己的负贡献，然后 dfs3 统计答案，再 dfs2 贡献回去。最后别忘了每个子树再 dfs2 负贡献一遍擦干净屁股走人。

独立做完这道题，感觉就可以说点分治的基本思路被我掌握了。

• （例题）洛谷4213【模板】杜教筛（Sum）

没看题解，没有 1a。

杜教筛板子题，求和 $\mu$ 和 $\phi$ 函数的杜教筛形式都简单的一比，看上去非常炫酷，但是也有两点需要注意的地方：1. 虽然杜教筛复杂度很酷，但是因为用到 map，最好还是先 $O(n)$ 预处理一下，否则卡时间（前面 n 个点访问最密集，map 的 log 复杂度全乘上去了，后面的稀疏一些反而不 care）。2. 易错点！当 n 顶到 int 上限的时候，数论分块会爆 int。由此可见测大数据还是很重要呀，尤其是大数据很容易测的情况下！

2023/09/21

• （例题）洛谷2495 [SDOI2011] 消耗战

没看题解，1a 了。

虚数例题，这个题的一次查询版本还是非常好想的，就是注意虚数上的边权应该是原树路径边权最小值而不是边权和。但实际上这题没必要专门写个树剖求路径最小权，直接拿点到根节点的最小边权其实也是对的（不难想象）。

虚数易错点：

1. vector 去重是 q.resize(distance(q.begin(),unique(q.begin(),q.end())));，注意要 resize。
2. 别忘了把根节点加进去。
3. 用 vector 的话下标从 0 开始，建树的时候别写错了。
4. lca 不要手抖写成 dp[acc[x][i]]>=y，本次写题的真实错误。
5. 根节点的深度必须是 1 不能是 0，否则 lca 会出错，本次写题的真实错误。

可见 lca 还是有点容易写错的，考试时还是抄板子最好。

2023/09/25

• （例题）洛谷4719 【模板】“动态 DP”&动态树分治

看题解了，没有 1a，写了 2 天。

动态 dp 板子题，主要是带修改的树 dp。其实就是首先把 dp 方程写成满足结合律的矩阵乘形式，然后用树剖去维护这个矩阵乘

细节比较多，如本题中 f 函数在求出 g 函数后就没用了，顶点到它所在重链的另一端的 g 矩阵之积就直接是顶点子树的答案，这里应该是应该是顶点到另一端点之积，而不是顶点到 x 之积，容易写错。因此建议抄板子。

以及树剖也容易写错，这次我没复习靠自己理解写的树剖，就犯了先求 dfn 序列再求重儿子的错误，也是建议抄板子。

2023/09/26

• （例题）LOJ2955 「NOIP2018」保卫王国

没看题解，1a 了。

和上一道题基本上一样，状态转移方程的结构都是类似的，也是能写成矩阵乘的形式。核心思路还是维护一个不考虑重儿子的最优答案 g，然后重儿子那部分交给树剖矩阵乘处理。剩下的代码都没什么区别。

做完这道题应该动态 dp 就算了解了，而且树剖又熟悉起来了。

2023/09/27

• （例题）洛谷 [POI2014] HOT-Hotels 加强版

看题解了，没 1a，甚至是对着题解代码改的囧。

这题上头了做到 2 点多，所以严格意义上来讲应该是 28 号完成的（笑）。

长链剖分的原理倒是理解了，最开始想了一个做法，以为自己是对的，其实看了题解研究了半天才发现漏了 $(a,b)\to lca(a,b)\to u\to c$ 的情况，其中 $depth(c)>depth(u)$，也就是 a 和 b 合并后先往上走，半路再往下拐的情况。

这种时候就必须用 g 数组来辅助了，这种情况下其实 $a,b$ 到 $lca(a,b)$ 的距离比较长，设为 $x$，$lca(a,b)$ 到 $u$ 设为 $y$，$u\to c$ 设为 $z$，这时候就有 $z+y=u$。巧妙的来了，可以从差值的角度考虑，设 g[i][j] 表示 $lca(a,b)$ 到 $i$ 的距离还差 $j$ 才能和 $lca(a,b)$ 到 $a,b$ 的距离相等。这样就可以做 dp 了。然后其实发现另外两种情况可以转化为 $lca(a,b)=u$ 和 $u=c$ 的情况，所以统一用这种情况考虑就行。

细节：

1. f 数组深度越低地址越靠前，g 数组深度越低越靠后，因为每次 f 数组自动往前补，而 g 数组其实应该自动往后补。
2. 因为 g 数组在最后地址，而 g[i][j] 中的 j 又最大是 i 的链长，所以 g 数组要开两倍。
3. 统计答案中有一条是 g[x][0]，这其实是三角星形状那个情况，$j=0$ 就表示不需要补差值，也就是 $i,a,b$ 已经满足条件了。注意这里 j 的意义是差值！
4. 遇到 +1, -1 不好决定的情况，别忘了用特殊实验法，效率很高。

长链剖分倒是整会了，但是这道题还不是很明白，比较考验 dp 功底，最好是过几天自己再来独立做一次。

2023/09/30

• 洛谷3899 [湖南集训] 谈笑风生

没看题解，没 1a。

也是长链剖分例题，$O(n)$ 维护深度信息，dp 部分不难，很快就想出来并写完了。但是 RE 了一个小时！最后自拍发现原因！：

dp[x]=dp[y]+1 写成了 dp[x]=y+1。

果然早上写题脑子不是很清醒，另外写题的时候不能急否则很容易写岔，另外以后要注意某个疑似有问题的点反复看不出问题的时候，就要把整个代码每个角落看一遍，看看是不是其他哪些奇怪的地方出了问题，这种事情已经发生过两次了。

2023/10/01

• （例题）LOJ105 文艺平衡树

没看题解，1a 了。

Splay 比较弱的例题，仅包含区间翻转操作，可以练 splay 相关操作（旋转、splay、split），但是有关序列操作设计的不多，其实还是维修序列更适合做板子题。

虽然是简单题，但是细节也是不少的。长度 n 的序列需要 $n+2$ 个点，主要是起始和结尾添加两个点，方便 split 操作；既然加了两个点，那 split 的两个点就得是 $l$ 和 $r+2$；打翻转标记的时候是异或 1 而不是等于 1 等。所以还是最好抄板子不要自己发明。

2023/10/02

• 洛谷2042 [NOI2005] 维修数列

没看题解，没有 1a。

Splay 正统板子题，细节比较多但是其实没有觉得多难写。可能码力还是进步了。不过有一些细节需要注意，一个是不用开 long long，因为数最大只有 1e3，而我这个写法没有回收点开 ll 会 MEL。另一个是 max_0 的值要设为 $-\inf$，这样当儿子不存在时会默认使用 $-\inf$ 更新最大字段和。如果不用 $-\inf$ 更新，就相当于可以选空序列，而这道题不允许选空序列，这个点是看了讨论区的提醒才注意到。

虽然没有看题解，但是看了讨论区的提示，而且基本上参考以前的板子来写的。其实 ACM 抄板子倒也正常，但研究生了还在考古高中的遗产学习，有点逗 233。

另外最近知识点学的很多，感觉身上一股 OI 味，不一定是好事，也许应该做做 cf。

• （例题）洛谷3690 【模板】动态树（LCT）

没看题解，没有 1a。

LCT 板子题，比想象中的好写，而且现在感觉也没有那么难理解，不知是不是网上资源更丰富导致学习更容易了。不过细节还是很多的，尤其是 update 的时机，不能漏。

2023/10/03

• （例题）洛谷3203 [HNOI2010] 弹飞绵羊

没看题解，没有 1a。

以前觉得很难以理解的题，现在随便秒掉了，很神奇。有个性质是每个人只会往一个方向飞，那把他飞过去的那个人看成他的爸爸，这不就是个树嘛。然后 lct 维护动态树，查一下每个人到最右点的距离就行了。这里有一个问题是 lct 的根会变，不能用深度求距离，那创建一个 $n+1$ 点，让所有被弹飞的点都弹到这里好了。然后就是 makeroot $n+1$，查询的点 access 到 $n+1$，splay 到根看链长度就 ok。

没 1a 一个是犯了把输入点标号写成 i 的蠢事，另一个是没看见题目里标号从 0 开始。这两点以后都要仔细检查呀。

2023/10/05

• 华科23新生赛

A，B，C。

一道 LCT 维护双联通分量的题做了两天做不出来，还从来没有过一个点，放弃治疗了来做一下土豆推荐的华科新生赛。

B 题垃圾！虽然我没看清“按照他的意愿重新组合拼接“是我的问题，但是这个题意仍然不清不楚的，有一万种可能性，做题全靠猜题意，想了半个多小时结果真实题意是个 naiive 题，大力点差评。

2023/10/06

• （例题）洛谷2542 [AHOI2005] 航线规划

看题解了，没有 1a。

做了三天总算把这题过了，大清早起来测了一组数据 debug 一下就过了=。=

主要是一开始想错了，就导致后面思路比较乱，整理一下思路重写一遍就好很多。

LCT 维护双联通分量主要是当出现环时就缩点，并查集维护缩点，由每个集合的代表元参与 LCT 的运算。这里的问题在于如何进行缩点。我最开始写的暴力缩点是不行的，复杂度不对正确性好像也有点问题。正确的做法应该是利用 LCT 认父不认子的灵活特点，首先拿出环上的点，dfs 一下将每个人的集合合并到这个环（链）在 LCT 对应的根上，并且把根的两个儿子切掉；然后要修改 access，在 access 的时候，每次不是往爸爸上跳，而是跳到爸爸的代表元上，这样相当于直接略过了中间被合并过的点。由于 LCT 上的操作基本都要先 access，即使 splay 之前也会先进行 access，因此这样就可保证合并过的点被跳过。

Access 修改为：fa[x]=top(fa[x]); x=fa[x];，注意不要写成 fa[x]=fa[top(x)];。

除此之外，这题值得注意的点还有：

1. 维护删环不好搞，但当只有删除没有增加的时候，就可想离线反序删除变添加，同样的思路在水管局长中也出现过。
2. 离线反序时注意，判断一下操作为删边时再去原图删边，别把询问操作的变也给删了。
3. 这题使用 map 当作邻接矩阵存图很方便。
4. 使用 set、map 等容器时慎用 erase 操作，因为可能一边 erase 删着，外面还在遍历着，这样就会导致外面的遍历出错。
5. 当使用并查集合并时，注意判断一下操作的两个数查询过代表元之后是否变相等。这题数据保证边存在所以代表元不会相等，但是其他题目可能出现操作的两个数在一个集合里的情况。
6. 每当在 LCT 外的地方修改 LCT 的儿子的时候，都要记得 update，这是一个检查点。

这题最后写下来代码还是挺简单的，一开始思路想错了导致很复杂。看来死磕学习不一定是好事啊，尤其在 ACM 的环境下，效率太低了。

2023/10/08

• 22 沈阳 vp

本场 vp 最大的问题是因为以为 cout<<endl; 的速度没有“如此的”慢导致在一道包含搜索的题目中卡了一万年，从而没有时间做 A 题。如果做掉 A 题就可以拿银牌（虽然根据补题结果来看 A 题 2 个消失之内估计是做不掉，囧）

2023/10/10

• ICPC2022 沈阳 A
  和西欧
  看题解了，没 1a。

这题可真难做，道理上没什么问题但是做的时候就是很烦人。推公式+前缀和优化，其实没什么好说的，需要注意的点：

1. 当所有区间都退化成点时，连续概率会退化成离散概率，不过这个问题样例提示了，比较良心。
2. 务必检查所有乘法！尤其是当运算操作比较多的时候，容易出现 n*m，i*a 这样的爆 int 情况。
3. a[i],b[j] 也是易错点，需要仔细检查。

另外针对不同情况写 3 个相似的代码也没什么丢人的，把情况孤立起来考虑可能会更容易，没必要强求复用代码。

这题做的我魔阴身要发作了，希望在现场赛不要碰到这种。

2023/10/15

• 22 杭州 vp

中规中矩的一场，因为 G 题没有想到 ababab 的情况痛失银牌。最后金牌题 I 题思路对了一半，后半部分 BSGS 没反应过来，对这个模型不熟。

2023/10/17

因为赶项目和科研任务空了好几天没练题 =。=

• ICPC2022 杭州 G

看题解了，没 1a。

数哈希板子题，最多有一个环的性质易发现，主要是环上 ababab（阿巴阿巴）的情况不易发现。写代码的时候要注意 ababa 也是不行的，只有偶数环能 ab 交错。

另外这道题写完发现我对数哈希的理解是错的，确实不能裸套多项式就完了，每个点合并到爸爸的时候必须做一下字节混淆。

2023/10/18

• ICPC2022 杭州 I

看题解了，没 1a（忘记删打表）。

非常有趣的一道题，我 vp 的时候想出前半段思路，也就是随机跑若干次找最大值，但是后面没想到。后面是这样的：先连续走 3333 个 1，获得一段连续的区间，然后再走一个之前的最大值，跑到这一段连续区间的比较靠前的位置，然后再走 3333 个 3333。这样，由于步长和区间长是一样的（这个很重要），那么就可以保证只要路过这段区间，一定至少有一次踩在区间里。把之前区间里的值存到 map 里，这时就可以发生碰撞，然后推导出步数了。由于还剩 3333 步可以用来前面的随机，所以随机出的最大值极大概率和区间长度的差值小于 $3333\times 3333$，这样就可以认为几乎能找到解了。

巧妙的题目，使我大脑旋转。

2023/10/22

• 22 绵阳 vp

偷懒场，有 3 个题有思路但是没有继续研究下去，提前撤退了。

2023/10/27

因为赶项目又好几天没做题，囧。

• CCPC2022 绵阳 D

看题解了，没有 1a。

场上就猜到三分的结论了，只不过没有仔细去证。其实猜个结论去做就对了。

但是如果直接在场上做，可能会自闭，因为补题的时候就自闭了。主要没有注意到这两个问题：

1. 如果两个人概率相等，必须把同概率的打包考虑。因为题目要求的是只要满足赔率大小关系，就会买进。如果不打包，就会存在只把一半人考虑在内，但是更优的情况，而这种情况显然是不应该的。
2. 1e6 组输入勿用 cin，会 T。

之前就因为 endl 卡时间了，这次居然输入多了还卡时间。再也不用 stdio。。。

• ICPC2023 拉丁美洲 J

没看题解，没有 1a。

淀粉质+权值线段树，用 pair 来维护有优先级的答案。算是比较裸的题，也想了一会。

没有 1a 的原因在于在求深度的 dfs 外写了 dp[x]=0，但是 dfs 进去第一句话就是 dp[x]=dp[y]+1，导致本来以为深度是变数，其实是点数。这个问题很易错，要特别注意。

2023/10/28

打 IEEE，没啥好记的，该做的都做了，不该做的也不会。就是感觉今年 IEEE 没啥意思，不好玩。

2023/11/01

又是赶组会的一天，挤时间做了点题。

• CCPC2021 女生赛 AB

A 题小模拟没啥好说的。

B 题没看题解，没有 1a。是倍增，自己想出来了，开心开心。就是有点偷懒，没好好测试和检查，其实本来可以 1a 的。

2023/11/02

• CCPC2021 女生赛 CDG

看题解了，没有 1a。

两道无聊签到题，C 题智商被爆了，没想到出现超过两次的数最多只有一半，真是爆智商了。

类似的还有超过和的一半的数只能有一个，以及土豆说的，n=1e6，每个ai的贡献之和ai的值有关（我怀疑他想说出现次数），那么ai最多只有根号n个值（出现次数应该）。

2023/11/03

• HAOI2012 高速公路

没看题解，1a 了。

披着期望外壳的线段树题，发现最终答案可以通过两区间合并后，维护 4 个值然后各种计算就完了。查询的时候合并答案。80 分钟做完，这个速度稍慢但是 1a 了，感觉整体还可以，说明我线段树用的及格了。

2023/11/04

• 22 威海 vp

一个全场都过的傻逼题卡全程。最后居然是找规律，其实已经发现循环节了，但是还隔那死看公式，没反应过来 x 不大直接暴力求就行了。暴力精神贯彻不到底啊。

剩下题做的还可以，一道贪心+二分，一道思维，都想出来了。

有一个计算几何摆烂了没碰，考场上应该能搞出，搞出这个就银了。

2023/11/05

• CCPC2022 威海 G

看题解了，1a 了。

异或和 gcd 搁一块，给我干蒙了。但是其实打表找规律，发现 gcd 的值是有循环节的。这时要注意到循环节里的规律是无所谓的，因为循环节不长，直接节内暴力求就行！

• CCPC2022 威海 C

没看题解，没 1a。

计算几何+分类讨论，没啥好说的。

犯了一个细节错误：向量开成 int 类型了，直接爆。然后思考上也不是很仔细。不喜欢这题。

• CCPC2022 威海 D

没看题解，1a 了。

非常裸的状压 bfs，意识到这题只有 $2^{19}$ 个状态的时候就已经结束了。

2023/11/06

• （例题）洛谷4238 【模板】多项式乘法逆

多项式练手题，抄板子。

• CCPC2021 女生赛 F

看题解了，没有 1a。

因为一开始没用字符串哈希的 O(1) 求字串，所以 T 了。

想到了 kmp 的结论（以前 vp 的时候推过），但是没有注意到两件事：

1. 行和列是独立的，把每一列看成整体求行的答案，然后行和列的答案乘起来就是矩阵答案
2. 可以用字符串哈希加速以上过程

这题没有想太久就去看题解了，但是有一说一确实学到新思路，如果自己死磕可能又浪费很多时间。感觉这才是合适的练习节奏。

2023/11/09

• 洛谷1495 【模板】中国剩余定理（CRT）

没看题解，1a 了。

上课之前做一道简单题练练手，没看板子自己推出中国剩余定理，最后推出来的结果居然和板子没区别，看来是掌握了，233。

• 洛谷4721 【模板】分治 FFT

看题解了，1a 了。

土豆押题分治 fft，学习一个。主要就是如果是 $a[n]=\sum_{i=0}^{n-1}a_ib_{n-1-i}$ 的形式，也就是说前面卷成后面，那么就分治。现求 $[l,r]$ 的值，并假设 $[0,l-1]$ 的值已经知道而且贡献已经贡献完毕。那么先递归求出 $[l,mid]$ 的值，然后进行 $[l,mid]$ 到 $[mid+1,r]$ 的贡献。这一部分画画图就知道了，能够恰好写成一个卷积形式。那么对这部分贡献进行 ftt（ntt）然后做乘法即可。

2023/11/10

• AGC 005 Problem F

看题解了，没有 1a。

生成函数练习题，每一步都在我的智慧之外，看来要学的还有很多啊。

这题是给你一个树，对于点集 $S$，定义 $f(S)$ 表示包含 $S$ 的最小子树的点数，问你对于任意大小 $k$ 的任意点集 $|S|=k$，$f(S)$ 的和是多少。

以下是几个关键步骤：

1. 首先固定 $k$
2. 考虑点在不在里面比较困难，所以考虑边
3. 假设这条边左边有 $a$ 个点，右边有 $n-a$ 个点，那么这条边所在的集合就有 $\begin{pmatrix}n\\k\end{pmatrix}-\begin{pmatrix}a\\k\end{pmatrix}-\begin{pmatrix}n-a\\k\end{pmatrix}$ 个，也就是所有的情况减去全在左边的情况再减全在右边的情况，这里是一个整体减局部的思想
4. 现在的目标是快速求 $\sum\begin{pmatrix}a\\k\end{pmatrix}$，统计一下每个 $a$ 和 $n-a$ 出现的次数 $c_i$，就转化为求 $\sum c_i\begin{pmatrix}i\\k\end{pmatrix}$，这里是一个和式转贡献的思想
5. 把这个式子拆开，就可以写成卷积形式 $\frac{1}{k!}\sum_{i=0}^nc_i(i!)\frac{1}{(i-k)!}=\frac{1}{k!}\sum_{i=0}^nf(i)g(k-i)$，其中 $f(i)=c_i(i!),g(i)=\frac{1}{(-i)!}$，这里是把求每一个值转化为求卷积的思想
6. 算卷积时会发现一个问题 $g(i)$ 在 $i>0$ 时无定义，于是全部右移 $n$，定义 $g'(i)=\frac{1}{(n-i)!}$，最后从 $x^{n+k}$ 中取答案即可，这里是多项式中负数下标的处理方法

这 6 步每一步我都想不出 囧，毕竟计数题技巧性很强呀，还得多多做题，光会板子不太够。

最后没有 1a，是因为模数居然不是 998244353，而是 924844033（原根 5），本子好像更喜欢用这个数。

• ICPC2021 沈阳 B

没看题解，1a 了。

秒了一个铁牌题，233。经典的分比特位考虑+二分图染色。