Znzryb's Blog
0%

CF Edu 170 D - Attribute Checks

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