P10160 [DTCPC 2024] Ultra

题目背景

Tony2 喜欢玩某二字游戏，这一天他在小 C 面前展示他的 $\text{Ultra}$。

但是小 C 不会 $\text{Ultra}$，所以他跑去图图酱一去了。

然后图图失败了

于是小 C 趁 Tony2 不在的时候偷偷地把他的跳跃键和下冲键交换了（

题目描述

Tony2 的操作可以看作下冲和跳跃的组合。

称一个 $\text{Ultra}$ 为一段连续的操作，以下冲开头，然后跳跃和下冲交替，并以下冲结束。由于是 $\text{Ultra}$，所以至少要有一次跳跃。

小 C 每次可以将一个 $\text{Ultra}$ 变成 $\text{uLTRA}$，也就是将这个 $\text{Ultra}$ 的每个下冲变成跳跃，将每个跳跃变成下冲。

小 C 不喜欢 $\text{Ultra}$，所以想要使得下冲次数尽量少。

形式化题意

给你一个 $01$ 序列，你可以进行如下操作若干次（或零次）:

• 将序列中形如 $101\cdots 01$ 的一个子串（即 $1(01{)}^k$，$k\ge 1$）替换成等长的 $010\cdots 10$（即 $0(10{)}^k$）。

你要操作使得 $1$ 的个数尽可能少，输出最少的 $1$ 的个数。

输入格式

一行一个长度为 $n$（$n\le 10^6$） 的字符串表示这个 $01$ 序列。

输出格式

输出一个数表示最少的 $1$ 的个数。

输入输出样例 #1

输入 #1

1010011

输出 #1

3

说明/提示

样例 $1$ 解释：选中该串的前三个字符 $101$，对其操作后该串变为 $0100011$，仅包含 $3$ 个 $1$。容易证明这是最优的。

C++实现

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 10;
int n, ans; char s[MAXN];
int l[MAXN], r[MAXN], sum[MAXN], cnt;

int main() {
	scanf("%s", s + 1), n = strlen(s + 1);
	for (int i = 1; i <= n; i++) 
		if (s[i] == '1') 
			ans++;
	for (int i = 1; i <= n; i++) 
		sum[i] = sum[i - 1] + (s[i] & 1);
	for (int i = 1, j = 1, k = 0; i <= n; ) {
		if (s[i] != '1') { i++, k = 0; continue; }
		for (j = i; j + 2 <= n && s[j + 1] == '0' && s[j + 2] == '1'; j += 2);
		if (i != j) {
			if (cnt && r[cnt] + k + 1 == i) 
				r[cnt] = j;
			else 
				l[++cnt] = i - k, r[cnt] = j; k = 0;
		} else {
			if (cnt && l[cnt] != r[cnt] && r[cnt] + 1 == i) r[cnt]++;
			else k++;
		}
		i = j + 1;
	}
	for (int i = 1; i <= cnt; i++) 
		ans -= sum[r[i]] - sum[l[i] - 1] - 1;
	printf("%d", ans);
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容