【做题笔记】冬去春来再尽年

· · 个人记录

前言

破晓呐喊鸣响极目所见彼方

一束光加速阴霾的消亡

重叠温热手掌铭记心声残响

让誓言融进血液鼓动心房褪尽晨曦苍凉

——《冬去春来再尽年》

5 月 16 日到 6 月 22 日做的题。因为最近在忙 whk，所以有点少。这就用了一个月，也不知道我还有几个月好活了。

这不是写题解，只是个总结，所以排版有点乱（并且有的是在手机上写的）。

上接【做题笔记】夏夜空

下接【做题笔记】Dance Night（应该……会有的吧？）

无耻的求赞/kel

P3835【模板】可持久化平衡树

板子题，不怎么需要动脑子，把普通平衡树的所有赋值语句改成 COPY copy 节点即可。

我做这题的时候犯了几个弱智错误。copy 函数好像把最后一个节点的下标当成了要复制的节点的下标，调半天。

P5055【模板】可持久化文艺平衡树

这个也是板子题。

用平衡树维护一个序列，就类似于用权值树状数组做普通平衡树这个过程反过来。一个是把集合操作变成序列操作，一个是把序列操作变成集合操作。这样就好理解了。

维护区间和跟维护 siz 一样就行。标记下传比较神奇，copy 之前要下传，我不知道为什么，不过好像尽量多 pushdown 不会错的。

P3320 [SDOI2015]寻宝游戏

席子叫我调这题，所以我就做了一下。这题好像就是蓝书上题目背景是微软的那个题。

手玩一下不难发现题目要你求的这个东西就是dfs序相邻的所有两个点的路径的并。这很显然，因为是个树，两点之间路径唯一，a->b b->c 肯定包含了 a->c 的路径。

然后修改操作是加点删点，加点删点只会影响到新加的点相邻的两个点。用权值树状数组找一下相邻的两个点，用 lca 求出任意两点之间的路径长度，就可以维护总代价了。

P3402 可持久化并查集

这也是板子。路径压缩是均摊复杂度的，不能可持久化，只能用按秩合并。

显然，并查集本质上就是在一个数组上改几下，所以把所有的数组改成可持久化数组就行了。调起来有点烦，容易写混，比如 querysz 调用了 query 之类，而且我在修改根节点的地方写出了 UB：update(1, n, rt[i] = ++forever, xx, yy, rt[i])

TLE 说明你的按秩合并的秩写错了。

P1442 铁球落地

简单题。原来是紫的，我发了个帖子然后降绿了。这题很像「REOI-1」深潜的第六兽，因为那题是我在洛谷 gks 第一次赛时 AC 的绿题，所以印象十分深刻。

首先状态转移方程是显然的，但是转移的时候需要找到从左/右掉下去第一个碰到的是哪个线段，即查询包含一个 x 坐标的线段最靠上的是哪个线段。显然这个就相当于从下往上扫过去然后遇到一个线段就把那一段 x 坐标赋值成线段的序号。区间赋值，单点查询，要用线段树。然后就做完了。

P3747 [六省联考 2017] 相逢是问候

毒瘤题。

首先可以发现一个元素只能进行几次修改操作，所以可以用一个线段树。虽然不能直接对整个区间进行操作，但是可以直接暴力操作每一个节点并记录操作次数，如果操作次数足够多就直接退出。这样复杂度也是对的。

对单点进行修改就是计算一个高度为修改次数的幂塔，这个类似于炸脖龙I那题。不过这题的模数范围比那题大，所以不能直接筛 phi，只能暴力求出需要的那几个值（也就是从最初的模数一路求 phi 会遇到的那几个数）。求幂也不能直接快速幂，因为这题幂是固定的，所以可以用光速幂优化。（改这个的时候别忘了记录指数是否大于模数，经过了有效的取模操作，这样才能用扩展欧拉定理）

边界问题跟炸脖龙也是一样的，很容易写错。这里有一组 hack 数据。

代码很长。至少我个人觉得写起来非常痛苦。

P4774 [NOI2018] 屠龙勇士

这题看上去就是个小清新 excrt 板子题，实际上也是，但是。代码不知道为什么写了 2.59KB，比楼上的相逢是问候还长，成为了我最近写的最长的一道题。

题目描述有点难读 差点以为是“抽象类”大模拟， 但是读完之后就发现每条龙对应的剑是固定的，按照题意模拟即可（要求前驱后继，所以要用权值树状数组模拟。数据范围比较大，还要先离散化。）然后观察题面和数据范围，可以发现实际上是两个问题：

这个形式很像 excrt，不过前面带个系数 k，因为 k p 不一定互质，所以不能直接乘逆元。不过逆元实际上就是把 kx = 1 的 k 化掉，所以类似的使用 exgcd 就行。注意转化之后模数也会除以 gcd(p, k)。

我写的一直 70pts，有两个地方写错了。一个是离散化写的很神奇，一个是 exgcd 转化原方程的时候模数没有除以 gcd(p, k)。

P4955 [USACO14JAN]Cross Country Skiing S

水题，显然是二分。

P1128 [HNOI2001] 求正整数

有点像反素数那题。因为约数个数就是每个质因数的幂次加一的乘积，不难想到用一个 dfs 枚举约数的质因数分解，这个时候的原数显然就是把大的幂次给小的质数。答案可能很大，用 Python 即可。

P6105 [Ynoi2010] y-fast trie

看到有人随机跳到了这个题，所以做了一下。原来 Ynoi 还有纯思维题的吗

显然输入可以全部先取模。然后 (i+j)\bmod C 就可以分两种情况讨论，i+j\ge C 和 i+j<C。前者显然 i 和 j 越大越好，取最大的两个加起来即可，反正也超不过 2C。

后者就是找两个数加起来小于 C 且最接近 C。如果其中一个数是固定的，那么只需要找到 C-i+1 的前驱即可。如果 C-i+1 的前驱是 j，则我们称 i 喜欢 j。显然，最优解一定是 i 喜欢 j 并且 j 也喜欢 i（不然就可以把其中一个换掉得到更优的解）。我们把这种情况称为 i 和 j 是 CP。于是可以维护所有的 CP 关系，复杂度是 O(1) 的。（其实只需要维护 CP 关系的价值即可，是不是 CP 可以需要的时候再判断）

接下来考虑如何插入一个数。插入一个数就是试图在它和它喜欢的人之间连边。如果它喜欢的人没有 CP，或者有 CP 但是它比它喜欢的人的 CP 更优的话，就抢过来，也就是连一条边，删一条边（如果有）。注意这里不会像增广路一样影响到一串边，因为只有一方解除匹配，另外一边没有受到影响，没法连新的边。

删除就是这个过程反过来做一遍。

这就做完了？做完了。

写这题的时候判 -1 不小心把 0 也判掉了，一直 81pts RE。。（因为这题答案需要解密，所以 RE 实际上也可能是 WA 的，感谢小猪和另外一位帮我的人）

一个类似但是完全不一样的题。

P3560 [POI2013]LAN-Colorful Chain

比星战更加板子的随机化哈希题。题目有点难读，实际上就是问一个字符串里有多少个子串能重排为给定串，输入格式在这个帖子里有。

显然符合条件的串长度是固定的，扫过去即可。问题变为了如何 O(1) 判定一个子串是否能重排为给定串。不难想到给每个字符一个权值，然后哈希。

P3964 [TJOI2013]松鼠聚会

一体机过题，应该没有紫。

这个好像是叫 摩尔 切比雪夫距离转 冯诺依曼 曼哈顿距离？不过 对于生命游戏爱好者来说 几乎是显然的。取一个 3x3 的网格，要求中间的格子到外面的所有格子 冯诺依曼 曼哈顿距离相等，不难想到把整个网格旋转 45 度，这样中间的格子到外面的格子距离都是 2 了。

好然后曼哈顿距离的 x 坐标和 y 坐标完全没关系。可以先按照 x 坐标排序完全不管 y 坐标，算出来所有 x 坐标上的距离之后再重新排序。x 坐标的距离怎么 O(n) 算呢。就是那个经典题，往任何一边移动 1 格的代价是远离的那边的点数减去靠近的那边的点数。（最近一次看到类似的东西是 LuoTianyi and the Floating Islands (Hard Version)）

哦，然后就做完了。

P5902 [IOI2009] Salesman

一体机过题。

经典数据结构优化 dp 入门例题。题意有点难读，这里简述一下：一条线上有一些物品，每个物品有不同的价值，向左移动一格和向右移动一格需要不同的代价，并且捡物品的顺序要求捡到的物品 T_i 必须单调不减。

如果 T_i 互不重复，那按照 T 排序之后就是从前往后选了。因为代价仅与上一个选择的物品的距离相关，所以枚举上一个选择的物品就可以 n^2 dp 了。现在考虑优化。首先分类讨论左移和右移的情况，设右移一格的代价为 C，当前考虑的物品在 x，价值是 v，则（只考虑当前物品左边的物品的）答案就是

v+\max\limits_{i\le x}(dp_i-C(x-i))

那个 -Cx 显然可以丢到 max 外面，然后里面的东西就只跟 i 有关了，是一个前缀最大值的形式。可以用一个树状数组维护 dp_i+Ci 这个东西的前缀最大值！（左移同理）

好然后考虑有重复的 T 的情况。显然如果 T 相同那么要么一直往右走一直往左走。我写的是每遇到一个 T，就按照坐标正着排一遍dp一遍反着排一遍dp一遍，然后把所有求出来的位置相同的 dp 值取 max（因为停止时的位置不同所以后续的结果也会不同）。（不过这个地方直接贪心我好像暂时也没想到什么 hack？）

注意树状数组初值要全部给 -inf.

P3287 [SCOI2014]方伯伯的玉米田

kyst 说这个题是甲紫。但是我没会做。被 kyst 吊打了。

这也是数据结构优化 dp 入门例题。

首先显然需要消除的是序列中的下降，所以拔高区间一定不会比拔高后缀优。然后设计状态：当前考虑第 i 个数，前面已经拔高了 j 次。（我就没想出来。。）注意一个位置可以拔高多次。

然后枚举当前位置要拔高几次，就可以朴素的 dp 了。发现它是一个二维前缀最大值的形式，所以可以用二维树状数组优化 dp。（所谓二维树状数组就是一维树状数组，但是把其中访问数组的部分改成了访问另外一维的树状数组。。记得二维树状数组别写成这样，反正我犯了这个弱智错误。。）

P3598 Koishi Loves Number Theory

终于写到最后一题了。

前置知识：高中数学等比数列求和公式。可得f(n)=\frac{x^{n+1}-1}{x-1}。（之前写错成了x^n。。感谢大%你之神）所有 f(n) 的分母都是相同的，所以可以先提出来。

因为要求它们的 lcm，先考虑它们的 gcd. 一个形如 x^{a}-1 能被什么数整除？（这个跟底数 2 并没有什么关系。） 所以 gcd(x^a-1,x^b-1) 也就是 x^{gcd(a,b)}-1。这样就能求出所有数的 gcd 了。不过并不能求出 lcm，因为 lcm(x^a-1,x^b-1)=\frac{(x^a-1)(x^b-1)}{x^{gcd(a,b)}-1} 这个奇怪的东西，不是原来的那个形式，不能继续和其他数结合了。

现在想想怎么从一堆数的 gcd 得到 lcm。手玩一下两个，三个，四个数的情况，可得就是所有大小为奇数的子集 gcd 的积除以所有大小为偶数的子集 gcd 的积。然后怎么求这个呢？

观察 CSDN 的题解可得， 总的 gcd 数量很少。用一个 map 来维护当前所有 gcd 的幂次。（也就是在分子的幂次减去在分母的幂次。当然 gcd 也是 x^n-1 的形式，所以只要记录 n 就行了）然后把数一个一个加进去。也就是把新的数和原来所有的 gcd 取 gcd，然后把原来 gcd 的幂次取相反数乘（因为记录的是幂次，所以就是加）进去。

最后用快速幂算一遍所有的幂次，相乘，除以 x - 1（别忘了），就是答案。

下期做题笔记，如果还有的话，我会继续为大家推荐更多条子和其他人的冷门凉曲和热门好鸽，敬请期待。

都看到这了别忘了点个赞w