题解：P12150 【MX-X11-T4】「蓬莱人形 Round 1」视奸

chenly8128 · 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;
}