日寄 of Febuary,2025

Sun Feb 09 2025

24 minutes

OI生涯记录日寄 OI

6040 words

~~孩子们，我回来了~~

2.9#

回来第一天，教练换了种训练法，给一套题，然后早上尽全力做，下午自己改。

~~好好好相当于 6 天考 6 次~~

第一次，4h 一题没出。

一开始以为是 DP，但是是搜索 + 大力优化。

具体就是写个记忆化，然后直接枚举每种状态。

数位 DP，但是还以为是找规律。

~~过了一个寒假都忘完了~~

直接枚举倍数会 T 飞，所以考虑枚举数，然后判断。

记录 num 代表模 $k$ 意义下的数，sum 代表二进制下 $1$ 的个数。

如果 num 最后等于 $0$ ，则将 sum 计入答案。

然后套板子就是了。

神奇 DP，~~实话说没怎么看懂~~

我们设 $dp _ {i,j}$ 表示第 $i$ 层，还剩 $j$ 个木块的方案数。

则有 DP 方程如下：

\text{let } k = \min (i,j) dp _ {i,j} = \sum _ {p = 1} ^ k (i + 1 - p) \times dp _ {p,j - p}

这个是 $\Omicron(n ^ 3)$ 的，会炸。

我们可以发现，这个可以把每个 $dp$ 的值展开，实际上就是从 $(1,2)$ 到 $(i,j - i)$ 的所有 $dp$ 的和，并且差值都是 $dp _ {i - 1,j} - dp _ {i - 2,j}$ 。

于是，我们就可以把答案优化为 $dp _ {i,j} = 2dp _ {i - 1,j} + dp _ {i - 2,j} + [j \ge i] dp _ {i,j - 1}$ 。

这样就能 $\Omicron(n ^ 2)$ 过了。

下午就把前三题和 T5 改了。

晚上懒得改 T4 了（不想手写 bitset），于是去写平衡树了。

2.10#

~~DP 综合训练~~

记忆化搜索。

我们发现，如果存在 $a \gt b \lt c$ 的木块，则中间的一定不能被合并，无解。因此，答案一定是一个单峰的形状。

而我们又发现， $\sum a \le 2 ^ {13}$ ，所以我们可以考虑维护每一个状态。

但我们又发现，每一个木块有两种放法，总共是 $2 ^ {26}$ 种状态。但是，知道了一边的和，我们就可以知道剩下一边的和，只用维护 $2 ^ {13}$ 种状态就好了。

然后暴力记搜救好了。

记得首先判断 $\sum a$ 是否是 $2 ^ i$ 。

上午写了个暴力，跑了所有 $n \in [1,40],k \in [1,n]$ 的情况，但是没看出规律。

翻译一下题面，就是把一个整数 $n$ 分为恰好 $k$ 个整数的和的方案数，就是 $p(n,k) = [i \ge j](p(i - j,j) + p(i - 1,j - 1)),p(0,0) = 1$ ，递归求解就好了。

但是，为什么不取模啊，还得开 int128。

很神奇的一道期望 DP。

首先，我们设 $dp _ {i,j}$ 表示正常进度花了 $i$ 秒，实际已经用了 $j$ 秒的期望剩余时间.

因为是期望 DP，一般倒推，所以答案为 $dp _ {0,0}$ 。

然后我们考虑转移，我们在发生意外的情况下，可以考虑是否重开，否则必须重开。

因此有转移方程：

dp _ {i,j} = (1 - p _ i)(dp _ {i + 1,j + t _ {i + 1} - t _ i} + t _ {i + 1} - t _ i) + \begin{cases} p _ i\min (dp _ {0,0},dp _ {i + 1,j + d _ i + t _ {i + 1} - t _ i} + d _ i + t _ {i + 1} - t _ i),j + d _ i + n - t _ i \lt r p _ i \times dp _ {0,0},\text{Otherwise} \end{cases}

然后神奇的就是，DP 方程里面有 $dp _ {0,0}$ ，我们要求的也是 $dp _ {0,0}$ ，然后因为存在 $\min$ 所以你不能暴力解方程。

所以，考虑二分，每次二分一个 $dp _ {0,0}$ ，然后和算出来的 $dp _ {0,0}$ 比较，如果大了就计入答案并且调小一点，否则调大一点。

有一说一不取模的计数 DP 真的烦，关键还卡 Python。

晚上~~好像在水题~~。

2.11#

今天考试。

T1#

乍一看就不会做，打了个暴力骗了 30pts。

实际上是区间 DP，但是没改。

T2#

第一眼看到撤销，我还以为是可持久化，但是再一看是定点撤销，就不用想了。~~甚至可以撤销撤销操作~~

赛时我本来想的是维护括号序列的树形结构，然后撤销和恢复就直接改儿子数量就好了。

但是大样例过不去，问题是如果有几个已经撤销的点连在一起，要么复杂度假，要么直接假。

实际上是用线段树维护每一层的括号数量，但是太烦了，我写的矩乘线段树。

我们发现，对于 $1$ 操作， $ans \to ans + cnt + 1,cnt \to cnt + 1$ ；对于 $2$ 操作， $ans \to ans + 1,cnt \to 1$ 。

然后我们维护一个向量 $\begin{bmatrix} ans & cnt & 1 \end{bmatrix}$ ，然后转移矩阵就出来了。

对于撤销操作，我们可以用线段树维护操作序列的 Trick，撤销的时候，把这个矩阵改成单位矩阵，恢复就改回来。

然后答案就是 $(ans \times tree _ {1}) _ {1,1}$ 。

T3#

神奇构造题，不会也没改。

T4#

神奇图论题，不会也没改。

2.12#

打了一场 Div.2 VP，做了 ABD 三道。

我们发现，如果 $n$ 的后面有 $k$ 个 $9$ 的话，那 $S(n + 1) = S(n) - 9k + 1$ 。

因此，我们就可以直接判断 $x - y + 1 \mod 9$ 是否等于 $0$ ，同时注意， $k \ge 0$ ，要判断 $\frac{x - y + 1}{9} \ge 0$ 。

神奇策略。

我们设 $c _ i$ 为 $i$ 在 $a$ 中出现的次数，则我们直接遍历整个值域，如果 $c _ i \ge 2,c _ {i + 1} \to c _ {i + 1} + c _ i - 2,c _ i \to 2$ ，如果遇到 $c _ i = 1$ ，则无解。

交互题。

首先，题目中说了， $\forall i,j,(x _ i,y _ i) \neq (x _ j,y _ j)$ ，意思是，B 对象不可能出现 $0$ ，而 A 对象只有在没有路径的时候才能出现 $0$ 。

所以，如果有 $p \notin x$ ，就可以查询 $p$ 和其他任意一个点，如果是 $0$ 就是 A 对象，否则为 B。

那如果一个不缺呢？我们发现对于 B 对象， $dist(a,b) = dist(b,a)$ 。所以，我们可以分别查询 $(a,b),(b,a)$ 。

但是 A 对象也可以通过给你一个环来卡你，所以，我们选择的 $a,b$ 就有要求。

因为前面缺失数的情况已经被判断掉了，所以我们可以直接选择满足 $x _ a = \min x,x _ b = \max x$ 的 $a,b$ ，然后判断返回值是否大于等于 $n - 1$ 。

因为就算 A 对象出环卡你，它的距离也一定不会大于 $\frac{n}{2}$ ，而前面选择最大最小值，就可以保证距离最小为 $n - 1$ 。

所以，我们的策略就如下：

首先判断 $x$ 是否为 $[1,n]$ 的错排，如果不是，就可以查询不在 $x$ 中的一个点，若返回值为 $0$ 则为 A，否则为 B。
如果不是错排，则选取最大最小值的点，判断返回值是否相当并且大于 $n - 1$ ，如果是，则为 B，否则为 A。

然后下午接着补 CF 的题，顺便学习了主席树维护区间 MEX 的操作。

因为李超树的专题里面有两道点分治 + 李超树的题，于是就在学点分治。

~~我觉得点分治只有求重心是一样的。~~

2.13#

今天终于拉专题了。

本来是在做 C 题，点分治 + 李超树，但是写挂了，写了一个上午，然后就没重构。

下午不想写，于是去学了学 KTT，然后花了半个下午搞定了板子题，之后就去跟 P5073 斗志斗勇了。

我们可以通过将操作离线，然后对全局加的数求前缀和来消去 KTT 不能操作负数的问题，但是第一次可能是负数，所以可以暴力加，加完再建树。

然后就是 KTT 维护最大子段和的模板题，但是 lxl 的毒瘤数据以 0.01s 卡掉了我。交了大概一页，突然发现可以将快排换成归并，会更快，然后就过了。

晚上教练让我们验初赛题，直接请 DeepSeek 上来 awa。

2.14#

考试。

T1#

结论题，然后赛时没想出来。就是对每一行的最小值取最大值。

T2#

DS 题，主要是求区间前驱后继，但是卡平衡树，我的主席树还写挂了。

T3#

DP，不会。

T4#

缩点 + DP，不会。

2.17#

今天拉专题。

这几天可以能都要写树分治吧。

早上去参加开学典礼，

CF263E

~~为什么不给翻译啊~~

读完题就发现，这个就是 P4178 变到二维上，并且第二维的值域不许你开树状数组。

我们可以将 P4178 的平衡树换成树状数组套平衡树，然后一交，发现 T 了，看来是卡了常数巨大的 $\Omicron(n \log ^ 3 n)$ 。

但是我们可以考虑剪枝，我们可以记录之前插入的最大范围，查询的时候，我们在这个范围里面查就好了。

我们再记录该子树内的最大深度，在插入的时候，我们只插入到 $dep$ 就好了。

Luogu P4149

一眼板，把板子记录的是否拥有改成最小边数就好了。

Luogu P6329

点分树模板，但是调了一上午，可能和今天早上不舒服有关。

点分树就是把点分治每一层的分治中心拿出来建一棵重构树，因此，树高就是点分治的层数，即 $\Omicron(\log n)$ 。

然后，我们发现，这棵重构树~~和原树一般没什么关系~~，但是有一点可以确定，重构树上的 LCA 一定在原树 $x \to y$ 的路径上。

结合前面写的树高为 $\Omicron(\log n)$ ，我们可以考虑暴力跳父亲，跳到根为止来枚举路径。

但是，我们可能会统计到在同一子树内的答案，于是我们还需要去重。

我们可以记录 $sum _ 1(x,k)$ 表示在重构树上与 $x$ 的距离 $\le k$ 的点权和， $sum _ 2(x,k)$ 表示重构树上 $x$ 的父亲的子树中与其距离 $\le k$ 的点权和。

则答案为 $\sum sum _ 1(fa _ x,k - dis) - sum _ 2(x,k - dis)$ 。

修改就一路向上跳单点修改就好，因此我们可以直接用树状数组维护。

2.18#

考试，因为是老 NOIP 所以只有三道题，35pts。

T1#

码农模拟，不改了。

T2#

根号分治，设定一个阈值 $B$ ，用正常套路，小于 $B$ 的暴力修改，大于 $B$ 的可以通过预处理来解决。

T3#

首先，对于每一个 $k$ ，合法集合的方案是唯一的。

然后，设 $f _ {n,k}$ 表示 $n$ 个人中 $k$ 个赢的概率。

考虑转移，我们新加一个人，即 $f _ {n,k} \to f _ {n + 1,k}$ 。

我们考虑在两个方向加入这个人，如果在前面，那么输则要使原来的赢家接着赢，概率为 $(1 - p) ^ k$ ，赢则要赢过所有大于它的，概率为 $p ^{n - k + 1}$ 。

所以，可以得到 $f _ {n + 1,k} = f _ {n,k} \times (1 - p) ^ k + f _ {n,k - 1} \times p ^ {n - k + 1}$ 。

同理，考虑放在后面可以得到 $f _ {n + 1,k} = f _ {n,k} \times p ^ k + f _ {n,k - 1} \times (1 - p) ^ {n - k + 1}$ 。

联立方程：

f _ {n,k} \times (1 - p) ^ k + f _ {n,k - 1} \times p ^ {n - k + 1} = f _ {n,k} \times p ^ k + f _ {n,k - 1} \times (1 - p) ^ {n - k + 1} f _ {n,k} \times ((1 - p) ^ k - p ^ k) = f _ {n,k - 1} \times ((1 - p) ^ {n - k + 1} - p ^ {n - k + 1})

即 $f _ {n,k} = f _ {n,k - 1} \times ((1 - p) ^ {n - k + 1} - p ^ {n - k + 1}) \times ((1 - p) ^ k - p ^ k) ^ {-1}$ ，初始情况是 $f _ {n,0} = 0$ 。

这样，在 $p \neq 1 - p$ ，即 $p \neq \frac{1}{2}$ 时就能 $\Omicron(n)$ 算出答案了。

然后我们考虑 $p = \frac{1}{2}$ 的情况，则输和嬴的概率都是 $\frac{1}{2}$ ，我们在 $n$ 个人中选 $k$ 个就好了， $f _ {n,k} = \frac{C _ n ^ k}{2 ^ {k(n - k)}}$ 。

晚上打了一场 CF Edu。

A#

签到题，如果有 $b _ {i \sim i + 2} = [1,0,1]$ 则无解。

~~那我为什么还 +2~~

B#

签到题，注意到每一种颜色对答案的贡献要么为 $1$ 要么为 $2$ ，当有相邻的同色块时为 $2$ ，统计所有贡献并减去最大的就好了。

~~这种题挂一发~~

C#

写了题解，直接拿过来算了。

CF2069C

由美丽数列的定义得，一个美丽数列一定是形如 $[1,2,2,\ldots,2,3]$ 的。由此启发我们来枚举每一对可以匹配的 $1,3$ 。

然后我们发现，子序列也是可以算作美丽数列的，设一共有 $k$ 个 $2$ ，则美丽数列的数量为 $\sum _ {i = 1} ^ {k} C _ {k} ^ {i} = 2 ^ {k} - 1$ 。

运用前缀和的思想，我们记 $sum _ {i} = \sum _ {j = 1} ^ {i} [a _ {j} = 2]$ ，则我们可以枚举每一对 $1$ 和 $3$ ，然后计算答案。

上面这个算法是 $\Omicron(n ^ {2})$ ，无法通过此题，考虑优化。

我们发现，每一个 $3$ 会和前面所有 $1$ 匹配，记 $cnt _ {i} = \sum _ {j = 1} ^ {i} [a _ {j} = 1]$ ，若 $1$ 的位置为 $p$ ， $3$ 的位置为 $pos$ ，则贡献为 $2 ^ {sum _ {pos} - sum _ {p _ {1}}} + \ldots + 2 ^ {sum _ {pos} - sum _ {p _ {cnt _ {pos}}}} - cnt _ {pos}$ 。

我们可以把每一项的 $2 ^ {sum _ {pos}}$ 提出来，后面就是 $\sum _ {i = 1} ^ {cnt _ {pos}} 2 ^ {-sum _ {p _ i}} = \sum _ {i = 1} ^ {cnt _ {pos}} (2 ^ {sum _ {p _ i}}) ^ {-1}$ ，然后再用前缀和，记 $invsum _ {i}$ 表示 $\sum _ {j = 1} ^ {i} (2 ^ {sum _ {j}}) ^ {-1} \times [a _ {j} = 1]$ ，则我们只需要枚举所有的 $a _ {i} = 3$ ，然后将 $2 ^ {sum _ {i}} \times invsum _ {i} - cnt _ {i}$ 计入答案即可。

时间复杂度为 $\Omicron(n)$ 。

~~然后看着别人六行的核心代码陷入了沉思~~

2.19#

打完 CF 能起晚一点就是爽。

早上过来，先把 C 题的人类智慧写成了题解，然后就去改了下 D，其实还是比较简单的贪心，如果 A,C 都不卡壳我应该能过。

因为有 Open Hacking 所以没出 Rating 变化，这肯定不能掉分了吧。

然后就把 CF 1303G 过了，过来才发现是路径长度维护反了。

过了一道点分治的题，昨天脑子抽了，不知道用什么 DS 维护，都在想 KDT 了，然后今天用线段树就过了。

2.20#

CF 分算完了，重新上绿了，爽了。

~~只要下次不掉回灰就好。~~

今天考试，黄题二分没想出来，只有 60pts。

T1#

利用了期望的线性性，答案为 $1 + \sum _ {i = 2} ^ n P _ i$ ， $P _ i$ 表示第 $i$ 堆在第 $1$ 堆前被取走的概率。

考虑求 $P _ i$ ，发现只和 $1,i$ 两堆有关，则 $P _ i = \frac{a _ i}{a _ 1 + a _ i}$ 。

然后就没有然后了。

T2#

如果不改变值，则就是 P1182，二分最大值就行。~~但是它有啊~~

我们发现，如果随机枚举 $x$ ，则 $Ans _ x \lt Ans$ 的期望是 $\sum \frac{1}{i} \approx \ln x$ 。

则我们可以随机生成一个 $x$ 的序列，然后每次遇到一个 $x$ 就用 $Ans - 1$ check 一下，如果非法，则继续下一个，否则就二分答案。

时间复杂度好神奇， $\Omicron(nm + \ln n (n \log n))$ 。

T3#

数论 + 容斥题，还要用 Miller-Rabin。

省流： T1 太简单气活了，T2 太神经气笑了，T3 太难气死了。

2.21#

补题。

本来说今天去讲题的，但是 G 题树套树送走了所有人，H 题又根本没人听。

然后就是把线段树优化建图学会了，同时用人类智慧方法过了 I 题（线段树优化建图 + 树剖 + Tarjan SCC）。

2.22#

考试。

T1#

我们发现，我们可以把最高点找出来，然后在旁边加数，贪心的往贡献小的地方加，同时用树状数组统计逆序对就行了。

T2#

首先，我们设 $f _ {i,j}$ 表示考虑完了前 $i$ 条线段，最后在 $j$ 的最小花费。

首先， $f _ {0,j} = |j - x|$ ，然后我们转移。

对于 $f _ {i,j}$ ，首先先加入线段 $i$ 的贡献， $f _ {i,j} = \begin{cases} l _ i - j, j \lt l _ i 0,l _ i \le j \le r _ i j - r _ i,j \gt r _ i \end{cases}$ ，然后我们用 $f _ {i,j} + 1$ 去更新 $f _ {i,j - 1},f _ {i,j + 1}$ 。

我们如果把 $f _ {i,j}$ 看作关于 $j$ 的函数，则我们发现它的导函数分为 $-1,0,1$ 三段，则 $f ' _ {i,j} = 0$ 的答案最优。

T3#

没改。

T4#

忘了/

2.24#

今天打 USACO。

其实昨天晚上就开了银组，然后没 AK，于是我重新注册了个号，上午在打铜组。

T1 是个简单模拟，T2 对权值数组做一个前缀和就做完了，T3 是个区间 DP。

然后下午也没有开银组，去补 Jan 的 USACO 了。

2.25#

考试。

T1#

原题是求 $\sum _ {i = 1} ^ n \sum _ {j = 1} ^ p \varphi(i ^ j) \pmod {10 ^ 9 + 7}$ 。

我们可以直接枚举 $i,j$ 来打表，发现 $\sum _ {j = 1} ^ p \varphi(i ^ j) = \varphi(i) (1 + i + i ^ 2 + \ldots + i ^ {p - 1}) = \varphi(i) (i ^ p - 1) (i - 1) ^ {-1}$

则 $Ans = \sum _ {i = 1} ^ n \varphi(i)(i ^ p - 1)(i - 1) ^ {-1}$

但是这个 $n$ 达到了 $10 ^ 7$ ，必须线性求 $\varphi,i ^ p,i ^ {-1}$ ，但是这三个都可以用线性筛筛出来，因为 $i ^ {-1} \equiv i ^ {m - 2} \pmod {m = 10 ^ 9 + 7}$ 。

所以总复杂度是 $\Omicron(n \log _ n p)$ 的。

T2#

发现，从大到小，每加入一个无限制的数，空位会多一个，加入一个叶子节点，空位会少一个，把每次操作前的空位数量求积就行。

T3#

不会的 DP。

T4#

神奇博弈论。首先，我们可以求出数列中所有数的异或和，记为 $S$ ，游戏是平局当且仅当 $S = 0$ 。

否则，我们可以找到 $S$ 的最高位，然后 $a _ i \gets a _ i \operatorname{and} 2 ^ p$ 。这样， $a$ 就是一个仅包含 $0,1$ ，且一定包含奇数个 $1$ 的数列了。胜的条件就变为取到奇数个 $1$ 。

然后分类讨论，若 $n$ 是偶数，那么先手一定能拿到奇数个 $1$ ，先手必胜。

否则，如果先手取了两边的一个 $0$ ，则局面就变成了 $n$ 为偶数，奇数个 $1$ ，先手必败。因此，先手一定会取 $1$ ，我们可以先把两边相同的删去，然后，如果相邻的两位相同，那才先手必胜，否则先手必败，同时，需要满足剩下的 $1$ 的个数是 $4$ 的倍数。

2.26#

今天做题。

大力补 USACO 2025 Jan 的题。

全部写下面得了。

做题记录

Silver 2 #

我们转换一下题意，就是找到一个 $x$ ，使得满足 $a _ i \equiv x \pmod M$ 所需要的操作次数最小。

于是，这个东西就可以转化为求一个点，使得它到其他所有点的距离和最小。这个有个结论，就是取中位数。

然后注意，这个是在模意义下的，所以可以加到 $x$ ，也可以减到 $x$ ，所以需要复制一遍，并且全部加上 $M$ ，然后统计贡献。

Silver T3 #

什么~~出题人求 npy~~ Ad-hoc 题。

我们发现，数量为一的数只有 $2,2n$ 两个，并且 $2$ 对应了一些不重复的数， $2n$ 也对应了一些不重复的数（推不出来可以打表）。

于是，我们就可以通过这个来推出对应关系，然后取字典序小的那个就好了。

Gold T1 #

这个一看就不知道该怎么做，直接考虑 DP。

设 $dp _ {i,0/1/2}$ 表示 $i$ 的值小于/等于/大于中位数， $w _ {0/1/2}$ 表示把小于/等于/大于中位数的变成 $m$ 的花费。

则有 DP 方程 $dp _ {u,x} = \min _ {med(i,j,k) = x} \{ dp _ {ls,i} + dp _ {rs,j} + w _ k \}$ ，如果没有儿子，那就是 $dp _ {i} = w$ 。

考虑带修的情况，因为完全二叉树的树高为 $\log n$ ，所以可以暴力修改，然后 $dp _ {1,1}$ 就是答案。

Gold T2 #

~~好耶，是 DS~~

因为 $1$ 操作不改变连通性，所以我们可以将 $t$ 视为假装删除，即不统计其贡献，否则直接删除。

由于不好维护删除，所以我们考虑反向操作，改成加入点，这样就可以方便的用并查集维护。加入点的时候更新集合的大小与答案，合并集合的时候也更新答案。

今天终于开可持久化了，光速刷榜交了过了的题。

然后学了可持久化 01Trie，顺手写 Blog。

2.27#

考试。

T1#

想不到怎么做，考虑 DP。

设 $dp _ {i,j,k}$ 表示考虑前 $i$ 个， $\{i - 1,i,i + 1\}$ 有 $j$ 个， $\{i,i + 1,i + 2\}$ 有 $k$ 个，且 $[1,i]$ 全部用完的方案数。

考虑转移，我们发现 $dp _ {i,j,k}$ 可以转移到 $dp _ {i + 1,k,cnt _ {i + 1} - j - k - 3x}$ ，然后就做完了。

但是这道题卡空间，所以 $dp$ 要动态开。

T2#

原题，ARC144C

T3#

不会，笛卡尔树 + 奇奇怪怪的算贡献。

T4#

不会，奇奇怪怪的 DP。

今晚打 CF，但是没回家，得在机房待到十二点。

A#

发现在模 $15$ 意义下， $0,1,2$ 都会产生贡献，算出来就好了。

B#

我们统计一下前缀和，如果存在 $-x$ ，则答案加一，然后找循环节，也就是前缀和为 $0$ 的地方，找到后就能算出次数了。

C#

最大值最小，一眼二分。

我们枚举 $x$ ，若 $a _ i \lt x$ 并且 $s _ i = \text{R}$ ，则必须满足，如果大于 $x$ 并且为蓝色，则也必须满足，最后统计段数然后判断是否 $\le k$ 就行了。

D#

盯真题。

我们设 $f _ i$ 表示到达 $i$ 的方案数， $sum$ 表示当前层的 $\sum f$ ，则下一层每一个点 $p$ 的贡献为 $sum - f _ {fa _ p}$ ，最后求和就好了。

2.28#

睡到 8 点才去机房~~吃泡面~~。

先把 Edu 的 C,D 补了，然后就做可持久化专题去了。

因为 jmr 的题可能要用线性基，就去学了学。

还有为什么可持久化专题会有纯图论题啊。