【题解】CF1678B1 Tokitsukaze and Good 01-String (easy version)

qW__Wp · 2024-11-09 19:00:42 · 题解

下文中的“字符串”表示 01 字符串；s 表示给定的字符串，t 表示可能的答案字符串。

为了方便叙述，我们作如下定义：

• 单元：如果一个字符串 a 被分为若干个长度为 2 的子串，称这些子串为 a 的单元。
• 完美单元：对于一个单元 b，若 b_1=b_2，则称 b 为一个完美单元
• 非完美单元：一个不是完美单元的单元称为一个非完美单元。
• 完美字符串：一个由若干个完美单元拼接而成的字符串称为完美字符串。

根据题意，t 可以被分为若干个完美字符串，因此 t 也是一个完美字符串。因此最优策略就是对 s 的所有非完美单元中的任一字符进行一次操作使其变为完美单元，最终 s 也会变为一个完美字符串，答案即为 s 中的非完美单元的数量。

时间复杂度 O(\sum n)。

Code:

#include <bits/stdc++.h>
//#define int long long
#define INF 0x3fffffff
#define INFF 1e18

using namespace std;

const int N = 2e5 + 5;

signed main() {
    int T; cin >> T;
    while (T --) {
        int n; cin >> n;
        string s; cin >> s;
        s = " " + s;
        int ans = 0;
        for (int i = 2; i <= n; i += 2) {
            if (s[i] != s[i - 1]) {
                ans ++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}