Znzryb's Blog
0%

Posted on Edited on

近期训练题目一句话总结

  • HDU 2026 春季联赛 10 D - 歪歪爱追剧：筛掉不含明星时刻的区间后做带权区间选择；坑点是没有前驱时也要允许当前区间单独成为答案。

  • CF 1100 E - Deconstruction Tree ：固定终点看前驱区间，非根转移是 need[y] < x < y；根转移只看第二大的根分支最大值。 题解

  • CF Round 1101 Div2 C2 - Seating Arrangement：两个洞见串起来看：一是桌子从空到非空是单向状态变化，所以拆成开桌者 / 跟随者；二是 A 不能待定式分配，因为其具有中间过程价值，因为它只有先作为跟随者进入结构，才会拥有“以后改成开桌者时吐回旧槽位”的中间过程价值。

  • 金马 5 校 - 奇点蜂测序：区间异或约束先转成前缀点关系 sl⊕sr+1=xs_l \oplus s_{r+1}=x，再用带权并查集维护连通块内相对异或；查询时同块输出差值，不同块输出 -1。

  • CF Edu 170 D - Attribute Checks：INT 当 dp 下标、STR 靠「已得点数 − INT」反推，把两维属性压成一维；每条检定本质是给一段连续区间 +1，用差分做到 O(1)，只有遇到加点才把差分 partial_sum 摊开、做一次背包式分裂转移再压回；m=5000 这个小界就是在暗示 O(n+m²)。

  • CF Edu 170 E - Card Game：单花色按点数从大到小变成括号前缀余额，用 Catalan / ballot 数压出 dp1；再让花色 1 的多余资源做一维 DP，刚好补完所有非王牌缺口。

Posted on

题目大意

题面

有一副牌，共 n×mn \times m 张。每张牌有两个参数：花色和点数。

  • 花色编号为 1…n1 \ldots n 。

  • 点数编号为 1…m1 \ldots m 。

  • 每一种花色和点数的组合都恰好有一张牌。

一张牌 (a,b)(a,b) 可以打败另一张牌 (c,d)(c,d) ，当且仅当满足下面两种情况之一：

  • a=1a=1 且 c≠1c\ne 1 。也就是说，花色 11 是王牌，可以打败任何非王牌花色。

  • a=ca=c 且 b>db>d 。也就是说，同花色里只能用更大的点数去打更小的点数。

两名玩家把整副牌平分。第一名玩家获胜，当且仅当：对第二名玩家的每一张牌，都能选出第一名玩家的一张牌打败它，并且第一名玩家的每张牌最多只用一次。

题目要求统计有多少种分牌方式能让第一名玩家获胜，答案对 998244353998244353 取模。

输入格式

输入一行两个整数 n,mn,m 。

输出格式

输出一个整数，表示合法分牌方式数量。

数据范围

  • 1≤n,m≤5001 \le n,m \le 500

  • mm 是偶数

样例

1
2
3
4
Input
1 4
Output
2
1
2
3
4
Input
2 2
Output
2
1
2
3
4
Input
3 6
Output
1690
1
2
3
4
Input
5 4
Output
568
1
2
3
4
Input
500 500
Output
84693741

思路讲解

一句话

这题先把一个花色内部压成一排 Catalan / ballot 数，再把非王牌花色的“缺口”当成资源消耗做 DP。

关键不变量：花色 11 多出来的牌，必须刚好补完所有非王牌花色内部的缺口。

一个花色为什么像括号序列

先只看一个固定花色，把点数从大到小扫。

  • 第一名玩家拿到这张牌，记成左括号。

  • 第二名玩家拿到这张牌，记成右括号。

同花色牌只能用高点数打低点数，所以扫到任何一个高点数前缀时，都必须保证这个前缀里第一名玩家的牌数不少于第二名玩家的牌数。

换成括号语言，就是：

任意前缀里，左括号数量不能少于右括号数量。

这就是 Catalan 数最常见的前缀余额模型。

Catalan 数和反射法

如果一个花色里双方各拿 m/2m/2 张，并且完全靠本花色自己匹配，那么合法安排数是：

(mm/2)−(mm/2+1)\binom{m}{m/2}-\binom{m}{m/2+1}

它来自反射法：所有平衡括号序列一共有 (mm/2)\binom{m}{m/2} 个；不合法序列会在某个位置第一次让前缀余额变成 −1-1 ，把开头到这个位置的括号全部翻转，就会一一对应到左括号多一个的序列，也就是 (mm/2+1)\binom{m}{m/2+1} 个。

所以合法数就是“全部方案减掉坏方案”。

带缺口的 ballot 数

这题里非王牌花色不一定要自己完全匹配，因为花色 11 可以来救场。

如果某个非王牌花色中，第一名玩家比一半少拿了 jj 张，那么：

  • 第一名玩家拿了 m/2−jm/2-j 张。

  • 第二名玩家拿了 m/2+jm/2+j 张。

  • 这个花色总量上缺了 2j2j 张先手牌。

为了不额外消耗更多王牌，这个花色从大到小扫描时，前缀余额最低只能掉到 −2j-2j 。这仍然是 ballot 数，方案数刚好是：

dp1[j]=(mm/2+j)−(mm/2+j+1)dp1[j]=\binom{m}{m/2+j}-\binom{m}{m/2+j+1}

这个式子也能用于王牌花色：如果花色 11 中第一名玩家比一半多拿了 jj 张，那么它自己内部能匹配，并且最后剩下 2j2j 张王牌去补其它花色。

状态定义怎么长出来

单个花色已经被压成了 dp1[j]dp1[j] ，后面就不用再记每张牌的具体归属了。

可以定义 dp2[j]dp2[j] 为：处理完若干个花色后，花色 11 还剩 jj 份优势没有被用掉的方案数。

这里的 jj 表示“多拿了几张的一半资源单位”。真实可补的王牌数量是 2j2j 。

初始化时，只处理花色 11 ：

dp2[j]=dp1[j]dp2[j]=dp1[j]

然后依次处理其它 n−1n-1 个花色。假设当前还剩 kk 份优势，当前非王牌花色少拿了 k−jk-j 张，那么处理后就还剩 jj 份优势：

ndp[j]+=dp2[k]⋅dp1[k−j]ndp[j] += dp2[k]\cdot dp1[k-j]

也就是代码里的转移：

1
2
3
4
5
6
for (int j = 0; j <= M / 2; ++j) {
    for (int k = j; k <= M / 2; ++k) {
        ndp[j] += dp2[k] * dp1[k - j];
        ndp[j] %= mod;
    }
}

最后必须剩余优势为 00 ，因为整副牌要平分，花色 11 多拿的量必须被非王牌少拿的量完全抵消：

1
ll ans = dp2[0];

复杂度

m≤500m\le 500 ，所以状态上限只有 m/2m/2 。

  • 预处理组合数： O(m)O(m) 。

  • 单花色贡献： O(m)O(m) 。

  • 多花色 DP： O(nm2)O(nm^2) 。

  • 空间复杂度： O(m)O(m) 。

AC 代码

AC 提交链接

源码较长，折叠如下。

心路历程（WA，TLE，MLE……）

卡点：第二维不应该是点数位置

一开始很容易想成 dp[i][j]dp[i][j] 表示“处理到第 ii 个花色、第 jj 张牌”。这个方向的问题是：花色内部一旦处理完，跨花色传递的并不是具体点数位置，而是这个花色消耗了多少王牌资源。

真正要传递的是“花色 11 还剩多少优势”，或者等价地，“非王牌花色累计少拿了多少”。所以第二维应该是资源缺口，不是 rank 下标。

卡点：每一轮 DP 必须清空

处理一个新花色时，ndp 必须从 00 开始。

1
ndp.assign(M / 2 + 2, 0);

如果写成 ndp = dp2，就相当于允许当前花色不处理，旧状态直接继承，会把方案数多算进去。

卡点：答案不是所有剩余状态求和

如果 dp2[j]dp2[j] 表示花色 11 还剩 jj 份优势，那最后只能取 dp2[0]dp2[0] 。

剩余优势大于 00 的状态，表示花色 11 多拿的牌没有被其它花色少拿的牌抵消，整副牌没有平分，不能算合法分配。

附件

暂无。

Posted on Edited on

题目大意

给两个长度相同的 01 串 A 和 B。一次操作可以把 A 的第一个字符搬到末尾，也就是做一次左循环位移。

要对每个测试用例求最少操作次数，使得 A = B。如果不管怎么循环位移都不可能相等，就输出 -1。

输入格式

第一行是测试组数 T。每组测试给两行：

1
2
A
B

数据范围

  • 测试组数：1 <= T <= 10000

  • A 和 B 都是只包含 0 / 1 的字符串。

  • 每组字符串长度满足：2 <= len(A) = len(B) <= 10^6

  • 单个输入中，所有测试用例的 len(A) 之和不超过 10^6

样例

1
2
3
4
5
6
7
8
9
10
11
5
1010001
1000110
000
111
01010
01010
0101
0011
100001101110000001010110110001
101100011000011011100000010101

输出：

1
2
3
4
5
2
-1
0
-1
22

第一组里，1010001 -> 0100011 -> 1000110，做 2 次就能变成 B。

思路讲解

一句话

这题本质上是在问：B 是不是 A 的某个循环位移；如果是，就找最小的左移次数。直接拼 A + A 然后找 B 也能做，这里用 0-based 字符串哈希模板，把每次“弹出头字符 + 追加到尾部”的变化维护成 O(1)。

把循环位移看成哈希上的 pop / push

字符串哈希和十进制数很像：越靠前的字符权重越高。设当前串长度为 n，哈希值是

h=s0⋅basen−1+s1⋅basen−2+⋯+sn−1.h = s_0 \cdot base^{n-1} + s_1 \cdot base^{n-2} + \cdots + s_{n-1}.

做一次左循环位移，相当于两步：

操作 对哈希的影响
把首字符 ch 从最高位删掉 h -= ch * base^(n - 1)
把 ch 放到末尾 h = h * base + ch

所以每次转一下，不需要真的改字符串，也不需要重新算整段哈希。

关键不变量：h1.hashval 始终等于当前这一次循环位移后的 A 的完整哈希值。

模板本身提供的是末尾 push/pop 和 0-based get(l,r)；这道题的操作是“删头 + 加尾”，所以在完整串哈希上单独写两个小函数：

1
2
3
4
5
6
7
8
auto popFront = [&](char ch) {
    h1.hashval -= U(ch) * h1.powBase[n - 1];
};

auto pushBack = [&](char ch) {
    h1.hashval *= base;
    h1.hashval += U(ch);
};

为什么只需要枚举 n - 1 次

如果一开始 A = B，答案就是 0。

否则每做一次操作就是左移一位。长度为 n 的字符串转 n 次会回到原串，所以只需要检查 1 到 n - 1 次。第一次遇到哈希相等的位置，就是最小操作次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if (h1.hashval == h2.hashval) {
    cout << 0 << "\n";
    return;
}

FOR(i, 0, SZ(s1) - 2) {
    popFront(s1[i]);
    pushBack(s1[i]);
    if (h1.hashval == h2.hashval) {
        cout << i + 1 << "\n";
        return;
    }
}
cout << -1 << "\n";

模数选择

这里用的是 2^61 - 1 这个 Mersenne prime 风格的哈希模数。乘法时用 __uint128_t 接住，再用折叠方式取模，碰撞概率很低，速度也比较舒服。

这版模板还有两个实用细节：

功能 用处
get(l, r) 内部 0-based，返回 s[l..r] 的哈希，还会自动修正边界
push(c) / pop() 维护“末尾追加 / 末尾删除”的在线哈希，适合栈式字符串处理

普通 unsigned long long 自然溢出也能写，但这题总长度到 10^6，用 2^61 - 1 会更安心一点。

复杂度

每个测试用例只初始化一次哈希和幂数组，然后枚举所有循环位移。

时间复杂度是 O(n)，空间复杂度是 O(n)。所有测试的总长度不超过 10^6，所以稳过。

AC 代码

AC 提交链接

源码较长，下面折叠完整 C++。

心路历程（WA，TLE，MLE……）

本地 Obsidian 笔记里没有记录这题的 WA / TLE。比较容易踩的点主要有两个：

  • 哈希递推方向要统一：前面的字符是高位，所以删首字符时删的是 ch * base^(n - 1)。

  • 循环次数不要多枚举：如果检查完 n - 1 次还没有相等，下一次就回到原串了，答案只能是 -1。

附件

暂无附件。

Posted on Edited on

题目大意

你的角色有 力量(STR) 和 智力(INT) 两个属性，都从 00 开始。按顺序读 nn 条记录，整局一共会获得 mm 个属性点（ mm 就是记录里 00 的个数），每个点你可以自己决定加到 STR 还是 INT。

每条记录 rir_i 的含义：

  • ri=0r_i = 0 ：获得一个属性点。

  • ri>0r_i > 0 ：智力检定，当前 INT ≥ri\ge r_i 就通过。

  • ri<0r_i < 0 ：力量检定，当前 STR ≥∣ri∣\ge |r_i| 就通过。

记录顺序不能改，问把点分配到最优时，最多能通过多少次检定。

数据范围

1≤m≤50001 \le m \le 5000 ， m≤n≤2×106m \le n \le 2 \times 10^6 ， −m≤ri≤m-m \le r_i \le m 。

思路讲解

一句话

用 INT 当 dp 下标、STR 靠「已得点数 −- INT」反推出来，把两维属性压成一维；每条检定本质是给一段连续区间整体 +1+1 ，用 差分\textcolor{blue}{\boldsymbol{差分}} 做到 O(1)O(1) ；只有遇到加点才把差分摊开、做一次背包式的分裂转移。总复杂度 O(n+m2)O(n + m^2) 。

m = 5000 是在暗示什么

第一眼会觉得这个 m≤5000m \le 5000 很神秘—— nn 都到 2×1062 \times 10^6 了，为什么单独给 mm 卡一个这么小的界？

其实这就是复杂度的暗示。 mm 只有 50005000 ，意味着 O(m2)≈2.5×107O(m^2) \approx 2.5 \times 10^7 是能过的；而属性点总数恰好就是 mm 。所以这是一个 状态规模被 m 限制住的 dp\textcolor{blue}{\boldsymbol{状态规模被\ m\ 限制住的\ dp}} ：对 nn 条记录只能做 O(n)O(n) 量级的线性扫，把贵的 O(m2)O(m^2) 留给加点那一步。

状态怎么设

设到当前为止已经拿到 PP 个点（ PP 就是目前见过的 00 的个数），其中有 jj 个加进了 INT。那么：

  • INT =j= j

  • STR =P−j= P - j

也就是说，只要固定了已得点数 PP 和 INT 值 jj ，STR 就被反推出来了——两维属性其实只剩一个自由度。于是只需要一维 dp：

dp[j]dp[j] ＝「当前 INT 恰好为 jj 」这条路径上，已经通过的检定数的最大值。

dp 的长度就是 P+1P + 1 （ jj 从 00 到 PP ），每遇到一个 00 长度就 +1+1 。

检定更新 ＝ 区间 +1 ＝ 差分

关键观察：每条检定，能通过它的那些状态在 jj 上是连续的一段，对这一段整体 +1+1 即可。

  • 智力检定 r>0r > 0 ：要 INT ≥r\ge r ，即 j∈[r,P]j \in [r, P] 整段 +1+1 。

  • 力量检定（记 r=∣ri∣r = |r_i| ）：要 STR =P−j≥r= P - j \ge r ，即 j≤P−rj \le P - r ，也就是 j∈[0,P−r]j \in [0, P - r] 整段 +1+1 。

如果每次都暴力扫这一段去 +1+1 ，最坏 O(nm)O(nm) 直接炸。所以把 dp 全程存成 差分数组\textcolor{blue}{\boldsymbol{差分数组}} ，区间 +1+1 变成端点 O(1)O(1) 改：

1
2
3
4
// 智力检定: [r, P] += 1
dp[r]++;
// 力量检定: [0, P-r] += 1, 其中 rem = P - r
dp[0]++;  dp[rem + 1]--;

dp 平时就以差分形式躺着，等真正要用到具体数值时再 partial_sum 摊开。

加点转移：摊开 → 分裂 → 压回

只有遇到 00 （多一个点）时，才需要真实 dp 值来做转移。这一步分三小步：

  1. partial_sum 摊开：把差分还原成真实 dpdp 值，之前累积的所有检定 +1+1 在这一刻一起生效。

  2. 分裂（长度 +1+1 ）：新点要么给 STR、要么给 INT。新的 INT 值 jj 可以从两处转移来——

  • 老 INT =j= j ，点给 STR（INT 不变）： dp[j]dp[j]

  • 老 INT =j−1= j - 1 ，点给 INT（INT 加一）： dp[j−1]dp[j-1]

所以 ndp[j]=max⁡(dp[j], dp[j−1])ndp[j] = \max(dp[j],\ dp[j-1]) 。代码里靠转移顺序（先写 ndp[j+1]=dp[j]ndp[j+1] = dp[j] ，下一轮再 max⁡\max ）一遍循环就拿到了这个 max⁡\max 值。

  1. adjacent_difference 压回：把 ndpndp 重新编码回差分形式，好让后面的检定继续用 O(1)O(1) 端点更新。
1
2
3
4
5
6
7
8
partial_sum(all(dp), dp.begin());          // 摊开成真实值
vector<ll> ndp(SZ(dp) + 1);
for (int j = 0; j < SZ(dp); ++j) {
    ndp[j] = max(ndp[j], dp[j]);           // 点给 STR: INT 不变
    ndp[j + 1] = dp[j];                    // 点给 INT: INT 加一
}
adjacent_difference(all(ndp), ndp.begin()); // 压回差分
swap(ndp, dp);

最后再 partial_sum 摊开一次取 max_element，就是答案。

💡 Note: 懒操作的本质：决策只在「加点」那一刻发生

  • 检定（r ≠ 0）不是决策：它只是给「已经够格的那一段状态」整体 +1——谁够格谁加分，你不用做任何选择。既然不分叉，就能攒着不动：用差分打个标记，懒到真正要用数值时再 partial_sum 摊开。
  • 加点（r = 0）才是决策点：这一刻你必须选「这个点给 STR 还是 INT」。这是整个 dp 唯一会分叉的地方，所以也只有这一刻需要摊开真实值、做 max 转移、数组长大一格。
    所以「转移放在加点那一步」不是凑巧，而是因为加点是全题唯一需要做选择的时刻；检定只负责记分、不负责选择，自然能被懒着批量处理。一句话：懒在不分叉的记分上，只在分叉的决策上才结算。

旁注：为什么「右移」只保住 STR、不保 INT —— 这恰恰是它的本职

有个很自然的疑问：partial_sum 还原以后， dp[x]dp[x] 表示「INT 花了 xx 、STR 花了 P−xP - x 」（注意这里的总点数是加新点之前的 P=curp−1P = curp - 1 ，因为 curp++ 在前、而 dp 还没变长）。那右移 ndp[i+1]=dp[i]ndp[i+1] = dp[i] 看上去保住了 STR、却把 INT 从 ii 改成了 i+1i+1 ——正属性的意义不就没保住吗？

症结在于：STR 从来没被显式存过，它永远是「当前总点数 −- 下标」临时算出来的，即 STR =curp−i= curp - i 。所以当 curpcurp 自己 +1+1 的时候，同一个下标 ii 对应的 STR 含义会自动变大 11 。两行转移正好对应「这个点花在哪」：

这一行代码 点花在 INT STR ＝ curp − 下标
ndp[i] = max(ndp[i], dp[i])（不右移） 负属性 STR 不变，仍是 ii 下标没动，但 curp ＋1，故 (P−i)→(P−i)+1(P-i) \to (P-i)+1
ndp[i+1] = dp[i]（右移） 正属性 INT i→i+1i \to i+1 curp−(i+1)=P−icurp-(i+1) = P-i ，不变

所以你的观察完全正确，但结论要反过来读：

  • 右移 ＝ 点给 INT。 INT 就应该涨 11 （这正是「把点花在 INT 上」），STR 不动。你看到的「STR 不变、INT +1+1 」不是 bug，是右移的全部目的。

  • 不右移 ＝ 点给 STR。 它看着像原地不动，但因为 curpcurp 涨了 11 、而 STR =curp−i= curp - i ，同一下标 ii 上的 STR 就悄悄 +1+1 了。换句话说「加到 STR」根本不需要任何搬运——只要让总数长大、下标不动，STR 自己就 +1+1 。这是这套一维差分 dp 最巧的地方。

合起来看新数组的下标 ii （即 INT =i=i ）：

它能从两处转移来——旧下标 ii 点给 STR（不右移）、旧下标 i−1i-1 点给 INT（右移）。取 max⁡\max 就是 ndp[i]=max⁡(dp[i], dp[i−1])ndp[i] = \max(dp[i],\ dp[i-1]) 。两条分支恰好覆盖「点给 STR / 点给 INT」两个决策，缺一不可，所以才 max 取优。

回到「两个旧格子汇聚到同一个新格子 ndp[i]」的视角。关键不在「谁汇进来」，而在两条路各动一个属性：左路把点给 INT（动的是 INT），右路把点给 STR（动的是 STR），最后 max 取优。（对应代码：右移那条是 ndp[i] ← dp[i-1]，原地那条是 ndp[i] ← dp[i]。）

1
2
3
4
5
6
7
8
9
10
11
graph TD
    A["dp[i-1]<br/>INT = i-1<br/>STR = P-(i-1) = P-i+1"]
    B["dp[i]<br/>INT = i<br/>STR = P-i"]
    C["ndp[i]（新格子）<br/>INT = i<br/>STR = curp-i = P-i+1"]
    A -->|"点给 INT · 右移 i-1 → i<br/>动的是 INT；STR 本就 = P-i+1，没变"| C
    B -->|"点给 STR · 下标不动<br/>动的是 STR：P-i → P-i+1（靠 curp 长大）"| C
    C --> M["ndp[i] = max( dp[i] , dp[i-1] )<br/>两条路取优"]
    classDef intc fill:#3a2a1e,stroke:#c08a3f,color:#ffe;
    classDef strc fill:#1e3a2f,stroke:#3fa66a,color:#dff;
    class A intc;
    class B strc;

二维 (INT, STR) 视角（以 P=3 为例）：横轴 INT＝dp 下标，纵轴 STR＝curp−下标。空心圈＝加点前状态（落在对角线 INT+STR=P），实心点＝加点后（外推到 INT+STR=curp）。黄点 dp[1] 加一个点 = 走一步：绿色往上＝点给 STR（STR+1），橙色往右＝点给 INT（INT+1），后者就是一维数组里的「右移」。STR 在这里是真坐标轴、不再隐式，所以「右移保 STR」一眼可见。TikZ 源码见文末附件。

复杂度

nn 条记录里，每条检定更新都是 O(1)O(1) ，合计 O(n)O(n) ；加点只发生 mm 次，每次的摊开 / 分裂 / 压回是当前长度 O(P)≤O(m)O(P) \le O(m) ，累计 O(m2)O(m^2) 。总复杂度 O(n+m2)O(n + m^2) ，在 m≤5000m \le 5000 下稳过。

AC 代码

AC 提交记录

源码较长，展开查看：

心路历程

这道题的几个台阶，按我当时想通的顺序：

  • 第一关：读懂 m=5000m = 5000 的暗示。 nn 大、 mm 小这种不对称的数据范围，几乎总在提示「按 mm 设计状态、对 nn 只做线性扫」。先有这个直觉，后面才知道往 O(m2)O(m^2) 的 dp 上靠。

  • 第二关：发现 STR 能被反推。 一上来容易想开 dp[STR][INT]dp[\text{STR}][\text{INT}] 两维，但 STR ++ INT == 当前点数是已知量，所以一维 dp[INT]dp[\text{INT}] 就够，省掉一整维。

  • 第三关：把区间 +1+1 差分化。 朴素地对每条检定扫一段做 +1+1 是 O(nm)O(nm) ，用差分 ++ 延迟 partial_sum 把它摊到 O(n)O(n) ——这是整道题真正的瓶颈优化，也是把 n=2×106n = 2 \times 10^6 扛下来的关键。

附件

完整 AC 源码（含中文注释）也作为附件挂在下方，方便下载到本地对拍 / 改造。

2025D_Attribute_Checks.cpp.txt

grid_intstr.tex.txt

Posted on Edited on

判断 0-based 还是 1-based，核心只看这个标号有没有实际意义：有意义就保留，没意义且只是容器访问就转成 0-based。