2023/11/27(#1)：点燃星，亲手点燃黑暗森林的火星

强度！强度！

我是星
利剑开刃寒光锋芒的银星
绝不消隐
不回顾永难再折返的故园的光阴
决意前进
点燃星
亲手点燃黑暗森林的火星
蒙昧初醒
而我却轻声告别这新生的黎明

不像这种加训方式的创始人做的都是神仙题，我做的全是水题……

然而即使这样还是拖到了次日（本文于 2023/11/26 动工），效率还是要提升！

[ICPC 2023 Nanjing] Counter

Portal.

按照时间排序，模拟即可。代码。

[ICPC 2023 Nanjing] Trapping Rain Water

Portal.

本身是个经典问题。set 维护所有的极值点，线段树查询区间最大值和区间和，每次修改直接暴力删除极值点，计算贡献即可。时间复杂度 $O(Tn\log n)$。代码。

[ICPC 2023 Nanjing] Equivalent Rewriting

Portal.

如果一个赋值操作最后将当前点的值确定，那么这个点向其它赋值过这个点的操作连边。如果拓扑序不唯一，那就有解。代码。

[ICPC 2023 Nanjing] Primitive Root

Portal.

解的形式形如 $(ip+1)\oplus (p-1)$，然后发现答案大概是 $m/p+1$，边界暴力判断即可。代码。

[CF1166D] Cute Sequences

Portal.

容易发现 $b=a\times 2^{k-2}+r_2\times 2^{k-3}+\cdots +r_{k-1}+r_k$。

看上去很像一个二进制拆分状物。反手先将 $r$ 全部减掉 $1$，然后贪心填每一位即可。代码。

「EZEC-14」众数 II

Portal.

发现如果一个数 $k$ 想要作为区间最小众数，那么这个区间必须以它开头，且不能碰到下一个 $1$ 或者在下一个连续出现 $k$ 的位置结尾。

我们计算一个数组 $w$，$w_i$ 代表以第 $i$ 个 $a_i$ 中的 $k$ 作为结尾段的左端点个数。发现 $w$ 的更改是区间加的形式，并查集维护区间的右端点即可。

总结一下，区间众数为 $k$ 的贡献为 $k\sum_{i=1}^n w_i\max\{0,a_i-k+1\}$。维护 $\sum w_i$ 和 $\sum w_i a_i$ 即可计算。代码。

「EZEC-14」终点

Portal.

先考虑 $fa_i<i$。规定 $fa_1=2$，求解 $x$ 时令临时父亲 $y=1$，在 $y$ 和 $fa_y$ 中寻找距离为偶数的点来找到中点，然后将临时父亲改为这个中点，$\log$ 次询问即可得到结果。

对于任意树的情况，我们需要先找到一组相邻的点。先询问 $1$ 和所有点的中点，找到和 $1$ 能取中点次数最多的点不断取中点即可得到一个和 $1$ 相邻的点。

使用 BFS 处理一开始所述的迭代过程。在求解一个点的父亲时需要保证它到根的路径上的所有点（除了自己）的父亲都是已知的，中点 $y$ 为一个不确定父亲的点时将询问挂在 $y$ 上，然后每次确定一个点的父亲处理所有挂在它上面的询问即可。代码。

[BJOI2018] 双人猜数游戏

Portal.

Alice 和 Bob 怎么这么聪明啊？？

小学时看过这种问题，然后现在在 OI 中见到了它。

设 $f_{i,j,k}$ 表示在第 $i$ 个回合，人能否确定答案是不是 $j,k(j\le k)$。

以 Bob 为例，情况只有三种：

• 如果这个人在它的上一个轮次已经知道答案，那么它这个轮次也知道，即 $f_{i,j,k}\leftarrow f_{i-2,j,k}$；
• 从未知推出已知：
  • $f_{i-1,x,y}(x+y=j+k)$ 中，他的对手仅有一个 $f_{i-1,j,k}$ 不知道，那么他自己可以确定 $j=x,y=k$；
  • $f_{i-1,x,y}(x+y=j+k)$ 中，他自己的上一个轮次只有 $f_{i-2,j,k}$ 不知道，那么他自己可以确定 $j=x,y=k$；
• 从已知推出已知：$f_{i-1,x,y}(x+y=j+k)$ 中，他的对手上一回合只新增确定了一个 $f_{i-1,j,k}$，那么他这回合就能确定 $f_{i,j,k}$，$(j,k)$ 是不是答案跟对手上一次的回答是一致的。

$500$ 以内可以找到答案，直接 DP 即可。代码。

间隔

时间来到了 11/27 凌晨。

马克在群里表演了一小时 AK CF Div.2，太牛逼了。

[BJOI2018] 链上二次求和

Portal.

我们有：

$$\begin{aligned} ans&=\sum_{k=l}^{r}\sum_{i=k}^{n}S_i - S_{i-k}\\ &=\sum_{k=l}^r\left(\sum_{i=k}^nS_i-\sum_{i=0}^{n-k}S_i\right)\\ &=\sum_{k=l}^r(SS_n-SS_{k-1}-SS_{n-k}) \end{aligned}$$

然后因为是区间修改，树状数组维护三阶和四阶前缀和即可。注意链上的点可以 $x>y$，代码。

[APIO2016] 最大差分

Portal.

子任务 $1$ 很简单，直接一路问过去就是 $\left\lceil\frac n 2\right\rceil$ 次询问次数。

子任务 $2$ 的询问代价与询问的值域有关。先问出 $a_1,a_n$，此时答案的最小是 $\left\lceil\cfrac{a_n-a_1}{n-1}\right\rceil$。将值域序列分块，每块的大小是最小答案，依次查询每块的答案，只有块内最小值减去之前的最大值才可能是答案（块内自己没有答案，因为块的长度小于最小答案）。代码。

插曲

大意了，发现自己好像一个上午什么都没干，就写了两道大水题（11/27）。

听了一些比较奇怪的歌。

下午和晚上怎么办啊。

[CF1063F] String Journey

Portal.

可以发现答案最大只有 $O(\sqrt{n})$，且 $t$ 的长度一定是 $ans,ans-1,\cdots,1$。

那么枚举答案，设 $f_{ans,i}$ 表示当前答案为 $ans$ 时以 $i$ 开头的后缀是否可行。指针 $i$ 从后往前扫 $s$，维护一个哈希表，向其中插入长度为 $ans-1$ 的不与 $[i,i+ans-1]$ 重叠的子串（前提是它的后缀是合法的），

使用 bitset 来实现哈希表，然后搞一个比较小的模数，代码。

无知时诋毁原神

Portal.

只会做水题。

打表发现 $n$ 为偶数时无解，奇数时构造 $a_i=n-c_i-1,b_i=(c_i-a_i)\bmod n$ 即可。代码。

[CF628D] Magic Numbers

Portal.

只会做水题。

直接数位 DP 即可。代码。

[CF1063C] Dwarves, Hats and Extrasensory Abilities

Portal.

只会做水题。

尝试简化问题。我们将所有点放在一条直线上，然后直接二分就行。代码。

ED

不要太晚，杂题差不多得了，晚上还有其它任务。

但感觉啥都没做啊！！希望之后能够有所改善吧！！

同学每天都好假……一个上午一套 AGC/Div1 的说自己摆的都是什么意思。

其实也好，感谢大家的暴卷逼着我不再那么摆烂。

让命运继续轮转下去吧。不要昨天立下的誓言今天就忘记啊！！