2025 年 3 月日祭

2025.3.1&2 正常说话

这两天参加省选。这里用正常的说话方式补充一些有关考试题目的内容。

• [洛谷 P11830] [省选联考 2025] 幸运数字

  钦定中位数为 ，设可重集中小于 的数的个数为 ，等于的是 ，大于的是 ，那么有 ，所以 。为了让 尽量成为中位数，那么考虑让 尽可能大，即能取 的都取 。同时可以得到 的范围，便可判断。用差分维护即可。

• [洛谷 P11833] [省选联考 2025] 推箱子

  先考虑打一个暴力，随后发现是区间覆盖（覆盖成 ，其中 是给定值， 是下标。）与区间查询。线段树维护即可。（可是我不会告诉你我写的双 可能要挂分。）

2025.3.4 难度偏高

今日歌曲：The Lucky One

今天补了一下 USACO25JAN，铜组难度感觉偏高啊。

• [洛谷 P11667] [USACO25JAN] Astral Superposition B

  思维题。先处理 B，这两颗星星一定一颗在当前位置，一颗在左上方对应的位置。接下来处理 G，如果当前位置能够由已有的星星移动而来，则忽略；否则当前位置需要一个星星。即可。

• [洛谷 P11672] [USACO25JAN] Table Recovery S

  这题一直没改，今天终于改了。先统计出每个数出现了多少次，仅出现了一次的两个数中的一个便是第一个数。又由于第一个数所在的行/列中的每个数的出现次数是不重复的，于是就可以根据第一个数推出整个表格。比较两个答案中更小的一个输出即可。

2025.3.6 正难则反

今日歌曲：Naked In Manhattan

今天中午 C 老师请吃饭，回来就出省选成绩了。省选总分 ，折合 ，。（其实一共也就 个初中生。）

今天略水。

• [洛谷 P11672] [USACO25JAN] Reachable Pairs G

  有趣的正难则反。对于 操作，相当于把当前点换成一个超级原点并不参与计数。所以考虑倒推，先建边（并查集合并）再加贡献。具体地，对于一条边 ，若：

  • ：由于两个点都是超级原点，直接合并 所在的块。

  • ：当枚举到 时合并 所在的块。

  • ：当枚举到 时合并 所在的块。

  枚举到一个点再加入贡献即可。

2025.3.8 打表可得

今日歌曲：Starlight

。

• A - 114514

  题目：定义函数 ，其中 是一个长度为 的序列。这个函数的值 满足：

  • 的长度为 。

  • 中的元素互不相同。

  • 。

  • 是满足上述条件的序列中，字典序最小的。

  现给定 ，求有多少个序列 使得 。

  题解：__打表可得_，每个位置可能的值是独立的，即对于任意一个位置 ， 的取值集合不会随其他值的改变而改变。设 表示值 是否出现过，那么对于 的取值范围就是 ，其中 满足 且 $vis{l - 1} = 0$。并查集维护即可。

• C - 深黯「军团」

  题目：给定 与一个长度为 排列 。计算从 开始的接下来 个排列的逆序对个数之和。

  题解：神秘数位 DP。这题赛时还是想到了许多，但是考试时误认为 的较高位不会改变，所以挂成 分（数据好水）。

  赛时想到了通过求一个排列的逆序对来算排名，也想到了要求的就是排名在一个区间内的排列的逆序对数之和，还**通过打表**想到了全排列的逆序对个数的 DP，甚至还想到了类似于阶乘进制的东西，可是因为不会康托展开而没写出来。

  具体地，将 与排列 康托展开。由于康托展开的值的数位之和就是逆序对个数，所以答案为 ，其中 表示 的数位之和。对于重复的部分，直接 DP 即可。

2025.3.11 观察样例

今日歌曲：Getaway Car

要改名了。今天 VP Codeforces Round 1008 (Div. 2)，打得烂的一匹，最开始只做了 A 和 B，不过幸好在 2:28 把 E AC 了，不然今天晚上整个人都不好了。

• [CodeForces 2077A & 2078C] Breach of Faith

  赛时一直在求 ，然后就被卡死了。

  事实上，发现 更好求一些。。显而易见，把最大值作为 即可不重复。排序即可。

• [CodeForces 2077B & 2078E] Finding OR Sum

  神秘交互题。以下均讨论八位整数。观察样例发现，询问 似乎比较有用，可以直接得到 。再根据直觉，考虑询问 ，将得到的答案 再减去 就可以得到 的贡献。为了不让每一位的贡献重叠，我们便想到空一个位置放一个 。这样，我们就可以根据这些数位的贡献来算出这些数位的和（指 对应数位之和）。剩下未知的数位也便可以根据 与已知的数位求出。显而易见，求答案时我们并不在意当前数位具体的值，只在意数位和。所以对于 的每一位只用分讨 或 即可。

  这种题确实挺直觉的，个人觉得也比较靠运气。比如我 C 想了半天就是想不到，这题基本是看一眼就有点想法而且就对了，甚至还是一发入魂。

2025.3.15 嗨克数据

今日歌曲：This Is Why We Can’t Have Nice Things

。

• D - 完美的答卷

  题目：给定长度为 的数组 ，设 ，求 。

  题解：本题数据过水，以至于赛时对拍拍出了问题但是交到 OJ 上过了。赛时这题也想到了许多，可是逻辑并不清晰，最后还是看了题解并与 dpfs 讨论才想出了以下的解法。

  钦定 是一个区间的最大值， 是这个区间的最小值，且 。设 表示 左侧第一个比 大的位置，则 ，且 在 的单调（递增）栈中，单调栈 + 01trie 维护即可。可是，上述两个集合的交集不一定从 开始，所以对于 trie 树中的一个节点 ，维护 表示经过该点的数的下标的最大值，便可以解决。可是删除又成为了一个问题。考虑用 vector 暴力维护每个 的历史值，理论上时间复杂度不变，只是常数巨大。

  改完之后，就开始造 hack 数据了。似乎有用但不多。

2025.3.18 极限 AC

今日歌曲：Paper Rings

今天 VP Codeforces Edu Round 176。由于准备 VP 时 CF 还在系统测试，所以并不算严格意义上的 VP。最后一共做了 4 道，而 D 是在 VP 1:54 时才 AC，此前还有 3 发罚时。也是极限 AC。

• [CodeForces 2075C] Two Colors

  先将 排序。发现对于某一种颜色，能够与其搭配的颜色都是连续的一段。所以前缀和并动态维护能够搭配的区间即可。注意略特判 的情况。

• [CodeForces 2075D] Equalization

  注意到花费不能重复，所以考虑背包 DP。设 表示将 右移 位、将 右移 位的最小代价，转移十分显然，即可 无脑做。然而由于我赛时太有脑了，非要写 ，最后调了好久才过。下次再也不长脑子了。

2025.3.20 疑似双休

今日歌曲：I Hate It Here

后天不用上课，这周疑似可以双休了！

今天在补好题推荐。

• [CodeForces 2078D] Scammy Game Ad

  很符合“时下流行”的题目了。

  考虑 DP，设 表示从第 个左/右门开始，到最后一个门的最大倍率。转移也是十分显然的。对于第 对门通过加法新产生的人数 ，将答案加上 即可。注意最初还有 个人。

2025.3.22

并不是双休，在家里 VP 模拟赛。

2025.3.25

打 USACO，菜得银组一道都不会。

2025.3.27

• [CodeForces 2077C] Binary Subsequence Value Sum

  极其有趣的题目了。

  显而易见，，所以一个字符串的权值 。把 换 ，那么 。继续将这个式子化简即可，这里不再赘述。

• [CodeForces 2082B] Floor or Ceil

  从二进制角度思考，向上取整等同于先加一再右移一位，向下取整则是直接向右移一位。所以，若一个向上取整操作后还有一个向下取整操作，那么这个向上取整操作相当于是无效的。又有在 次操作之后，最大值最多比最小值大一。所以对于最小值，先向上取整再向下取整即可，最大值反之。

• [CodeForces 2081A] Math Division

  考虑多操作一次的期望。多操作一次，则代表在第 位上产生了进位，又因为 ，所以前 位产生了进位（第 位是最高位）。设 表示前 位进位的期望，则：

  直接 DP 即可。