Znzryb's Blog
0%

Posted on Edited on

题目大意

确定一个值，两个点的什么时候不合法→三个点什么时候合法→。。。）（两个叶子的 LCA ，相当于就是在这个 lca，裂成两条链，如果 x 个叶子的两两 lca 都是这个 lca，那这个树从 lca 这里裂成了 x 个

I - Homura’s Timeline Records (晓美焰的时间线记录)

时间限制： C/C++/Rust/Pascal 2秒，其他语言4秒

空间限制： C/C++/Rust/Pascal 1024 M，其他语言2048 M

特殊判定 (Special Judge)： 是

64位 IO 格式： %lld

题目描述

给定一棵包含 nn 个节点的树，根节点为 11。树上的边代表时间线的分支，根节点代表所有时间循环的共同起点。

定义节点的深度 (depth) 为从根节点到该节点路径上的边数。没有子节点的节点称为叶子节点，代表一条完整的时间线。

晓美焰以某种未知的顺序 L1,L2,…,LsL_1, L_2, \ldots, L_s 体验了每一条完整的时间线（即恰好遍历了每一个叶子节点一次）。

丘比的观察系统按照以下规则为每一个叶子节点 uu 记录了一个参考编号 bub_u：

  1. 第一个被体验的叶子节点被分配参考编号 00。

  2. 对于随后被体验的每一个叶子节点 uu，系统会在所有之前已经体验过的叶子节点中进行筛选。它会选择一个叶子节点 vv，使得它们的最近公共祖先的深度 depth⁡(LCA⁡(u,v))\operatorname{depth}(\operatorname{LCA}(u,v)) 尽可能大。

  3. 如果有多个叶子节点满足深度最大的条件，系统会选择其中最早被体验的那一个。

  4. 系统最终将 bub_u 赋值为选出的 vv。

注：LCA⁡(u,v)\operatorname{LCA}(u,v) 表示节点 uu 和 vv 在树上的最近公共祖先。更深的最近公共祖先意味着两条时间线共享更长的因果历史。

现在，给定这棵树以及所有叶子节点的参考编号 bub_u，请你判断这些编号是否可能由某种合法的叶子节点体验顺序产生。如果存在这样的顺序，请输出任意一种合法的顺序。

输入描述

第一行包含一个整数 nn (1≤n≤2⋅1051 \le n \le 2\cdot 10^5)，表示树的节点数。

接下来的 n−1n-1 行，每行包含两个整数 uu 和 vv (1≤u,v≤n1 \le u, v \le n)，表示节点 uu 和节点 vv 之间有一条无向边。保证给定的边构成一棵树。

接下来一行包含一个整数 ss (1≤s≤n1 \le s \le n)，表示以节点 11 为根时叶子节点的数量。

接下来的 ss 行，每行包含两个整数 uu 和 bub_u (1≤u≤n1 \le u \le n, 0≤bu≤n0 \le b_u \le n)，其中 uu 是一个叶子节点， bub_u 是它的参考编号。

保证： 给出的节点恰好涵盖了以 11 为根的树的所有叶子节点，且每个叶子节点只会出现一次。

注意： 输入中的非零 bub_u 值不保证一定是叶子节点的编号（可能包含非法数据）。

输出描述

如果不存在任何合法的叶子节点访问顺序，输出一行 NO。

否则，第一行输出 YES。在第二行输出 ss 个整数 L1,L2,…,LsL_1, L_2, \ldots, L_s，表示一种能够产生该记录的合法叶子节点体验顺序。

输出的序列中，每一个叶子节点必须恰好出现一次。如果有多种合法顺序，输出任意一种即可。

样例

Plaintext

1
2
3
4
5
6
7
8
9
10
11
12
7
1 2
1 3
2 4
2 5
3 6
3 7
4
4 0
5 4
6 4
7 6

Plaintext

1
2
YES
4 5 6 7

样例解释

在样例中，叶子节点分别为 4,5,6,74, 5, 6, 7。我们来验证输出顺序 4 5 6 7 是否合法：

  1. 叶子节点 44 第一个被体验，因此 b4=0b_4 = 0。

  2. 对于叶子节点 55，之前唯一体验过的叶子节点是 44，因此 b5=4b_5 = 4。

  3. 对于叶子节点 66，之前体验过 44 和 55。LCA⁡(6,4)=1\operatorname{LCA}(6,4) = 1，LCA⁡(6,5)=1\operatorname{LCA}(6,5) = 1。两者与 66 的最近公共祖先深度相同。由于 44 比 55 更早被体验，系统选择较早的 44，因此 b6=4b_6 = 4。

  4. 对于叶子节点 77，之前体验过 4,5,64, 5, 6。计算可知：LCA⁡(7,6)=3\operatorname{LCA}(7,6) = 3，而 LCA⁡(7,4)=LCA⁡(7,5)=1\operatorname{LCA}(7,4) = \operatorname{LCA}(7,5) = 1。因为节点 33 的深度大于节点 11 的深度，深度最大的是节点 66，因此 b7=6b_7 = 6。

综上所述，产生的结果与输入相符，4 5 6 7 是一个合法的顺序。

思路讲解

（先窄化问题，把整个序列的构建，先看两者这个之间的这个关系）

根据题意，如果对于叶子节点 uu，它的参考编号 bu=vb_u = v（v≠0v \neq 0），这不仅意味着在访问序列中 vv 必须排在 uu 之前。思考一下：设 w=LCA⁡(u,v)w = \operatorname{LCA}(u, v)，在以 ww 为根的整棵子树中，vv 的访问顺序必须满足什么条件，才能在所有已访问的节点里成为“LCA 深度最大”且“出现最早”的那一个？

image

我们会发现，其实 z，v 是一样的。

image

两个点的情况考虑完了，我们试试看正过来想，3 个点的情况怎么样合法呢？

image

image

你们大概地问了一下这个CZK这道题目怎么做，那么，其实这道题目是这样子的，其实我们也大概想到了一点，就是我们我在纸上写的时候，我想到了这个树上的差分。但是实际上因为它是一个归属问题，所以我们应该进行树上的染色。

image

我们不难发现，如果题目给出的是一个合法的 B 数组，我们可以把 B 数组当做 parent 数组，比较自然地连出一棵树。如果在这棵树上做 BFS，把从根节点出发的路径涂成它的 ID，（其实不是从根节点出发的路径，而是从这个点出发向上走。因为有一个 parent 数组，我们可以用这个 parent 指针不断地往上走，一直走到被涂到颜色的点。但如果是第一个点的话，那么肯定是一直走到根节点）那么后面的人向上涂色时，第一个必须经过的就是自己 B 数组的值（然后停下来）。他们不能经过其他的值，如果经过其他的值，那么就不行了。

AC代码

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

Posted on Edited on

题目大意

Dice Tower

时间限制: 2000 MS | 内存限制: 524288 KB

题目描述

联合演出结束后，Ave Mujica 的舞台机关还没有拆。睦留下了一批骰子道具，祥子想把它们堆成一座能从观众席各个方向看到的骰子塔；一旁的爱音则认真研究起怎样摆才能让露出的点数更多。

祥子在舞台平面上画出了一个 nn 行 mm 列的网格。第 ii 行第 jj 列的位置上堆着若干个完全相同的单位骰子。从正上方看，第 ii 行第 jj 列的骰子塔高度为 hi,jh_{i,j}，也就是说这个位置上堆了 hi,jh_{i,j} 个骰子。

所有骰子都与网格对齐，且同一个格子里的骰子上下紧贴摆放；若试图把它们摆歪，会被祥子立刻制止。

每个骰子的 66 个面分别有 1,2,3,4,5,61, 2, 3, 4, 5, 6 个点，且相对两面的点数和为 77。睦提醒大家，骰子各个面的相对位置固定：初始时，上、下、前、后、左、右六个面的点数依次为 1,6,2,5,3,41, 6, 2, 5, 3, 4；之后只能通过旋转改变朝向，不能将骰子翻成镜像。

爱音可以任意旋转每个骰子，并且不同骰子的朝向可以不同。相邻两个骰子贴在一起的面不会露出。一个骰子对答案的贡献等于它所有露出面的点数之和。

请你帮爱音求出所有骰子的贡献之和最大可以是多少。

输入格式

第一行包含一个整数 TT（1≤T≤1051 \le T \le 10^5），表示测试数据的组数。

对于每组测试数据：

  • 第一行包含两个整数 n,mn,m（1≤n,m≤1031 \le n,m \le 10^3），表示网格的行数和列数。

  • 接下来 nn 行，每行包含 mm 个整数，其中第 ii 行第 jj 个整数为 hi,jh_{i,j}（0≤hi,j≤1090 \le h_{i,j} \le 10^9），表示该位置上骰子塔的高度。

保证对于所有的测试数据，满足 ∑n×m≤106\sum n \times m \le 10^6。

输出格式

对于每组测试数据，输出一行一个整数，表示该组测试数据中露出面的最大点数之和。

样例输入

Plaintext

1
2
3
4
5
6
7
8
2
2 2
1 2
3 4
3 4
0 2 0 1
3 1 4 0
0 2 2 5

样例输出

Plaintext

1
2
156
314

样例解释

样例中的两组测试数据分别对应原来的两座骰子塔。

在第一组数据中，骰子塔的普通外表面积为 3434，但本题计算的是露出面上的点数之和。通过合理旋转每个骰子，可以使露出面的点数之和达到 156156。

注意： 最底层的骰子的下表面（即与舞台平面接触的面）也计入露出的表面并产生点数贡献。

思路讲解

那么这种实现方式比较复杂，是因为它没有实现轴的单独判别。

它是用面数进行判别的，那么实际上我们可以把单个块的逻辑给抽离出来。我们没有必要在遍历的时候，在同一个地方书写计算的逻辑。

这个函数的计数的计数原理就是我们知道一个相对面组，它的和一定是7，所以说如果凑齐了一个相对面，那么它的答案一定是贡献7，我们称一个相对面组为一个轴，轴中如果只有一个面，那么就是贡献6，5，4，我们优先给他分配比较高的面。

这个就是 axis1，acc1，和 origin_cost 的原理。

1
2
ll acc1 = accumulate(all(axis1), 0ll);
	ll res = ... + origin_cost[acc1];

完整的函数如下：

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
i128 origin_cost[] = {0, 6, 11, 15};
// X, Y是坐标，H是该点高度，ver是该点暴露在外的垂直面数量（夹在中间就是0，头尾就是1，2 只有块高度为一的时候）
i128 cal_single(ll x, ll y, ll h, ll ver) {
	if (h == 0) return 0;
	vector<ll> axis1(3), axis2(3);
	if (ver == 1) {
		axis1[2]++;
	} else if (ver == 2) {
		axis2[2]++;
	}
	for (int k = 0; k < 4; ++k) {
		auto [tox,toy] = make_tuple(x + dx[k], y + dy[k]);
		ll toh;
		// 小心这里，不要漏掉，也不要直接跳过
		if (tox < 1 || toy < 1 || tox > N || toy > M) {
			toh = 0;
		} else {
			toh = grid[tox][toy];
		}
		if (toh < h) {
			axis1[k & 1]++;
			if (axis1[k & 1] == 2) {
				axis1[k & 1] = 0;
				axis2[k & 1]++;
			}
		}
	}
	ll acc2 = accumulate(all(axis2), 0ll);
	ll acc1 = accumulate(all(axis1), 0ll);
	ll res = acc2 * 7 + origin_cost[acc1];
	return res;
}
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
i128 ans = 0;
for (int x = 1; x <= N; ++x) {
	for (int y = 1; y <= M; ++y) {
		ll h = grid[x][y];
		if (h == 0) {
			continue;
		}
		if (h == 1) {
			ans += cal_single(x, y, h, 2);
			continue;
		}
		ans += cal_single(x, y, 1, 1);
		ans += cal_single(x, y, h, 1);
		vector<ll> hls;
		// 注意一下哨兵值的设置
		// 如果设定为1的话，那么将无法计入1
		hls.push_back(0);
		for (int k = 0; k < 4; ++k) {
			auto [tox,toy] = make_tuple(x + dx[k], y + dy[k]);
			if (tox < 1 || toy < 1 || tox > N || toy > M) continue;
			if (grid[tox][toy] == 0) {
				continue;
			}
			if (grid[tox][toy] <= h) {
				hls.push_back(grid[tox][toy]);
			}
		}
		hls.push_back(h);
		// 不要忘记对HLS进行排序
		sort(all(hls));

		for (int k = 1; k < SZ(hls); ++k) {
			// 采用直接减法方法，所以说要把1给记进去的话，那么哨兵值必须得设为0。
			ll num = hls[k] - hls[k - 1];
			ans += num * cal_single(x, y, hls[k], 0);
		}
		ans -= cal_single(x, y, 1, 0);
		ans -= cal_single(x, y, h, 0);
	}
}
cout << ans << "\n";

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1234&rid=11474

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

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