2022 NOIP 备赛记

SUNCHAOYI · 2022-10-04 21:29:44 · 生活·游记

前言

已经高二了，依旧是蒟蒻。应该是最后一次比赛了，所以打算拼一把。

就从国庆这一天开始写起吧。没啥逻辑，想到啥就说点啥，也算是记录一下一个信竞生的日常吧。

\texttt{2022.10.01}

大概是开始零碎的复习了。

先从树链剖分入手，大概是每天码一题的样子，但是弱智的错误还是接连不断。什么询问下标没用改成 \texttt{dfn} 序啊，深搜写的时候忘记更新重儿子导致剖分了个寂寞啊等等问题是层出不穷。大概把剖分的基础题差不多写了一遍。

树链剖分往往和线段树相结合，所以说下标的问题要值得注意，因为剖分大多依赖的是 \texttt{dfs} 后的 \texttt{dfn} 序。在写询问的时候，总是记不清楚 if (dep[fx] < dep[fy]) swap (fx,fy),swap (x,y); 这个交换的顺序，认真的理解了一下，现在应该能明白了。while (fx != fy) 循环里的交换，默认 x 的深度大于 y，所以是让 x 向上跳；而循环外的最后一次交换，由于已经找到了最近公共祖先，所以方便编写我们让 x 成为深度较小的那个，从而进行线段树上的操作（线段树的更新中编号小的显然 \texttt{dfn} 序小，也就是深度小）。

做题时遇到一类需要进行与边权相关的操作的题目，有一个比较好的处理技巧--就是把边权转到深度较大的点上。考虑一下正确性，每一条边都被两个点相连，所以一定能通过这种方式将边权全部进行转化，而每一个点的深度在第一个 \texttt{dfs} 中已经记录，所以也不需要增加过多的代码。不过在查询的时候，需要注意的就是 \texttt{LCA} 那个点所存的边相当于是其上方的边，在询问是并不会经过，因此在查询时最后一次更新写成 modify (1,1,n,dfn[x] + 1,dfn[y]) 就能完美的解决这个问题。原因很简单，由树链剖分求 \texttt{LCA} 可知，最后的那个 x 就是最近公共祖先，又由于重儿子优先的原则，子树内所有的点的 \texttt{dfn} 是连续的，所以直接把这个点去掉即可。

习题列表：

P4114 Qtree1 同 QTREE - Query on a tree 边权转点权，单点更新，区间查询。
P4315 月下“毛景树” 边权转点权，区间更新，区间查询。
P3038 [USACO11DEC]Grass Planting G 同 SP12005 GRASSPLA - Grass Planting 边权转点权，区间更新，单点查询。
P3178 [HAOI2015]树上操作区间更新，区间查询。
P3833 [SHOI2012]魔法树区间更新，区间查询。
CF343D Water Tree 区间更新，单点查询。
CF165D Beard Graph 单点更新，区间查询，最近公共祖先。
P3950 部落冲突单点更新，区间查询，最近公共祖先。
P4116 Qtree3 轻重链剖分，set。

\texttt{2022.10.05}

数位 \texttt{dp} 的一些中等题先写起来，这种题目大多都有套路，一般用记忆化来写。给个最简单的模板：

ll dfs (int pos,bool limit,bool lead)
{
    if (pos > cnt) return 条件;
    if (!limit && ~dp[pos][sth.]) return dp[pos][sth.];
    int res = limit ? a[cnt - pos + 1] : 9;ll sum = 0;
    for (int i = 0;i <= res;++i) sum += dfs (pos + 1,(i == res) && limit,(i == 0) && lead);
    if (!limit) dp[pos][sth.] = sum;
    return sum;
}

一类题目可以直接进行记忆化，而一类题目需要通过合理的状态设计从而将其进行转移并记录。

习题列表：

P4127 [AHOI2009]同类分布枚举各位数之和来充当模数，从而进行记忆化。
P4317 花神的数论题枚举二进制数中 1 的个数，设 f[i] 表示有 i 个 1 的数的个数，之后根据乘法原理用快速幂求解。
P6218 [USACO06NOV] Round Numbers S 记录 0 与 1 的个数到达边界时进行比较即可。
P4124 [CQOI2016]手机号码记录前两位数以及不能出现的数这四个信息。注意前导零的处理，可以直接循环枚举第一位然后再去搜索，同时需要判断位数（L = 10^{10} 时，L - 1 的位数便不再符合）。

\texttt{2022.10.09}

国庆回来竟然就要月考，~~一通乱考~~，晚上还是来机房刷题。接着回到数据结构，再来看看树状数组。

说到树状数组，总是会与逆序对联系在一起，毕竟太经典了。同时，树状数组的题目往往伴随着离散化（要不就 \texttt{MLE} 了嘛）。弄清楚树状数组哪里需要 +1 或 -1，估计也就没什么大的问题了。

一般来说，查询 query (x) 表示求小于等于 x 的数相关的内容，所以求小于时需要 -1。又因为树状数组的区间查询是基于差分的思想，要减去左端点之前的部分，所以说也要 -1。似乎最常见的情况就只有这么多，先写这些吧。

由于线段树与树状数组都比较常考，接下来几天里，就做做有关的题目吧。

习题列表：

P6186 [NOI Online #1 提高组] 冒泡排序与逆序对相结合，记录 k[i] 表示逆序对数为 x 的位置的个数，然后通过找规律发现 c 轮的排序会少 \sum_{i = 1}^{c} k[i] 个逆序对，最后通过树状数组维护每次操作产生的影响。
P3586 [POI2015] LOG 通过找规律发现要维护的是 \ge s 的数的个数以及 < s 的数的和。需要离散化，所以如果是在线操作的话应该用平衡树去维护。
P4054 [JSOI2009] 计数问题二维树状数组，写起来和一位的差不多，同时再多开一维数组记录颜色的信息，查询的时候用差分的思想去解决问题即可。单点修改，区间查询。
P4514 上帝造题的七分钟区间修改，区间查询。令 d[i] = a[i] - a[i - 1]，则有 \sum_{i = 1}^{k} d[k] = a[k]，修改时分别处理 l 与 r + 1 即可。同样的，扩展到二维时，二维前缀和变为 \sum \limits_{i = 1}^{x}\sum\limits_{j = 1}^{y}\sum\limits_{k = 1}^{i}\sum\limits_{l = 1}^{j} d[k][l] = \sum \limits_{i = 1}^{x}\sum\limits_{j = 1}^{y} d[i][j] \times (x - i + 1)(y - j + 1) = \sum \limits_{i = 1}^{x}\sum\limits_{j = 1}^{y} (x +1)(y + 1)\times d[i][j] + (x + 1)j\times d[i][j] - (y + 1)i\times d[i][j] + ij \times d[i][j]。因此开四个树状数组分别维护这四个信息，最后还原差分序列即可。
P1637 三元上升子序列比较简单的一道题，遍历中间的那个数字，然后正反两边循环分别用树状数组维护比其大（小）的数的个数，根据乘法原理得出答案。
P3605 [USACO17JAN]Promotion Counting P 容易想到退化成链时变为求逆序对的个数。类似的，离散化之后用树状数组维护比某一节点大的数的个数，用 dfs 前后的值作差得到答案。
UVA12983 The Battle of Chibi 同 CF597C Subsequences 不难想到 O(kn^2) 的朴素 \texttt{DP}，dp_{i,j} 表示前 i 个数中以 i 结尾的且长度为 j 的严格上升序列。然后发现 dp_{i,j} 会由 dp_{i,j - 1} 得到，因此可以用数据结构优化 \texttt{DP}。对于第 i 个数，需要找到比它小且在它前面的节点，不难想到使用树状数组维护。同时，可以用滚动数组优化空间，得到最后的时间复杂度为 O(kn \log n) 的代码。
P5200 [USACO19JAN]Sleepy Cow Sorting G 不错的思维题。手模就能发现，最少的数目是倒序第一个出现 a_i > a_{i + 1} 的 i，相当于 i 之后的都已经有序，不需要移动。输出方案时，由于需要移到有序数组中的某一位置，因此需要知道移动时比它小的数的个数，用树状数组维护，对于每一个移动的量，答案为 k - i + query (a[i] - 1)。
P3582 [POI2015] KIN 由于不能某个数多次出现，则不能累加它的贡献。考虑枚举并记录每种数上一个数出现的位置，如果一种数两次出现，那么我们就把上一次的位置修改成其相反数从而抵消贡献;如果大于两次，显然不能多减去贡献，那么把上一个位置之前的全部变为 0 即可。于是题目就转换成了区间最大子段和，线段树维护左右子树的最大子段和，区间和，最大子段和即可。

\texttt{2022.10.16}

$\texttt{T1}$ 属于是无脑模拟，确定 $n$ 个化学方程式中的每一个化学方程式是否平衡，然后加了一堆便于操作而产生的条件。一开始写乱了，后来果断重构，写成函数，然后一发过样例，就没管它了。 $\texttt{T2}$ $60\texttt{ pts}$ 的部分分一眼秒，属于是二维前缀和优化求最大值，时间复杂度为 $O(n^4)$。然后考虑优化，容易想到固定 $x_1,y_1,x_2$ 时，$y_2$ 的枚举是可以一直往一个方向扫的，因此考虑尺取法。考虑一个结论，令一个矩形的价格之和为 $s$，若 $s \in [a,b]$，画一下数轴可知此时是最优解，而 $s$ 如果在这个区间之外，则需要尽量的靠近这个区间。所以尺取法以 $<a$ 和 $>b$ 为边界，正反扫两次，由于每个数最多被扫一次，所以时间复杂度为 $O(n^3)$，常数不大，可以通过此题。 ~~我不会说赛时因为自己 sb，只判断了两个极值然后写挂的。~~ $\texttt{T3}

贪心可知找到距离最近的一个电梯然后向上走即可，于是题目转化为求距离 x 最近的电梯。不难想到用线段树（求区间最大值）与二分维护，似乎直接线段树二分也行，复杂度还能少个 \log，之后直接求两点的劣弧的距离即可（笑死，赛时这里写挂了）。

由于成环的特性，直接进行线段树操作并不方便，考虑开三倍的数组，x,x + n,x + 2 \times n 均维护同一个位置，这样前后走的时候就方便处理了。

最后在 query 的时候加了个优化，如果左区间返回非零值就可以直接结束，这样刚好能够使 O(n \log ^2 n) 大常数的线段树过了这道题。

【updated】 发现题解写了一个记忆化搜索就过了，我敲！

\texttt{T4}

看了题解好像也不麻烦，看来对 \texttt{dp} 的状态设计能力还需要加强。由于交换顺序不会产生影响，设 dp_{0/1,i,j,k} 决定了区间外的最左/右的 i 个娃娃，区间内的最左/右的 j 个娃娃，代价为 k 时最大的减少量，转移时 dp_{0/1,i,j,k} = \max (dp_{0/1,i - 1,j,k},dp_{0/1,i,j - 1,k},dp_{0/1,i - 1,j - 1,k - abs (l - r)} + W)。从区间的左右分别选择做两次 \texttt{dp}，然后枚举断点进行合并。

由于i 这一维可以滚动数组优化，所以总时间复杂度 O(n^2k)，空间复杂度 O(nk)。当然，k 大于一定值时，答案一定为前 r - l + 1 小的值的和，所以也可以进行空间上的再次优化，不过不加也可以通过此题。

总的来说，这场模拟赛难度不大，但是却需要足够的细致才能一次写对，继续加油吧！

\texttt{2022.10.18}

开始状态压缩 \texttt{dp} 的复习。

P3694 邦邦的大合唱站队由于 m 的数据范围极小，所以设 dp_i 表示在 i 状态小的最小出队人数即可。
P2704 [NOI2001] 炮兵阵地首先预处理同行都情况，把合法的状态进行储存。之后处理列的情况，需要满足列也不冲突，因此状态中要加入前一行，枚举时需要从上两行开始处理。前两行比较特殊需要分开处理。
P2831 [NOIP2016 提高组] 愤怒的小鸟预处理出两个点能构成的所有 c = 0 的二次函数，记录一次二次项系数即可，然后将所有过某抛物线的猪放入一个状态中。转移时每次加入一条抛物线更新状态，当然要注意某抛物线只过一点的特殊情况。实现起来有一定的细节，需要注意 a < 0。
P3092 [USACO13NOV]No Change G 枚举各枚硬币的使用状态，然后转移时通过二分找到上一次的购买的物品。

\texttt{2022.10.21}

又是模拟赛。

然后 $\texttt{B}$ 一开始没想法，先去看了 $\texttt{C}$。发现是贪心，按三种属性分别从大到小排序后枚举后，判断第一对合法的三个人组成一组，然后输出即可。写完 $\texttt{C}$ 以后接着看 $\texttt{B}$，发现又是可以用 `set` 维护，一直往右扫，如果能解题目就解，否则弹出最大值来换（前提是更优的情况下）。写完用暴力拍了一下不对，然后发现要用 `multiset`，继续拍还是不对，然后就寄了。赛后发现是 `erase` 函数错了，不能写成 `s.erase(*(--s.end())`，因为这样会把所有一样的值全都删除。赛后改写成 `s.erase (--s.end())` 就过了（这样的话删的是末尾的地址指向的值，因此只会删除一个数）。 $\texttt{D}$ 因为模拟赛时间与吃饭冲突，所以就没写。赛后发现是个神必模拟，加个优先队列，按楼层高低为关键字排就过了。 ### $\texttt{2022.10.22}

晚上打了 \texttt{Atcoder}，意外的是得知 \texttt{G} 重题直接水过去了。另外 \texttt{D E} 都是简单的 \texttt{dp}，但是还是有一定的细节。\texttt{F} 赛时来不及了，赛后补吧。

\texttt{2022.10.23}

再次模拟赛。今天的 \texttt{ABC} 都偏简单，\texttt{D} 赛时没想出来。简单说一下做法。

### $\texttt{2022.10.24}

停课了。

早上补题。\texttt{D} 终于有想法了，发现答案为 n - \texttt{最长连续不下降序列}，但是只会 O(n^2)，将各个数字不重复的子任务相结合，写了个O(n^2) 的暴力求解加上 O(n) 的离散化后的 \texttt{dp}，然后得了 80，之后就卡在处理重复数字的优化上了。题解好像是比较直接的处理了，将题目转化为最大化固定不动的数字，然后通过分类讨论向前还是向后移，求得答案。

终于有时间把那些压箱底的题目给补了，通过了很是开心！！！

\texttt{2022.10.25}

上午打一场 \texttt{CF} 的模拟赛（复现赛），编号是 \texttt{CF1736}，$\texttt{A B C1}

切出 $4$ 题，大概在 $300-400$ 名左右吧，全靠 $\texttt{D}$ 的分作贡献。于是下午继续补 $\texttt{CF}$ 和 $\texttt{Atcoder}$ 的题目，……（省略一万字），就写到这吧。为啥晚上还会有一套模拟赛，啥都不会，没交上去评测，真凉心。 ### $\texttt{2022.10.26}

补了昨天 \texttt{CF} 剩下的两道题，\texttt{C2} 单独考虑每个数对答案的贡献，每个数最多扩展到的左端点为 f_i = \max (1,i - a_i + 1)，而综合考虑，第 i 个数能到的最左边的端点为 p_i = \max \{f_j\} (j \le i)，然后不修改时答案为 \sum_{i = 1}^{n} (i - (p - 1)) = \dfrac{n(n + 1)}{2} + n - \sum_{i = 1}^{n} p_i。修改时用线段树维护即可，看着题解写的，还是有那么一点麻烦。

晚上依旧模拟赛，终于可做。 $\texttt{T1}$ 博弈论，类似 $\texttt{Nim}$ 游戏，但是有上限，发现只要取个模就变为该游戏，所以对于上限 $x$，$\texttt{Alice}$ 胜的充要条件为 $a_1 \mod (x + 1) \otimes a_2 \mod (x + 1) \otimes \cdots \otimes a_n \mod (x + 1) > 0$。于是直接模拟可以拿 $\texttt{50 pts}$，但是后续并不会优化，先放着。 $\texttt{T2}$ 数据结构毒瘤题。大鱼吃小鱼，判断能否使鱼的体积大于 $k$。依旧不太会做，只是知道尽量吃大一点的鱼的贪心思想，写了一个 `set` 模拟，不知道能拿几分。 $\texttt{T3}$ 简单题，以最后答案的范围是 $[0,999]$ 为突破口，通过答案确定可能的区间。枚举 $x,y$，满足 $\frac{x}{y}$ 已经是最简分数，然后计算可以同乘以的数的个数即可。 $\texttt{T4}$ 像是一个数位 $\texttt{dp}$，而且还需要高精度。直接准备拿 $n \le 6$ 的暴力分以及 $m = 0$ 的点。由于懒得写高精度，于是用 `python` 打表，但是表过大屡次把编译器卡爆，所以最后就打了 $n \le 100$ 的表，不晓得能拿多少。交上去评测了（省略第一次测忘开 `long long` 的惨状），$50 + 30 + 100 + 50 = 230$，还可以叭，该拿的分都拿了（除了最后一题的神必高精度模拟）。 ### $\texttt{2022.10.27}

上午复习数论。

重新推了一遍 \texttt{exgcd}，怎么感觉这么陌生啊这这这....

了解到一个叫做米勒罗宾素数测试的方法，本质是运用费马小定理的逆定理。随机出几个数 x，若不满足 x^{n - 1} \equiv 1 (\mod n)，则可以说明 n 是合数，计算概率可知，若重复 p 次，均通过检测，则只有 (\frac{1}{2})^{p} 使它为合数，代码写起来很简单就不给了。

P1463 [POI2001][HAOI2007] 反素数将数表示成算术基本定理的分解形式后，根据贪心，让小的质数的幂尽量大。不难发现，在该数据范围下，并不需要枚举过多的质数，直接搜索求解。
找出 n 个数两两之间最大公约数的最大值。

倒序枚举最大的最大公约数，然后利用桶判断该公约数出现的次数，一旦大于等于 2 次，则为一个合法解。由于倒序，此时最优，直接输出即可。由枚举方式可知，对于每个公约数 d，分别判断的是 2d,3d \cdots 是否存在，因此由调和级数知时间复杂度为 O(n \log n)。

现在给定一个整数 n,需要找到一个大于 n 整数 m，使得 \mathrm{LCM}(1,2,\cdots,n) \mid \mathrm{LCM}(n + 1,n + 2,\cdots,m)。

按照算术基本定理的分解形式，发现 m 满足 a_i^{\max{\{p_i\}}} \mid m，显然只要满足 m 是其中一个最大的质数的幂次的 2 倍即可。

求 \sum_{i = 1}^{n} \gcd (i,n)。

枚举最大公约数 d，设 x = ad,n = bd(d \mid n)，则满足 \gcd (x,n) = d 时，当且仅当 \gcd (a,b) = 1，也就是 \gcd (a,\frac{n}{d}) = 1，即两数互质，不难最大公约数为 d 时符合条件的个数为 \varphi{(\frac{n}{d})}。所以最后的答案为 \sum_{d = 1}^{n} d \times \varphi{(\frac{n}{d})}。由于 n \in [1,10^9]，所以计算 \varphi 时用 O(\sqrt n) 的复杂度计算即可，即 \varphi(n) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})\cdots(1 - \frac{1}{p_n}) 的表达式。

Minimum Modular 由余数的定义可知，若所有剩下的数 \mod M 均不同，显然最小的 M \in [n - k,\max \{a_i\}]，由数据范围可知我们可以枚举 M。发现当 a_i 与 a_j 同余时，|a_i - a_j| \mid M，所以我们可以预处理差值，然后将 M,2M,\cdots,kM 的数全部进行统计，若在题目允许的修改范围内，那么我们就找到了最小的 M，输出即可。
已知若 x,y \in S，则 \gcd (x,y) \in S。现在给出集合中一定存在的若干个数，需要求出集合的最小大小。

集合的最大数一定是所给中的最大值，于是我们又可以枚举每一个数，判断是否存在。对于一个输入中不包括的数 x，将所有已经存在于集合的 kx 的 k 进行 \gcd 运算，若最后的结果为 1，则说明最后能够得到 x，将其标记后加入答案即可。时间复杂度为调和级数以及外层的枚举，为 O(n \log n)。

求 \sum_{i = 1}^{n} n \% i 的值。

原式可以变为 \sum_{i = 1}^{n} n - \lfloor \dfrac{n}{i} \rfloor \times i = n^2 - \sum_{i = 1}^{n} \lfloor \dfrac{n}{i} \rfloor \times i。后者显然用整除分块加上等差数列求和维护即可，需要注意取模以及数据范围（n 先取模后运算，否则会爆），时间复杂度为 O(\sqrt n)。

\texttt{2022.10.28}

【插播广告】今天是巨佬 \texttt{CENRUIYANG} 的生日，让我们一起祝他生日快乐。把这条消息转发到五个群，就能向他一样爆切 \texttt{IOI} 了（狗头。

重温一下最短路。

拆点是个很好的做法，相当于是将一个点拆成不同状态的多个点，然后分别连边进行建图。

【例】求将任意仅一条边的边权除以二后的 S 到 T 的最短路（保证边权全部为偶数）。

每一条边都为除或不除两种状态，因此可以用 [1,n] 表示未除过的点，[n+1,2n] 表示除过的。连边时只有 (x,y+n),(y,x+n) 时将边权除以 2，另外的 (x,y),(y,x),(x + n,y + n),(y + n,x + n) 边权不变。最后跑一次为原图大小 3 倍的最短路，然后输出 dis_{t + n} 即可。

赛前再次看下模拟退火，~~为了骗分~~。

明天 \texttt{rp++} 吧！

\texttt{2022.10.29}

\texttt{CSP-S rp++!}

开考，\texttt{T1} 多次读错题目，好不容易写完后测了大样例突然发现写假了，这时候离开考已经过去了 1.5h，直接就慌了。

接下来先写了 \texttt{T2}，满分似乎有些细节，于是果断去拿 85\texttt{pts}。写完以后，感觉时间不大够了，便去写了 \texttt{T1,T3} 的部分分，\texttt{T4} 没来得及写。

感觉发挥不大好，但是却发现我只要一慌乱就不能再仔细去分析题目了，所以在 \texttt{NOIP} 之时一定要更加冷静一点。

估分： (55-60)+85+(15-40)+0=155-185，感觉不是卡线就是被线卡。

\texttt{2022.10.31}

补题。\texttt{T2} 写了八棵线段树，然后分类九类过了。

$\texttt{T3}$ 直接判断每个点的出度是否为 $1$ 不就行了吗？当时怎么没有想到。然后利用 `hash` 来重置每个点的权值，当所有可以用的点的权值和和 $\sum _{i = 1}^{n}w_i$ 相同时就可以判断合法了，这样复杂度就降到了 $O(q)$。 ### $\texttt{2022.11.2}

写点数据结构题。

写点构造题。

\texttt{2022.11.3}

GSS2 - Can you answer these queries II 求区间最大子段和（可为空），但是重复数字只算一次。不难想到离线处理，按询问的右端点进行排序。设当前的点为 i，则该数所产生的影响的区间为 [pre_i + 1,i]，因此在更新后求出历史区间和的最值（以之前的一点最多到 i 点的最值）。
P6018 [Ynoi2010] Fusion tree \texttt{01 Tire} 的运用。对于每一个节点，开一个字典树。对于操作三，可以直接通过字典树求出子结点的异或和，由于只有一个父亲，直接单独处理即可。对于操作二，先删除再插入节点，同样的，对父亲单独进行处理，受到影响的是父亲的父亲节点。对于操作一，需要通过模拟可知，加一相当于在 \texttt{01 Trie} 中交换左右节点，因此直接递归求解即可。
P1318 积水面积单调栈，当且仅当左右区域均比其大时会产生积水。可以直接正序倒序处理出两个数组表示从左/右开始的最大高度，然后遍历判断 a_i 与最大高度的最小值的相对大小即可。
P4053 [JSOI2007] 建筑抢修按时间排序后能加就加，不能加时若能够替换原有答案使得更优（也就是说当前修复时间比原有答案的最大值小时），则将其替换。可以使用优先队列或 multiset 实现。

\texttt{2022.11.6}

周末按道理是去教室自习，但是还是来到机房，还翘了数学考试。

上午瞎做了点题目，中午打饭的大伯给了两块肉还说这已经很多了？？？（真的气死）

下午模拟赛。（在机房打题真的会降智嘛，怎么打弱智错误？）

$\texttt{T2}$ 简单数学题，发现要求 $n \times m + (n - 1) \times (m - 1) + (n - 2) \times (m - 2) + \cdots + (n - m + 1) \times (m - (m - 1))$。直接拆括号，化简成 $nm^2 - \dfrac{m(n + m)(m - 1)}{2} + \dfrac{m(m - 1)(2m - 1)}{6}$。然后发现要高精，尝试 `python`，突然意识到要超时，然后又灵机一动写了个 `__int128`，直接水过。然后跳过了 $\texttt{T3}$ 写 $\texttt{T4}$，降智开始了！想了很久就是想不出正解，于是打算骗 $\texttt{69 pts}$，然而第二层 $\texttt{dp}$ 写成了 `for (int j = 1;j < n;++j)`，而应该是 `for (int j = 1;j < i;++j)`。赛时连着对拍一起写挂了，所以没查出来，$\texttt{69 pts} \to \texttt{21 pts}$。最后写 $\texttt{T3}$ 发现是个进制转换，然后无脑模拟。过了样例，提交后就开摆了。赛后发现爆灵，然后发现自己行末的 `;` 竟然打成了 `,`，也就是说条件语句不执行，答案也不会被更新，直接晕倒。更加神奇的是，$256$ 进制我乘的权值竟然是 $255$，再次晕倒。随便改了两下就过了。于是，由于我的降智，$100 + 100 + 100 + 69 = 369 \to 100 + 100 + 0 + 21 = 221$，真的是……无语住了。继续写 $\texttt{T4}$，尝试优化 $\texttt{DP}$，考虑用优先队列，时间复杂度 $O(nm \log n)$，加一个特判就可以拿到 $\texttt{88 pts}$ 的好成绩。发现每层扫 $m$ 次实在有点浪费时间，由于要找到最值，于是将是否类型一样分别考虑然后去最大值，用线段树来优化 $\texttt{DP}$，发现可做。写了一发就过嘞，开心！！！最后时间复杂度 $O(n \log m)$。 ### $\texttt{2022.11.8}

出分了！\texttt{CCF} 果然是脚造样例，不过应该还是拿二等奖（因为没写 \texttt{T4})。

实际分数：\texttt{60+85+60+0=205 pts}。

\texttt{2022.11.9-11.11}

学校举行运动会加上艺术节，当然要去玩啦！

老师在班上说，竞赛要学会取舍啥的，~~怎么感觉在讽刺我捏~~ \texttt{qwq}。

\texttt{2022.11.12}

P3957 [NOIP2017 普及组] 跳房子单调队列优化 \texttt{dp}。
Axel and Marston in Bitland dp[s][op][i][j] 表示以 op 起始，i \to j 是否存在距离为 2^s 的边，然后用 bitset 压位处理。
P4290 [HAOI2008] 玩具取名区间 \texttt{dp}，码量比较大，同时需要注意初始化。
P3049 [USACO12MAR]Landscaping S 普通线性 \texttt{dp}，dp[i][j] 表示 a 的前 i 个与 b 的前 j 个相匹配的最小花费。
Name That Tune 期望 \texttt{dp}，dp[i][j] 表示在听完前 i 首歌花费 j 秒的期望，然后用前缀和进行优化。

晚上打 \texttt{CF}，快速切 \texttt{AB}，\texttt{C} 题贪心的思路非常好想到，但是实现起来细节巨多，一直 \texttt{WA} 一直调，交了 6 发才过，导致浪费了大量时间。用仅剩的 30 分钟去写 \texttt{D}，按位处理，然后调了一半就结束了，降大分。

\texttt{2022.11.13}

学校模拟赛，又一次凉心。

$\texttt{T2}$ 贪心，写完测了大样例发现假了，实际上没看清题目中的一个限制，哎不管了，就先这样。 $\texttt{T3}$ 直接模拟就可以有 $\texttt{40 pts}$，仔细一想预处理每一行可以用倍增。一开始想要设第 $i$ 行从 $j$ 开始经过 $2^p$ 的距离所需的最小花费，由于贪心的思想，每次应该从 `X` 的格子开始计算花费，所以这样设并不好转移。想了一会儿，果断放弃。换一种设法，设 $f_{i,j,p}$ 表示第 $i$ 行从 $j$ 开始花费 $2^p$ 的代价能到达的最远距离，最远点设为 $m + 1$，于是就有 $f_{i,j,p} = f_{i,f_{i,j,p - 1},p - 1}$，于是时间复杂度就降到 $\log$ 级别了。 $\texttt{T4}$ 完全不会，暴力没时间打了。 $\texttt{20 + 14 + 100 + 0 = 134 pts}$，第二题的假算法竟然还有分是我没想到的。 ### $\texttt{2022.11.14}

麻麻生日。

\texttt{2022.11.15}

练习一些树上问题，包括贪心，数据结构和 \texttt{dp}。

Distance to the Path 想了很久的数据结构题，感觉将问题拆分成子树内外进行考虑，是个很妙的做法。写了篇题解。
P2279 [HNOI2003]消防局的设立 \texttt{dp} 和贪心均可做，贪心好写一点，从深度大的节点开始，分别考虑每个节点的儿子节点与父节点。
P3942 将军令上一题的加强版，大致依照之前的思路进行贪心即可。
P3523 [POI2011] DYN-Dynamite 和前两题相似贪心与 \texttt{dp} 相结合，不过由要使最大值最小可知需要二分。
P1084 [NOIP2012 提高组] 疫情控制好想但不好写的树上贪心，外面还要套个二分。
P4281 [AHOI2008]紧急集合 / 聚会三个点两两求 \texttt{LCA}，然后去最优值。
P4092 [HEOI2016/TJOI2016]树用树链剖分维护最大值，不过需要分清楚 \texttt{dfs} 的下标和实际的下标。似乎还有一个离线倒序处理的方式，可以少一个 \log。
P4211 [LNOI2014]LCA 码量巨大的树链剖分题。离线处理所有询问，按端点排序后，用树链剖分与差分相结合。对于一个 i，将链 1 \to i 均增加一，查询时计算 1 \to z 的值即可。
Book of Evil 还是子树内外分开考虑的套路，dp_{u,0/1} 表示以 u 为根的子树内怪物与 u 的最大/次大距离，dp_{u,2} 表示 u 到子树外怪物的最大距离，然后两次 \texttt{dfs} 进行转移。
Centroids 继续换根 \texttt{dp}，设 dp{u,0/1} 表示以 u 为根子树内最大/次大的且不超过 \frac{n}{2} 的子树大小，g_u 表示以 u 为根的子树外最大的且不超过 \frac{n}{2} 的子树大小，然后和上一题差不多按套路转移即可。

\texttt{2022.11.17}

Vitaly and Advanced Useless Algorithms 复习了一道关于 0-1 背包的题目，细节有点多调了 1h，顺便水了一篇题解。
P5017 [NOIP2018 普及组] 摆渡车再次写了这题，在题解的提示下用斜率优化写过这题目。

做点图论相关的题，顺便复习了下缩点。

P4568 [JLOI2011] 飞行路线分层图的思想，也就是所谓的拆点。
P1462 通往奥格瑞玛的道路二分后跑最短路，最大费用最小化就很套路。
P2783 有机化学之神偶尔会做作弊边双连通分量缩点后求 \texttt{LCA}，感觉也很套路，就当复习一下。
P1491 集合位置
P2865 [USACO06NOV]Roadblocks G 两题均和次短路有关，而下面的允许重复走一条边。因此前者每次删一条边后跑最短路，后者遍历枚举每一条未删的边计算 dis1_u + dis2_v + val_i 的最小值。
Too Many Constraints 与 [ABC277Ex] Constrained Sums 都是 \texttt{2-SAT} 的题目，难点都在于将约束条件转换为连边，最后跑 tarjan 是套路。细节很多，调了整整一天。

官方分数线出了，被卡在 \texttt{2=} 的前几名（\texttt{ZJ-OIer} 之痛啊呜呜呜）。不过好在有前 20\%（唯一能区分 \texttt{70 pts}也能够 \texttt{2=} 的 \texttt{OIer} 了），晚上蓝勾到账，咕值排名上升到 \texttt{rk 49} 了，好耶！！！

\texttt{2022.11.18}

学一点之前一直没搞懂的期望 \texttt{dp}。

FAVDICE - Favorite Dice 同 P1291 [SHOI2002] 百事世界杯之旅再同优惠券 Coupons 设 f_i 表示已经扔了 i 面后，还需仍的次数的期望。则 f_i = \dfrac{i}{n} \times f_i + \dfrac{n - i}{n}\times f_{i + 1}，即 f_i = f_{i + 1} + \dfrac{n}{n - i}，再次转换知 f_i = f_{i + 1} + \dfrac{n}{i}。
P4550 收集邮票和上一题有些相似 f_i = f_{i + 1} + \dfrac{n - i}{i},g_i = \dfrac{i}{n} \times (f_i + g_i + 1) + \dfrac{n - i}{n} \times (f_{i + 1} + g_{i + 1} + 1) = g_{i + 1} + f_{i + 1} + \dfrac{i}{n - i} \times f_i + \dfrac{n}{n - i}，直接递推求解。
P2719 搞笑世界杯 f_{i,j} 表示分别剩下 i 与 j 张时的票时，最后两张票相同的概率，则在 i > 1,j > 1 时均为 \frac{1}{2} 的概率转移，注意边界条件的判断。
P3802 小魔女帕琪 7 个一组进行分析且互不干扰，所以共有 n - 6 组 p = (n - 6) \times E(x) = (n - 6) \times \dfrac{7! \times a_1 \times a_2 \times \cdots \times a_7}{n \times (n - 1) \times \cdots \times(n - 6)}，化简一下直接写就行了。

写一道有关矩阵乘法优化的 \texttt{dp}。

P3176 [HAOI2015]数字串拆分写了篇题解。

平衡树下周再看一下吧，希望别鸽。

\texttt{2022.11.19}

打洛谷的 \texttt{NOIP} 模拟赛。

第一题容易发现答案为 2/3/4，2 非常容易判断，用二位前缀和处理 3 / 4 的情况可以拿到 \texttt{80 pts}（但是赛后证明数据过水，特判能直接过）。赛时又想到一个树状数组维护左上角和右下角的矩形的情况，由于折点不一定是整数，所以还要加一个二分判断。写了好久过了大样例，应该没啥问题。

第二题 ty = 1 的点异常好做，直接计数 \texttt{dp}，但是因为忘记取模调了好久。对于 ty = 2 的没啥想法。

第三题，不会，直接写了暴力。

第四题，没啥想法，也是暴力。发现第二个子任务可做，但是觉得有点烦就没写。

最后得分 100 + 50 + 30 + 8 = 188，\texttt{rk 42}，感觉还行（但是感觉难度偏高），第三题有 \texttt{30 pts} 真不错。

\texttt{2022.11.20}

校内模拟赛。

**【简要题意】** 只能将排列从上往下 $k$ 层进行归并排序，其余只能单纯的合并，求能使其有序的排列数量。最多只能递归到第 $k$ 层，所以二分处理，到达该层时的某段区间为 $[l,r]$，当前还有 $m$ 个数可以选，则这一段区间可以选的数量为 $C_m^{r - l + 1}$，处理完后剩下的数减少 $m$ 个。当然，需要处理未到第 $k$ 层时就出现 $l = r$ 的情况。所以说只需要去处理出组合数，然后就能递归求解，时间复杂度为 $O(n + tn)$。 $\texttt{T2}$ 旅行。 **【简要题意】** 从一张单向图中选若干点，使得存在一条 $s \to t \to s$ 的路径且点权最小。应该是 $\texttt{dp}$，但是不知道如何处理来回经过重复点的情况。最后就写了一个最短路与状压来拿了 $n \le 10$ 的部分分。 $\texttt{T3}$ 教室。 **【简要题意】** 每一个点的权值为 $0/1$，状态为 $0/1/2/3$。状态为 $0$ 时表示权值一定为 $1$，状态为 $i(i \in [1,3])$ 时表示点左侧相关的三个点（左/上/左上）至少有 $i$ 个点的权值为 $1$时该点的权值才有 $\frac{1}{2}$ 的可能为 $1$。求所有点权和的期望值。按顺序扫，对于每个点的情况容斥求解，当然也可以时分类去写期望值，写成了一个 $O(nm)$ 的程序，能过第一个样例，但是怎么都过不了第二个，一直没想通所以最后就没改了。与巨佬 [$\texttt{CENRUIYANG}$](https://www.luogu.com.cn/user/115271) 讨论后总算知道问题出在哪里。每个点的计算不能简单的依赖左侧三点的概率，因为之前的点可能会导致某些 $1$ 不可能出现，总算明白正解为啥是复杂的状压加轮廓线 $\texttt{dp}$ 了。 $\texttt{hack}$ 数据，关注右下角的点。 ``` 2 3 0 1 1 3 3 1 ``` $\texttt{T4}$ 数树。 **【简要题意】** 设 $dis(x,y)$ 表示两点间的最短路径。给定一棵树，求互异三元组 $(a,b,c)$ 满足 $dis(a,b) \le k,dis(a,c) \le k,dis (b,c) \le k$ 的个数。一看就很复杂，写了个预处理 $LCA(x,y)$ 的 $O(n^3)$ 暴力和处理链的 $O(n^2)$ 就没有再多突破了。最后得分：$100 + 40 + 30 + 50 = 220$，没有挂分这是好的，但是没写出 $\texttt{T2}$ 这是糟的。 ### $\texttt{2022.11.22}

信心赛，四道题后来都在洛谷上找到了。

P1161 开灯易知 x \oplus y \oplus y = x，所以全部异或起来即可。
P1174 打砖块 \texttt{50 pts} 的 \texttt{dp} 十分好写，dp_{i,j} = dp_{i - 1,j - s} + sum_{i,s}，处理一个前缀和即可。这题就麻烦在遇到 Y 时只赚不亏，所以可以“借”子弹然后归还（然而前提是能够借到）。打的时候过了样例，但是测的时候发现还是写错了。
P1950 长方形只要找到不重复统计的方式，然后直接单调栈优化即可（机房好像还有人写出了 \texttt{dp} 做法）。
P1462 通往奥格瑞玛的道路前几天刚做过，直接二分加上最短路。

最后得分，100 + 50 + 100 + 100 = 350。

\texttt{2022.11.23}

考前最后一场模拟赛。

\texttt{T1 seg}

【简要题意】n 个点总共组成 \frac{n(n + 1)}{2} 条线段（可能退化成点），线段可以存在或不存在，求有多少种线段存在的方案满足能够最大化选择 k 条线段使其互不重叠。

基于贪心思想的计数 \texttt{dp}。用 dp_{i,j} 表示 [1,i] 选择 j 条线段，第 j 线段的右端点选在 i 的方案数。对于 \forall l \in (p,i] 的所有线段，对右端点进行分类。若 r \in (i,n) 这些线段在之前已经被计算过，由于往后进行 \texttt{dp}，不需要重复计算；有一条 r = i 的可选线段的方案数为 2 ^ {i - (p - 1) + 1} - 1 = 2 ^ {i - p} - 1；r \in (i,n] 的线段，即使存在此时也不选择，方案数为 2 ^ {(i - p) \times (n - i)}。预处理 2 的幂次即可。

\texttt{T2 calc}

【简要题意】求 [1,n] 中不能被 \forall i \in k,a_i 中整除的数的个数（a_i 两两互质）。

写递推式，f_{n,k} = f_{n,k - 1} + \lfloor \frac{n}{a_k} \rfloor - f_{\lfloor \frac{n}{a_k} \rfloor,k - 1}。由数论分块可知，不同的下取整的数不会太多，所以直接写了记忆化。交上去时 80，看了题解发现大于某一个数时可以不被记忆化而直接被计算，所以可以用数组代替 map，节省空间与时间。

\texttt{T3 ball}

【简要题意】给定一个长度为 n 的 01 串，进行区间 0 \to 1,1 \to 0 的操作，每次操作保留，然后进行查询最长的 00 \cdots 011 \cdots 1 的串的长度（可以没有 0 或 1）。

线段树维护区间两个端点最长同色串的类型与长度，区间两个端点最长 01 或 10 串的长度，区间最长 01 与 10 串的长度。合并时处理完端点后考虑左右两个区间的中间部分的答案对整个区间产生的影响。区间进行翻转直接打标记即可，然后下传的同时改变串的类型，交换 01 与 10 串的答案即可。赛时没调出来，只交了一个暴力 \texttt{qwq}。

\texttt{T4 array}

【简要题意】构造数列 A，方法为：不断重复 k 次将 \rm{Mex\{A\}} 插入 A 末尾，然后将这 k 个数的和插入 A 末尾，以此类推。求 n 的数列中的位置。

没想法，写了暴力。赛后看了题解还是不会，只知道是数学推式子题。

最后得分，100 + 80 + 20 + 20 = 220。

\texttt{2022.11.24}

做做 \texttt{NOIP 2020}，并借题复习一下最后一块--字符串算法。

P7114 [NOIP2020] 字符串匹配预处理前后缀出现奇数次的字符数量，然后枚举 AB，由于只有 26 个字母，在判断 C 时直接用树状数组求出符合条件的 A 的个数，枚举 AB 出现的次数采用了哈希。最后发现开 O2 才能过，由于现在比赛自开 O2，所以就没事了。
P6739 [BalticOI 2014 Day1] Three Friends 哈希判重，唯一的坑点就是多解是指得到的 S 不唯一而不是方式不唯一（可能多种方式均得到同一个 S）。
P3538 [POI2012]OKR-A Horrible Poem 若 f(l,r - len) = f(l + len,r)，则 len 为一个可能的循环节，所以线性筛预处理每个数对应的最小素因子即可。

总结一下哈希（hsh 表示哈希值，pw 表示权值）：

从 s 中截取 s[l:r]，哈希值为 hsh_r - hsh_{l-1} \times pw_{r - l + 1}。
将 1. 的计算方式编写为函数 f(x,y)，将 s 中的 s[sx:sy] 与 s[fx:fy] 合并，哈希值为 f (sx,sy) \times pw_{fy - fx + 1} + f (fx,fy)。
不要忘记 pw_0 = 1 的初始化。

\texttt{2022.11.25}

练习骗分/调试小技巧。

打表洛谷日报《浅谈打表与其技巧》。【注意 \texttt{CCF} 的代码长度上限是 100KB】

具有一般性的，通过分块打表来缩减表长，将搜索与表相结合，从而优化代码。

P2567 [SCOI2010]幸运数字搜索出幸运数只有 2000 个左右，因此可以通过这些幸运数进行打表，块长设置在 2 \times 10^6 较为合适。
P4318 完全平方数 5 \times 10^5 的表长加 O2 终于过了。如果想要不吸氧并且在合理长度内，可以将表同减某一个数以缩小长度，最后加上即可。

对拍

防止 .bat 文件出错，写成在 Dev-C++ 内的形式。

#include<windows.h>
using namespace std;
int main(){
    while(1){
        system("data.exe");
        system("bf.exe");
        system("sol.exe");
        if (system("fc bf.out sol.out")) break;
    }
}

模拟退火重做了 P1433 吃奶酪不过只拿到一半的分，不管了，会这个方法就行。
clock () - st < 0.9 * CLOCKS_PER_SEC 卡时，注意前面单位是毫秒，后面是秒。
应试技巧看了看这篇博客。

好了，写完了，明天比赛加油吧！\texttt{rp++!}

\texttt{2022.11.26}

要去打 \texttt{NOIP} 了。

预估 $76 + 15 + 0 + 8$，实测第二题的暴力也写错了，于是变成 $84 \texttt{pts}$ 滚粗。比赛开始前想的是写完第一题就去打暴力，但是实际却是死磕第二题，然后没时间写暴力。退役前的最后一场比赛算是完全得崩了。【要是当是努力调完 $\texttt{T1}$，后面直接写部分分，那么 $100 + 30-50 + 35+ 8$ 并不是问题，估计也能拿个 $1=$ 了，现在连 $2=$ 都不保……】【upd】好叭，还有二等，距离一等就差在了写挂的 $\texttt{T2 T3}$ 的暴力分上。 ### 后记不断拼搏的 $\texttt{OI}$ 生涯算是结束了，不知道高三这年会不会来玩玩。【结局：高三还是来玩并且圆梦 $\texttt{1=}$】一些小结写到语文随笔里了（不知道语文老师能不能接受我的“胡言乱语”），啥时候搬点过来。