自动搬运

查看原文

来自洛谷，原作者为

	chenly8128 God helps those who help themselves.

搬运于2025-08-24 23:13:10，当前版本为作者最后更新于2025-04-13 20:29:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

细节题，赛时交了 5 发才过。

这题需要分段分类。

题目中说“过程中可以超过 $[1,n]$”，但是因为超过 $[1,n]$ 的节点没法被删掉（或者说删掉后会产生至少一个另外的、超出 $[1,n]$ 的节点），不可能与集合 $B$ 匹配，所以实际上不能超过 $[1,n]$。（当然，笔者实力有限，没有想明白为什么题目里会有这么一句话，这一段分析可能是胡扯，欢迎批评指正）。

part 1

首先考虑特殊性质 B 怎么做。如果没有 101 那么，很明显操作从来没有进行过，不然一定会产生 101 结构。于是直接统计每个需要选择的元素的权值累加和即可。

part 2

对于 $B$ 中形如 X0…0Y 形式的结构（0 至少两个），中间所有 0 代表的集合元素，都不能在 $A$ 中出现。否则这样的元素 $a$ 删掉后，与它相邻的、$B$ 中没有出现的元素 $b$ 就会出现；为了与 $B$ 匹配，只能再删除 $b$，然后 $a$ 就会出现。以上过程循环交替，永远不可能使得 $a$ 和 $b$ 同时被删除。

根据以上结论，可以将 $B$ 分段。凡是出现连续两个 0 的位置，都要把 $B$ 分为两段，两段之间一定互不干扰。特别的，为了代码方便，首尾都加上两个 0 作为哨兵。

现在只需要在每一段中处理这个问题了。

part 3

如果某一段满足性质 B，那么直接用 part 1 方法求解。如果不满足性质 B，那么该段长度至少为 $3$：

• 如果该段长度为 $3$：那么该段只能为 101，此时需要分类特判。$A$ 有 111，101，011，110，010 这几种选法，计算最优解即可。
• 如果该段长度大于 $3$：假设 $B$ 中该段形式如 1X1，只要在 $A$ 的 X 段中有元素被选择，那么整一段一定可以通过若干次操作与 $B$ 吻合。因此只需要根据贪心思想，选择所有负权值的节点即可。然而根据结论，如果 $A$ 的 X 中一个节点都没有选择，那么必须强制选择权值最小的非负节点。

参考代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5+10;
int c,T,n,v[MAXN],sum[MAXN],sum2[MAXN];
char s[MAXN];
signed main (void) {
	scanf ("%lld%lld",&c,&T);
	while (T--) {
		scanf ("%lld%s",&n,s+1);
		for (int i = 1;i <= n;i++) scanf ("%lld",v+i);
		for (int i = 1;i <= n;i++) {
			sum[i] = sum[i-1] + min(0ll,v[i]);
			sum2[i] = sum2[i-1] + v[i];
		}
		int ans = 0,st = 1,p = 1e16;
		s[0] = s[n+1] = s[n+2] = '0';
		bool b = false;
		for (int i = 1;i <= n+2;i++) {
			if (s[i] == '0' && s[i-1] == '0') {
				st = i+1;
				p = 1e16;
				b = false;
				continue;
			}
			if (s[i] == '0' && s[i+1] == '0') {
				int ed = i-1;
				if (st <= ed) {
					if (b) {
						if (ed - st == 2) {
							if (v[st+1] < 0) {
								ans += sum[ed] - sum[st-1];
								continue;
							}
							if ((v[st] >= 0 && v[ed] >= 0)
								|| (v[st] < 0 && v[ed] < 0))
								ans += min(v[st+1],v[st]+v[ed]);
							else if (v[st] < 0) ans += v[st] + min(v[st+1],v[ed]);
							else ans += v[ed] + min(v[st+1],v[st]);
						}
						else {
							ans += sum[ed] - sum[st-1];
							if (sum[ed-1] - sum[st] == 0) ans += p;
						}
					}
					else ans += sum2[ed] - sum2[st-1];
				}
				continue;
			}
			if (i-1 > st) p = min(p,v[i-1]);
			if (s[i] == '1' && s[i-1] == '0' && i != st) b = true;
		}
		printf ("%lld\n",ans);
	}
	return 0;
}