2025 年 2 月日祭

2025.2.8 水讨论区

今日歌曲：Bigger Than The Whole Sky

今天洛谷讨论区关闭了。（以后不能水讨论区了。）

这个寒假，什么也没干。一看进度，已经和初二的差不多。但是他们第一遍拉得挺快，估计效果不大。

我如果现在回去，在那边又吃不饱。于是，就只有多肝一肝，把之前的进度补上来。

晚上打ABC392。

• [Atcoder ABC392E] Cables and Servers

  略考细节的题。先找连通块，之后再找每个连通块中的返祖边（即无用的边），再把连通块连通即可。

  （可是这题我赛时AC，后来突然想到一个hack。还没改，烦死了。）

2025.2.9 终于战胜

今日歌曲：Holyground

综合题1。

• [Gym 103466I] Space Station

  神奇搜索题，暴搜+剪枝+略微组合数学即可。

  神奇卡常题目，拼尽全力，2700ms+，终于冲进3s。

• [Gym 101982D] Count The Bits

  很普通的一道DP题，可是赛时都在想组合数学。

  表示到第 位模 的值为 的数中 的数量， 表示到第 位模 的值为 的数的数量，直接转移即可。

• [Gym 102428F] Fabricating Sculptures

  神奇DP题。最开始看题解都没看懂，一是自己确实不理解是怎么算的，二是题解写得比较简略，看了好久才看懂。

  设 表示从上往下一层层放，当前一共放了 个，最下面一层放了 个的方案数。有方程 （希望没写错）。将这个式子拆开再维护前缀和即可。（开了long long见祖宗。）

• [Gym 104172F] Sum of Numbers

  很有趣的一道题。很容易发现，两个相邻字符串长度之差（的绝对值）为 或 。暴搜即可。

  赛时的想法是，将原字符串平均分，再给 或 的偏移。可是偏移少了一些，虽然没 TLE 但一直 WA，拼尽全力无法战胜。

  赛后再改一改，拼尽全力终于战胜。

今天本来说再补补昨天的 F，改改昨天的 E，结果今天的第三题看半天看不懂，昨天的 E 和 F 都没做。

最终今天做了四道题。

感觉心态有点崩。（尤其是看第三题的时候。）

……

2025.2.10 放弃即可

今日歌曲：Peace

综合题2。

今天还做出了一道题。

• [Gym 100861E] Extreme Programming

  看了题解真的好简单。首先我们先确定这些问题的顺序。推推式子，排序即可。现在，我们不用考虑顺序，只用直接背包，找出最大的 与最小的 即可。

  可是这道题不知道哪里写挂了，WA on test 15。**放弃即可**。

• [Gym 100217I] Sharing the Sweets

  分拆数板子题。（可是我不会。）写板子即可。

  分拆数 OI Wiki。

• [Gym 100202A] Little Brackets

  这题着实简单。设 表示放了 个括号，当前高度为 ，是否到过最高点（深度为 ）的方案数。直接转移即可。

  可是赛时想多了，一直在想组合数学。或许先设方程再推会好一些。

  赛时还因为多测不清空挂了四发。

今天还举办了 CWOI ER 2 & 1 > 2 Round，感觉对于他们还是太难了。

（今天字符数破 了。）

2025.2.11 放弃即可

今日歌曲：Pink Pony Club

模拟赛 。

• B - 刀言刀语 （[洛谷 P6864] [RC-03] 记忆）

  今天给的题解以及同学讲解的都是非矩阵做法，可是听得迷迷糊糊。一下午尝试乱搞做法，结果没搞出来，最后，一道题都没改出来，**放弃即可**。晚上终于学习了矩阵，基本学懂了，这才发现矩阵有多好用。之后又看了这道题的矩阵+线段树做法，终于基本懂了。

  将这些数据打包成矩阵：。对于操作一，等同于 。对于操作二，等同于 。对于操作三，若是恢复某个操作，则与操作一二相同；若是删除某个操作，则将这个操作设为单位矩阵（），不会对答案产生影响。用线段树维护每个操作对应的矩阵，区间求和（求积）即可。

  这道题记得比较详细，毕竟是第一次接触矩阵。

• C - 刀妙构造

  题目：给定一个长度为 的排列 ，通过尽可能少的操作，使得 。判断是否有解。若有解，输出具体的操作。操作的定义：选择 满足 ，交换 与 。

  题解：原本就满足 的位置将原数组分割成若干个块。对于每个块，若是目标的一种排列则有解。设当前块为 ，则依次把数 移到位置 。要注意的是，在移动的过程中，可能会使得其它的 成立。所以我们将这些即将成立的位置先进行偏移，再将当前的数移到目标位置即可。

  扩展：尝试在 的时间复杂度内求出有解的排列个数，对 取模。

这几天强度还是比较高，因为跟进度跟得有点吃力了。今天晚上眼睛疼，难受。

2025.2.12 罚时吃饱

今日歌曲：two years

今天上午VP Codeforces Round 1004 (Div. 2)，下午改Codeforces Round 1004 (Div. 1)。上午C题因为少判了一个条件，罚时吃饱了。

• [Codeforces 2066A & 2067D] Object Identification

  神奇交互题。观察到一个性质：对象 的答案可能是 ，但对象 的答案不可能是 。

  若 不是 的一个排列，一定可以找到一个不在 中的数 ，对其与另一个不同的数询问。若是对象 ，因为 没有向任何点连边，所以答案一定为 。若答案不为 ，则是对象 。

  若 是 的一个排列，那么找到满足 的 。询问 与 。若是对象 ，那么两个答案应该是相等的，并且都 （因为 ）。然而如果是对象 ，那么当 ，不可能同时存在一条长度至少为 的 到 的路径与一条长度至少为 的 到 的路径（因为 ）。综上所述，若两个答案相等并且都 ，则是对象 ，否则是对象 。

  按照题解模拟即可。

• [Codeforces 2066B & 2067E] White Magic

  这题似乎挺简单的，只是赛时看了一眼但是没多想。

  首先可以注意到，没有 的子序列一定是合法的，有两个及以上的 的子序列一定是非法的。所以要么选所有非零元素，要么选所有非零元素与一个 。

  若是选一个 ，显而易见，选最左侧的 是最优的。于是判断这么选是否合法即可。

• [Codeforces 2066C & 2067F] Bitwise Slides

  很有意思的 DP 题。

  我们根据题意可以得出，对于时刻 ，记 ，有 。于是对于某个时刻，有这三种状态：。设 表示这三种状态的情况数，经过推导（具体过程略），可以得出 。发现可以滚动。由于值域较大，用 map 维护 DP 即可。

• [Codeforces 2066D1] Club of Young Aircraft Builders (easy version)

  有趣的组合数学题。

  因为下面的楼层并不会影响上面的楼层，所以从下往上考虑。对于某一个高度，丢飞机的次数最多为 ，假设它实际丢 个，则有 种情况。所以设 表示到了第 层楼，已经丢了 个飞机的情况数。有转移方程 。

  答案为 。直接 DP 即可。

  扩展：求证答案为 。

今天晚上略水……没做题。但是今天一天综合下来……还将就吧。

2025.2.13 笑点解析

今日歌曲：evermore

今天 jmr 终于回来了。

今天学习了李超线段树。

• [洛谷 P4097] 【模板】李超线段树 & [HEOI2013] Segment

  刚开始学李超线段树，觉得挺简单的。其实它跟吉司机线段树有点像，只是维护的东西要少一些，并且代码更好写。

  对于每个节点，考虑维护在它中点处的最高线段编号，那么用类似于吉司机线段树区间取 ：若当前线段完全优于原有线段，那么直接替换；若当前线段完全劣于原有线段，那么直接舍弃；若当前线段与原有线段有交点，那么递归更新当前线段较大的那一段。对于查询，直接把路径上所有的线段取 即可。时间复杂度

• [洛谷 P4069] [SDOI2016] 游戏

  纯堆码量的题。首先这题一眼树链剖分，一眼李超线段树。这题算是很基础的树剖，只是套的是李超线段树。

  于是 LCA + 树剖 + 李超线段树 就算是码量炸弹了。也许树剖都这样，只是我没怎么写过。所以……先把模板题写了再说。

  • [洛谷 P3384] 【模板】重链剖分/树链剖分

    第一道真正意义上的树剖。之前倒是写过一个有点树剖思想的贪心（但那个好像是长链剖分）。

    一共交了四发，笑点解析：前三发线段树没 pushup。由于当时另外没找到问题，于是我严重怀疑是线段树的问题。然后用那个线段树，写了一个线段树的板子，一测挂了，才发现是没写 pushup，糖丸了。

    第一次写树剖，稍微参考了一下题解代码，但整体还是自己在写。树剖其实挺好理解的。

  写完模板题，该写这道题了。这道题从下午就开始写，一直调到晚上都没调出来，只有明天再补了。

今天 把 给 了。适度阻止竞赛低龄化是有道理的，没必要小学就开始竞赛，而且有些 真的很没数值；但另一方面，以后的分数线会有所上升。

今天晚上 让我们帮他帮另一个人验初赛题。那题……一言难尽。

2025.2.14 绝世好题

今日歌曲：Red Wine Supernova

今天%你赛，。

• B - permutation （[Codeforces 1827B2] [加强版] Range Sorting (Hard Version)）

  绝世好题之神秘计数（？）题。

  又是一道正难则反。容易发现，答案为：

  考虑枚举 满足 ，那么 。显而易见， 是 右侧第一个比它大的数，那么 ，其中 满足 是 左侧第一个比它大的数， 是 右侧第一个比 小的数。维护即可。

  这题……题解给的用 set 维护，可惜常数太大，被 卡掉了。他又给了个链表的实现，不想看，于是自己开始研究。

  由于要求的值都是最近的最大/最小值，所以考虑使用单调栈维护。 与 都非常好求，可是如何求 是个问题。

  当时做这道题的时候自己没想出来，后来看原题题解区才懂。做法是，对于前文所提到的 ，维护 个集合 ，满足 。接下来倒序遍历 ，对于每个 ，顺序枚举 ，将单调栈中 的数弹出，栈顶元素即为 。在将每个 操作完后，将 加入单调栈。正确性证明如下（部分摘自原题题解）：

  记 表示查询 右侧第一个比 小的数。（ 含义同上。）若这个询问弹出了 ，那么 的答案显然不为 。现在需要证明 的答案不为 。

  • 若 ，因为 ，所以 可以作为答案，答案不可能是 。

  • 若 ，因为 ，所以答案不可能是 。

  • 若 ，那么 ，否则 右侧第一个比它的的数不可能是 ，所以 ，答案不可能是 。

  终于证完了。按上述步骤维护即可。

  这题本来就有一定的思维难度。如果用单调栈，这道题的思维难度就更高了。如果用有的数据结构（比如 set），倒是好想好写，可是 卡常。

因为今天一下午加晚上一直苦攻 T2，所以昨天的题还没来得及补。

今天写得很晚了，准确来说已经第二天凌晨了。今天就到这里。

2025.2.18 无处不在

今日歌曲：I Forgot You Existed

“我无处不在。”——

今天在改游戏那道题，最终决定重构！

2025.2.20 笑点解析

今日歌曲：The Archer

今天还是在改游戏，最后终于还是改出来了。笑点解析又来了。

• 在 里计算了 。

• 在线段树中的编号与实际编号混淆了。

• 另外还有一些很糖的低级错误，比如右儿子写成 之类的。

2025.2.22 显而易见

今日歌曲：wish you were gay

。

• A - 怎么又是先增后减 （[Atcoder joisc2014_b] [JOI Day2 T2] たのしい家庭菜園）

  论赛时代码只与正解相差两行，赛时是有多糖。

  显而易见，一个数要么放左边，要么放右边。若放左边，则需要交换当前数与左边逆序对的个数，右边同理。显而易见，取较小的一侧的答案。用数据结构维护即可。

2025.2.25 数组开小

今日歌曲：mirrorball

• [Codeforces 241E] Flights

  神秘又简单的差分约束。显而易见，我们只关注在 到 路径上的点，并且 到路径上每个点的距离都是唯一的。那么有 。差分约束即可。

  做的时候由于数组开小了，挂了若干发，也是糖丸了。

• [洛谷 P1993] 小 K 的农场

  模板题。

2025.2.27 联合省选

今日歌曲：It’s Nice To Have A Friend

今天写了一点联合省选 2025 游记。

• [洛谷 P4926] 倍杀测量者

  模板题。

• [洛谷 P2474] [SCOI2008] 天平

  不怎么板但码量极小的题。

  我们要求的是满足 的无序二元组 的个数。由于我们并不知道 中的具体数值，只知道部分大小关系，又发现我们可以把上述和式转化为差式，所以维护两个数的差的范围即可。