5月日志

DimStar
  2026-05-05 09:16:22 2026-05-05 09:16:22 创建   2026-06-13 20:15:55 2026-06-13 20:15:55 更新      4.1k 字  

26-5-2

嗯，对，我在烬区一发制导炸了接近 5000 分。（）

26-5-3

Skipped.

26-5-4

To do.
Skipped.

26-5-5

To do.
Skipped.

26-5-6

To do.
Skipped.

26-5-7

To do.
Skipped.

DimStar’s Blog 进入大 To do 时代！
DimStar’s Blog 进入大 Skip 时代！

26-5-8

AtCoder ARC124 E，这题是 DP 后手动容斥。

注意到若所有人都传球，则该方案一定有重复，因为可以使每个人少传一个球，结果不变。

否则，则该传球方案对应的最终局面不重复，因为若要保持相同局面，只能是所有人都增加/减少传球，而这两种方式都不符合最少传球数为 的要求。

所以至少有 个人未传球，所以就可以用所有传球方案数减去至少传了一个球的方案数。

算方案用了一点组合意义，将乘积转化为选一个球，有 表示一个人选择的球不是传来的球，此时前 个人的选择方案数, 表示一个人选择的球是传来的球，此时前 个人的选择方案数。

转移如下（ 表示至少传球个数）：

后面那个东西的转移系数可以 算。

由于环的问题，所以要枚举第一个人选的是自己的球还是传来的球（初状态 或 ），然后最后取对应的 作答案。

为什么初状态 ？

因为此时不知道前一个球传来的球有多少个，所以只能放个不影响答案的 ，最后枚举了第 人传了多少球才能知道方案数，因此取 （事实上是 ）。

26-5-9

CF1942G，思路大致是对的，但是卡在计数的不重不漏上，本来是考虑最后一张特殊牌的位置来去重，但是这个东西只能 做，想要优化是极其困难的。

所以通过考虑第一次（显然最多有一次）抽牌数耗尽的位置去重。

直接枚举，方案数是好想的，还有就是如果 就可能抽完所有牌，此时没有抽牌数的耗尽位置（全程未耗尽），要考虑该情况，不过这种情况的方案数也是简单的。

大模拟赛 CWCPC - 1，7 道大败而归，hyc 比我多做三道蓝题，蓝题都不会，大哭。

26-5-11

改题，把 CWCPC - 1 的三道蓝题改了。

分别是神秘斐波那契数列，神秘手写 bitset 优化枚举，神秘记忆化搜索。

26-5-12

上午改了 CWCPC - 1 的 D。

下午尝试做 L。

26-5-13

终于推完式子了写出 L 了。

26-5-14

改了 CWCPC - 1 的 E。

这题首先是将答案映射到不存在取模的情况下，然后在 DP 中利用各种各样的单调性，省去不必要的信息，压缩状态。

26-5-15

P3266。

神奇的题目，从 DP 变到反射容斥，神奇。

先从题目中发现一行的选法只有 种，因此可以塞进 DP 态里。

转移规律是简单的，这样可以写出一个 的 DP，然后优化一下，减少重复转移，就变成了这个。

代码是这样：

1
2
3
4
5
6
7
8
9
10
11
12
nmf(j, 0, m) f[1][j] = 1;
nmf(i, 2, n)
{
    f[i][0] = f[i - 1][0] + f[i - 1][1];
    nmf(j, 1, m)
    {
        f[i][j] = f[i][j - 1];
        modadd(f[i][j], f[i - 1][j + 1]);
    }
}
int ans = 0;
nmf(j, 0, m) modadd(ans, f[n][j]);

发现这个东西画到格子上，再对第二维加上第一维（即在坐标系上“搓”一下）。

代码写出来是这样：

1
2
3
4
5
6
7
8
9
10
11
12
nmf(j, 0, m) f[1][j] = 1;
nmf(i, 2, n)
{
    f[i][i] = f[i - 1][i - 1] + f[i - 1][i];
    nmf(j, 1, m)
    {
        f[i][i + j] = f[i][i + j - 1];
        modadd(f[i][i + j], f[i - 1][i + j]);
    }
}
int ans = 0;
nmf(j, 0, m) modadd(ans, f[n][j]);

可以发现此时转移基本上是直接加上左边和下面的 DP 值，这启发我们想到格路计数。

注意到答案事实上是 。平移一下，将起点设为 ，再将转移整理一下。

1
2
3
4
5
6
7
8
9
10
11
nmf(j, 0, m) f[0][j] = 1;
nmf(i, 1, n)
{
    f[i][i - 1] = f[i - 1][i - 1];
    nmf(j, i, m + i)
    {
        f[i][j] = f[i][j - 1];
        modadd(f[i][j], f[i - 1][j]);
    }
}
ans = f[n][n + m];

这玩意事实上就是朴素的双线限制格路计数，将第二维视为横坐标，则有限制 ，即不能碰到 和 。

然后直接做即可。

26-5-16

模拟赛，问候乱序放题的组题人。

T1，一道线段树分治模板。

T2，紫色题目，有点 Ad-hoc 意味。

转化为移动 两个数组上的指针，要求右指针所指的值始终不小于左指针所指的值。

想象成在一个矩阵上移动点， 是行， 是列。

首先发现对于两个数组中的最值，有很好的性质。

有仅当 且 时合法，否则会有一列/行全不合法，显然无解。

如果符合上面的条件， 的最大行上的位置均合法， 的最小列上的位置均合法。

所以此时只需要能够从 走到 的最大行，或者 的最小列，并且能够从 走到 的最大行，或者 的最小列，就是合法的。

然后转化成两个子问题。

发现在子问题中同样可以通过上面的条件找最大行最小列，然后缩小子问题规模。

当起点在最大行最小列时就合法。

如果此时子问题内 且 说明会形成一圈不合法点，此时就不可能从起点走到终点。

处理一下 和 的前后缀最值即可 做。

T3，先差分变成求前缀，再转化成二进制类似数位 DP 的东西，DP 代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// pw[n] = pow(3, pow(2, n))
LL solve(const string &s, int pos)
{
    if (pos == 0)
        return 3;
    // 因为胜利方案的手势显然石头剪刀布各 1/3，所以直接乘另外一边的全方案数，再乘胜率（左 2/3，右 1/3）。
    if (s[pos] ^ '0')
    {
        // 此时所有左子树赢的方案均有贡献，直接加。右子树递归算，再乘左子树方案数，再乘 1/3。
        return (pw[pos] * inv3 * 2 + pw[pos - 1] * solve(s, pos - 1) % mod * inv3) % mod;
    }
    else
    {
        // 此时答案方案是左子树递归算乘右子树方案数乘 2/3。
        return (pw[pos - 1] * solve(s, pos - 1) % mod * inv3 * 2) % mod;
    }
}

T4，先转树上子树修改为区间修改，有关取模的东西，只能很暴力的做，因此根号分治，还要分块处理区间修改，模数小时，散块直接做，整块修改挂在 表示对块 ，模数为 ，余数为 的修改总值，模数小时，散块直接做，整块修改挂在 表示对深度为 ，块为 的修改，这个东西涉及到区间加，平衡一下，选择差分区间修改，查询时暴力求和，平衡后这样时空复杂度是 ，由于空间限制，分块块长要开大，根号分治阈值要开小，另外由于要取模，全开 unsigned 能卡常。

本场由于脑抽 T3 数组没开够从 80 变成 50，挂了 30。

26-5-18

改模拟赛和晚练。

我好菜。

26-5-19

改模拟赛。

26-5-20

AtCoder ABC288 H，神题。

主要是先通过异或性质将可重排序序列（）转化成求不可重排序序列，再转化成不可重序列数量（g_i），再通过集合划分容斥简化成二进制数位 DP。

第一步式子，应该是好理解的，先将不可重序列排序，再乘上可能出现的重复对方案：

note: 是从 个数中可重复的选 个，可能的可重集个数。

第二步集合划分容斥很复杂，容斥用 DeepSeek 讲了一下。

https://chat.deepseek.com/share/r6xrgd3kvdlckq3c4o.

反正就是用这个容斥一下，对于容斥时钦定出来的每一个块，按照块大小是奇数还是偶数判断是否需要塞进数位 DP 里算，如果大小为偶数不需要算的话该块方案数直接是 。

设个 DP 状的容斥系数 表示有 个元素，其中有 个奇数大小相同块（只有这些块有效，需要塞进数位 DP 里）的容斥系数。

枚举第一个元素所在块的大小 ，有如下转移：

然后数位 DP 放个代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
LL w[202]; // w[i] 表示异或和为 x，长度为 i，值域为 [0,m] 的有序序列数，可以相同
LL f[32][202]; // f[i][j] 表示异或和为 x，枚举到第 i 位，有 j 个不自由数字的方案数
void calc()
{
    if (x == 0)
        w[0] = 1;
    nmf(cnt, 1, n)
    {
        memset(f, 0, sizeof(f));
        f[30][cnt] = 1;
        ref(i, 30, 1)
        {
            int mp = (m >> (i - 1)) & 1; // 该位上界
            int xp = (x >> (i - 1)) & 1; // x 这位的值
            nmf(j, 0, cnt)
            {
                if (f[i][j] == 0)
                    continue;
                if (mp) // 若上界为 1
                {
                    nmf(k, 0, j) // 枚举钦定多少数为 0
                    {
                        if (j < cnt)
                            modadd(f[i - 1][j - k], f[i][j] * pw_2[cnt - j - 1] % mod * binom(j, k));
                        // 2 的幂那一项表示自由数的选择方案，显然有一半的方案满足该位异或值为 xp
                        else if (!(((j - k) & 1) ^ (xp))) // 没有自由数，此时有 j - k 个数该位为 1，异或值为 (j - k) & 1
                            modadd(f[i - 1][j - k], f[i][j] * binom(j, k));
                    }
                }
                else // 若上界为 0
                {
                    if (j < cnt) // 若有自由数
                        modadd(f[i - 1][j], f[i][j] * pw_2[cnt - j - 1]);
                    else if (xp == 0) // 此时的异或值显然为 0
                        modadd(f[i - 1][j], f[i][j]);
                }
            }
        }
        nmf(j, 0, cnt) // 枚举自由数个数
            modadd(w[cnt], f[0][j]);
    }
}

然后就是 的计算，枚举有多少个奇数块（有效数字），加上容斥系数乘数位 DP 算出的方案数。

复习一下如何算 。

到此这题就做完了，两步转化，集合划分容斥，二进制数位 DP，数数推式子，神题吧。

26-5-21

CF1967E1。

限制条件比较多，但是发现，对于一个 序列，显然是让 向上走可能性更多，这个贪心策略包含了向下走的可能性。

这样不用考虑确定 后 会往哪走，于是考虑 DP。

设 表示填到第 个位置，当前 走到 的方案数。

注意到如果 则接下来无论怎么填 都阻拦不了 飞上高天，于是之后的所有方案均合法，所以 的值域就可以限定为 。

26-5-22

UOJ 424，神秘题，发现这个题面中的“最大值的位置”“区间”之类词和笛卡尔树很有关系，发现事实上要问的就是可能的不相同的笛卡尔树个数，由于左叶子一定严格小于父亲，所以“左深度”不能超过 。

然后这东西显然可以 DP，就是 ，边界为 。

然后猎奇的就是这玩意可以理解为最大嵌套层数不超过 的合法括号序列数。

可以理解成这个括号序列 ， 枚举的是 的长度。 的可嵌套层数就要减一， 的可嵌套层数则还是 。

然后最大嵌套层数不超过 的合法括号序列数显然可以反射容斥做。

但是具体怎么做我忘了。 ：）

26-5-23

组队 CPC，7 题 Rank 24 离场。

26-5-25

AtCoder AGC070 C。

题面就是普通反射容斥的样子。

将 Alice 赢作为向右 步，Bob 赢作为向上 步，平局作为停。

则题目限制就是不能碰到 。

设 表示 Alice 赢 次，Bob 赢 次，平局 次，从 走到 的方案数，此时仅有三种操作的次数限制和不能连续朝一个方向走两步，没有不能碰到线的限制。

考虑容斥。

发现 没有包含所有不合法方案。

因为下图这种情况反射后出现了连续向一个方向走两次的情况，这种方案应被容斥掉但是如果直接减去 的话就不会被容斥掉。

如图

我们考虑每一种不合法情况被反射时的情况，显然反射前一步一定是“上”。

  1. 就是上面的“上 右”型，该情况的方案数是 ，理解为反射点处下一步本来是停/右，我们强行插入一个“上”（右反射后是上，因此我们钦定在此处有一个“上”，将滚木(停/右)变为上(停/右)）。

  2. “上 若干个停 上”型，该情况的方案数是 ，理解为我们在反射点处强行插入一个“停”（停上反射后是停右，因此我们钦定在此处有一个“停”，将反射后的右变为反射后的停右）。

  3. “上 若干个停 右”型，该情况的方案数是 ，理解为我们在反射点处强行插入一个“停上”（停右反射后是停上，因此我们钦定在此处有一个“停”和“上”，将反射后的滚木(停/右)变为反射后的停上(停/右)）。

因此 。

考虑 怎么算。

  1. 将 A 分成连续块
    把 个相同的 A 分成若干个连续块（每个块内的 A 彼此相邻，但块之间由 C 或 B 隔开）。设块数为 ，则块内相邻 A 的对数为 。
    令 ，即需要钦定插入 B 来分隔的相邻 A 的对数。
    将 个 A 分成 个非空块的方式数为 。

  2. 放置 C 和 A 块
    将 个相同的 C 排成一排，形成 个间隙。
    从中选择 个间隙，每个间隙放入一个 A 块。
    选择间隙的方式数为 。

  3. 插入 B
    此时得到的序列长度为 ，其中相邻 A 的对数恰好为 。这些相邻 A 之间必须插入 B（钦定），每个位置恰好插一个 B。
    整个序列共有 个间隙（包括两端和字母之间），其中 个是强制插 B 的间隙，剩余可用间隙数为 。
    还需要插入 个 B，已强制插入 个，故还需插入 个 B。每个可行间隙最多放一个 B（否则 B 会相邻），因此从 个可行间隙中选 个的方式数为 。

  4. 对所有可能的 求和
    的取值范围是 （，且 ）。
    总方案数为：

做完了。

26-5-26

上午道法与历史会考，下午做了 P7115。

分治，类似快速排序，将 种颜色分为不大于 的和大于 的，由于值域确定， 可以取到 ，然后可以分治处理。

如何将两种颜色分类是容易的，先移出一根上白 （值不大于 ）下黑（值大于 ）的柱子，然后之后移乱序柱子，借助这根上白下黑的柱子分类，具体过程并不难想，此处略过。

26-5-27

CF526F，分治，令 表示第 行怪物的列号，转化成计数 的 对数量。

分治算跨过 的贡献只需要处理 的后缀最值（，）， 的前缀最值（，），分讨最大最小值分别在哪一边，发现是这四种情况。

由于保证 互不相同，所以不用取等，全部使用严格比较。

  1. 最大在左，最小在左，，枚举 即可。
  2. 最大在左，最小在右，，枚举 ，对 双指针+桶维护即可。
  3. 最大在右，最小在右，，枚举 即可。
  4. 最大在右，最小在左，，枚举 ，对 双指针+桶维护即可。

还有个 QOJ 21566，四维偏序，模板题甚至还写炸了一次，我好菜。

26-5-28

早上改了昨晚晚练，并成功的将一道五维偏序差分降到了四维，写出来发现又 WA 又 TLE，然后被 cdo 提醒发现其实还可以差分成二维偏序加区间加单点查，相当于三维偏序。

火锅好吃。

结果下午才写出来。

26-5-29

出去研学。

不有趣。

打 Gemmer。

26-5-30

P3380。

树套树模板，没有什么特别的，第一次写，用的是树状数组套权值树状数组。

内层权值树状数组因为树状数组不支持动态开点所以用 unordered_map 存以达到动态开点的效果。

核心操作就是区间求某个值的排名和求某个排名的值，求排名对应的值用倍增代替二分去掉一只 。

  • 标题: 5月日志
  • 作者: DimStar
  • 创建于 : 2026-05-05 09:16:22
  • 更新于 : 2026-06-13 20:15:55
  • 链接: https://dimstar-zhang.github.io/2026/05/05/5月日志/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
目录
5月日志
  1. 26-5-2
  2. 26-5-3
  3. 26-5-4
  4. 26-5-5
  5. 26-5-6
  6. 26-5-7
  7. 26-5-8
  8. 26-5-9
  9. 26-5-11
  10. 26-5-12
  11. 26-5-13
  12. 26-5-14
  13. 26-5-15
  14. 26-5-16
  15. 26-5-18
  16. 26-5-19
  17. 26-5-20
  18. 26-5-21
  19. 26-5-22
  20. 26-5-23
  21. 26-5-25
  22. 26-5-26
  23. 26-5-27
  24. 26-5-28
  25. 26-5-29
  26. 26-5-30