2025 年 4 月日祭

2025.4.1 愚人节

今日歌曲：Forever Winter

我的日祭之前断更了一段时间，今天终于补上了。

今天改不动题，于是在出题。

2025.4.6 水讨论区

今日歌曲：Guilty Pleasure

讨论区居然真的回来了，又可以水讨论区了（。

今天 VP Codeforces Round 1015, Div. 1 + Div. 2，赛后结算时，发现机房网络得了 MVP。详见犇犇。

前四题都是沟槽构造，不再赘述。

• [Atcoder ABC400F] Happy Birthday! 3

  考虑正难则反。问题转化为：

  一个环上有 个物品，颜色分别为 ，每次操作选择两个数 使得 ，对 进行“漂白”，即将颜色都设为 。一次操作的代价为 。求将整个环漂白的最小总代价。

  先断环为链。设 表示将 漂白的最小代价，那么显然有 。

  设 表示使 能够漂白的最小代价，那么显然有 。当 时，有 。

  答案即为 。

• [Codeforces 2086E] Zebra-like Numbers

  确简单的啊，可是自己就是想不到。

  考虑计算一个数的斑马值。贪心地，尽量选大的斑马数减即可。

  考虑记搜，设 表示 中斑马值为 的数的个数。那么显然有 ，其中 是不大于 的最大的斑马数。具体地， 表示 中斑马值为 的数的个数， 表示 中斑马值为 的数的个数。

2025.4.8 过水了

今日歌曲：it’s time to go

过水了今天。

2025.4.10 证明略

今日歌曲：The Albatross

• [Atcoder ARC196A] Adjacent Delete

  唐题啊，可是和我相比还是我更唐。

  假设 是偶数。如果我们忽略删除相邻数的条件，即可以任选两个数相减，那么答案应该是前 大的数（记作“较大数”）的和减去前 小的数（记作“较小数”）的和。

  容易发现，当我们只能选相邻数相减时，依然可以达到这个答案，因为在任意时刻，总存在至少一对较大数与较小数相邻。

  当 是奇数，那么一定有一个元素不被选，且这个元素一定在奇数位，这样才能把数组分成长度为偶数的两段。枚举不被选的位置，用对顶堆维护前后两段的答案即可。

• [Atcoder パ研合宿2024 第3日 E] Roller Coaster

  人类智慧啊。选高度差最大的边即可。证明略。

• [Atcoder パ研合宿2024 第3日 G] Bracket Sequence

  极一眼啊，大概十分钟切了吧。跟翻转括号序列的一个区间那题差不多，这题还简单一点。

  注意到位置 可由 与跟 位置高度相同的位置转移而来。拿一个桶维护后者即可，遇到右括号时记得清零。

2025.4.12 写了跟写了一样

今日歌曲：august

模拟赛。

• A - 倒水

  题目：有三个容量分别为 的杯子与一个容量为 的一个桶，每次可以：

  • 把一个杯子灌满；
  • 把一个杯子的水倒出去；
  • 把一个杯子的水倒到另一个杯子直到这个杯子空了或另一个杯子满了；
  • 把一个杯子的水倒到桶里。

  对于 中的每一个 ，求要使桶装满水，最少的操作次数。

  题解： 发的题解写了跟写了一样。

  容易发现，经过转化，可以得到两种操作：向桶里加 单位水与从桶里舀出 单位水回到对应的杯子（后者是操作一与操作三的结合），每次操作的代价都为二。注意到，对于某一个水杯，若我们用它进行的最后一个操作是操作二，那么代价为一，因为不用把舀出来的水倒出去。设 表示桶里有 单位水的最小代价， 表示三个水杯是否最后用于操作二，那么先正着 DP 一遍，即全部使用操作一，再反着 DP 即可。统计答案时应统计 。

• B - 让他们连通 （[Codeforces 1706E] Qpwoeirut and Vertices）

  居然能场切 。

  要让区间 连通，等价于 ， 与 连通。设 表示 与 连通的时间，则答案为 ，可以用 ST 表维护，常数又小又好写。

  对于 ，考虑启发式合并。在合并时，枚举较小的集合的元素，并判断它是否与另一个集合中的元素相邻即可。赛时因为没判 被硬控了半个小时。

2025.4.15 不想证明

今日歌曲：cardigan

• [Atcoder パ研合宿2024 第3日 G] 門松

  无脑做啊，不想证明。

• [Atcoder パ研合宿2024 第3日 H] Big XOR Game

  这题评分比括号序列还要低。

  从高到低讨论，对于每一位，设当前位上是 的数的个数是 ，那么有：

  if(((cnt + 1) / 2) & 1 and (cnt / 2) & 1 ^ 1) Alice;
  if(((cnt + 1) / 2) & 1 ^ 1 and (cnt / 2) & 1) {
    if(n & 1) Bob;
    else Alice;
  }

  不想详细说明。

2025.4.19 输入挂了

今日歌曲：Sad Beautiful Tragic

TTPD 一周年了。

今天模拟赛因为输入挂了 ，机房 rating 暴涨暴跌。

• A - 说唱入门教学

  题目：给定一首歌的歌词（以拼音形式），每两句话一一匹配，，求出 押的个数。

  题解：题面好唐。先把韵母处理出来，然后 trie 树即可。常数极大。

• B - 画画入门教学

  构造题，手动推一推小样例即可。