洛谷P17589题解

分析

题意

给定长度为 $n$ 的 01 串，$a_i=1$ 代表会员，$0$ 代表不是。

一共有 $m$ 次翻转操作，每次操作指定位置 $x$，可以把 $a_x$ 取反（$0$ 变 $1$，$1$ 变 $0$）。

我们可以任选其中一部分操作执行，目标是让最终序列里 $1$ 的数量尽可能大，求这个最大值。

思路

同一个位置如果出现多次翻转操作，我们只关心这个位置有没有被选中翻转，翻转偶数次等于没翻，奇数次等于翻一次。所以对于每个位置：

1. 如果这个位置在 $m$ 次操作里出现过：我们可以自主选择翻或者不翻。
   • 原数是 $0$：翻一下变成 $1$，赚 $1$ 个会员，肯定翻。
   • 原数是 $1$：翻一下变成 $0$，亏 $1$ 个会员，肯定不翻。
2. 如果这个位置在 $m$ 次操作里没出现过：不能翻转，保持原样。

做法：

1. 先统计原始串中 $1$ 的总数。
2. 标记所有在操作列表中出现过的下标。
3. 遍历所有下标，如果下标被标记且原值是 $0$，说明我们可以把它翻成 $1$，答案加上这部分的数量。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
char a[MAXN];
bool vis[MAXN];
int main() {
    int n, m;
    cin >> n >> m;
    scanf("%s", a + 1);
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == '1') sum++;
    }
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        vis[x] = 1;
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[i] && a[i] == '0') res++;
    }
    cout << sum + res << endl;
    return 0;
}