Codeforces Round 1114 (Div. 3)

kevin 2026-08-05

411 观看次数

1189 字数

0 评论

无标签.. 习题

Codeforces Round 1114 (Div. 3) 题解

比赛链接：Codeforces Round 1114

B. Evanescent

题意

定义 $f(s)$ 为字符串 $s$ 的压缩版本：将每个由相同字符组成的极长连续段替换为该字符的一个副本。
例如 $f(\texttt{"aabbcc"}) = \texttt{"abc"}$。

$|f(s)|$ 表示压缩后字符串的长度。空串的长度为 $0$。

给定一个长度为 $n$ 的小写字母字符串 $s$，你必须恰好删除一个字符 $s_i$（其中 $2 \le i \le n-1$，即不能删首尾字符），得到新串 $s'$。求 $|f(s')|$ 的最小可能值。

思路

压缩长度的本质

每一段贡献一个字符。第一段自然存在，之后每发生一次「相邻字符不同」，就说明进入了新的一段，长度就 $+1$。

所以不需要真的去压缩，直接数相邻不同对就行：

$$ |f(s)| = 1 + (\text{相邻不同的位置个数}) $$

具体到代码就是：初始化 cnt = 1，然后扫一遍字符串，每当 $s_i \neq s_{i-1}$ 就把 cnt++。

删除的局部影响

设原串压缩长度为 $\textit{cnt}$。当我们删除位置 $i$ 的字符时，只有三对相邻关系发生变化，其余部分完全不变：

关系	变化	对长度的贡献
$(s_{i-1}, s_i)$	消失	若 $s_{i-1} \neq s_i$，则 $-1$
$(s_i, s_{i+1})$	消失	若 $s_i \neq s_{i+1}$，则 $-1$
$(s_{i-1}, s_{i+1})$	新产生	若 $s_{i-1} \neq s_{i+1}$，则 $+1$

因此删除位置 $i$ 后的新长度为：

$$ \textit{cur} = \textit{cnt} - [s_i \neq s_{i-1}] - [s_{i+1} \neq s_i] + [s_{i+1} \neq s_{i-1}] $$

遍历所有合法删除位置 $i \in [1, n-2]$（0-based），取最小值即可。每个位置的代价是 $O(1)$，总复杂度 $O(n)$。

算法步骤

读入 $t$ 组数据。
对每组数据：
- 读入 $n$ 和字符串 $s$。
- 计算原始压缩长度 $\textit{cnt}$：初始 $\textit{cnt} = 1$，遍历 $i = 1 \dots n-1$，若 $s_i \neq s_{i-1}$ 则 $\textit{cnt} \mathrel{+}= 1$。
- 初始化 $\textit{ans} = \textit{cnt}$。
- 遍历 $i = 1 \dots n-2$，按上述公式计算 $\textit{cur}$，更新 $\textit{ans} = \min(\textit{ans}, \textit{cur})$。
- 输出 $\textit{ans}$。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;

        int cnt = 1;
        for (int i = 1; i < n; i++)
            if (s[i] != s[i - 1]) cnt++;

        int ans = cnt;
        for (int i = 1; i < n - 1; i++) {
            int cur = cnt;
            if (s[i] != s[i - 1]) cur--;
            if (s[i + 1] != s[i]) cur--;
            if (s[i + 1] != s[i - 1]) cur++;
            ans = min(ans, cur);
        }
        cout << ans << '\n';
    }
    return 0;
}

复杂度

时间复杂度：$O(n)$ 每组。
空间复杂度：$O(1)$ 额外空间。

易错点

$\textit{cnt}$ 初始化为 $1$ 而非 $0$：非空字符串至少有一段。
遍历范围是 $[1, n-2]$（0-based），对应题目中的 $2 \le i \le n-1$（1-based）。
当 $n \le 2$ 时循环不执行，直接输出 $\textit{cnt}$，无需特判。

C1. Marenol (easy version)

题意

给定两个长度均为 $n$ 的二进制字符串 $a$ 和 $b$。每次操作可以选择 $a$ 中的一个长度为 $3$ 的子串进行变换：

$001 \longleftrightarrow 100$
$110 \longleftrightarrow 011$

判断是否能通过有限次操作将 $a$ 变为 $b$。

思路

寻找不变量

观察两类操作的本质：

操作	左 → 右	含义
$001 \to 100$	唯一的 `1` 从位置 $3$ 移到位置 $1$	`1` 向左跳 $2$ 格
$100 \to 001$	唯一的 `1` 从位置 $1$ 移到位置 $3$	`1` 向右跳 $2$ 格
$110 \to 011$	最左边的 `1` 从位置 $1$ 移到位置 $3$（中间的 `1` 不动）	一个 `1` 向右跳 $2$ 格
$011 \to 110$	最右边的 `1` 从位置 $3$ 移到位置 $1$	一个 `1` 向左跳 $2$ 格

关键发现：

1 的总数不变：每个操作只是重新排列已有的 1，不增不减。
移动步长恒为 $2$：每次 1 移动恰好 $2$ 个位置。
下标奇偶性不变：因为步长是 $2$，位于奇数位（1-based）的 1 永远在奇数位，偶数位的 1 永远在偶数位。

因此，充要条件为：

$a$ 和 $b$ 中 1 的总数相等；
$a$ 和 $b$ 中奇数下标上 1 的数量相等（偶数下标上的数量自然也随之相等）。

算法步骤

读入 $t$ 组数据。
对每组数据：
- 读入 $n$ 和两个字符串 $a, b$。
- 统计 $a$ 和 $b$ 中：
  - 1 的总数 $c_a, c_b$；
  - 奇数位（1-based）上的 1 的数量 $\textit{odd}_a, \textit{odd}_b$。
- 若 $c_a = c_b$ 且 $\textit{odd}_a = \textit{odd}_b$，输出 Yes，否则输出 No。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        string a, b;
        cin >> n >> a >> b;

        int ca = 0, cb = 0, oa = 0, ob = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == '1') {
                ca++;
                if (i % 2 == 0) oa++;  // 0-based 的偶数位对应 1-based 的奇数位
            }
            if (b[i] == '1') {
                cb++;
                if (i % 2 == 0) ob++;
            }
        }

        cout << (ca == cb && oa == ob ? "Yes" : "No") << '\n';
    }
    return 0;
}

复杂度

时间复杂度：$O(n)$ 每组。
空间复杂度：$O(1)$ 额外空间。

易错点

直接用 vector<int>(s.begin(), s.end()) 构造向量会得到 ASCII 码（'0' → $48$，'1' → $49$），导致判断 == 0 永远为假。直接用 string 和字符比较最安全。
注意 0-based 和 1-based 下标转换：代码中 i % 2 == 0 对应 1-based 的奇数位。

C2. Marenol (hard version)

题意

在 C1 的基础上，如果可以将 $a$ 变为 $b$，求最小操作次数；如果不能则输出 $-1$。

思路

从「可行性」到「最小步数」

C1 已经得出：一次操作就是让一个 1 移动恰好 2 格，且奇偶性不变。因此：

一个 1 从位置 $p$ 移动到位置 $q$（$p, q$ 同奇偶），需要 $\dfrac{|p - q|}{2}$ 次操作。
同一奇偶组内，1 的相对顺序不会跨越（因为每次只移 2 格，两个 1 不可能互相穿过），所以最优配对就是按出现顺序一一对应。

这个下界实际上总是可达的：每次找到第一个不在目标位置的 1，它总能通过 001↔100 或 110↔011 向目标方向移动，不会被卡住。

算法步骤

用两个数组分别记录 $a$ 和 $b$ 中偶数和奇数下标上 1 的出现位置（0-based）。
若任一同奇偶组内 $a$ 和 $b$ 的 1 个数不等，输出 $-1$。
否则，每组内按顺序配对，累加 $\dfrac{|\text{pos}_a - \text{pos}_b|}{2}$。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        string a, b;
        cin >> n >> a >> b;

        vector<int> pa[2], pb[2];
        for (int i = 0; i < n; i++) {
            if (a[i] == '1') pa[i % 2].push_back(i);
            if (b[i] == '1') pb[i % 2].push_back(i);
        }

        if (pa[0].size() != pb[0].size() || pa[1].size() != pb[1].size()) {
            cout << -1 << '\n';
            continue;
        }

        long long ans = 0;
        for (int p = 0; p < 2; p++)
            for (int i = 0; i < (int)pa[p].size(); i++)
                ans += abs(pa[p][i] - pb[p][i]) / 2;

        cout << ans << '\n';
    }
    return 0;
}

复杂度

时间复杂度：$O(n)$ 每组。
空间复杂度：$O(n)$（存储位置数组）。

总结

这三题都体现了「寻找不变量 / 局部性质」的优化思想：

B 题：压缩长度 $=$ 相邻不同对数 $+ 1$，删除只影响局部三个位置的关系。
C1 题：操作的本质是 1 以步长 $2$ 移动，因此 1 的总数和奇偶分布是不变量，简单计数即可判断。
C2 题：在 C1 的基础上，同一奇偶组内的 1 按顺序配对，步数就是距离除以 $2$ 的累加。