题解 CF1458D 【Flip and Reverse】

题面

(T) 组询问，每次给定一个字符串，每次可以选择一个 1 和 0 数量相等的字符串，然后把字符串前后翻转并 01 翻转。求最后得到的字典序最小的字符串。

数据范围 : (T, n le 5 imes 10^5, sum n le 5 imes 10^5)

题解

刚才有个群友问我 Z 菜鸡发生肾摸事了，我说怎么回事？给我发了几张 CF 分数对比图，我一看！嗷！原来是昨天，我打了一场 CF，爆零了，掉分到 newbie ，又被嘲讽了。

首先假设我们有一个 (x) 值，遇到 (0), 让 (x) 减少 (1)；遇到 (1) 让 (x) 增加 (1)。

考虑按照原字符串建立一张图。对于每一个 (x) 值建立一个点。例如说现在的 (x) 值为 (t), 遇到了一个 (1), 然后我们从 (t) 到 (t + 1) 连一条无向边。

选择一个 1 和 0 数量相等的字符串，前后的 (x) 值一定相等。于是这就形成了一个环。

考虑将这个字符串取反，其实相当于从这个点绕着这个环走一圈。

然后我们要求的是这张图的最小字典序的欧拉路径。

可以考虑贪心，能向小的数走就往小数的走。

怎么判定数 (t) 能不能往小数 (t - 1) 走？首先一定要有 (t) 到 (t - 1) 的这条边，如果 (t) 有到 (t + 1) 的边那么 (t) 到 (t - 1) 的边数至少为 (2) （肯定要返回 (t)）。

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

代码

我菜，参考了 tourist 的

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = j, i##E = k; i <= i##E; i++) 
#define R(i, j, k) for(int i = j, i##E = k; i >= i##E; i--)
#define ll long long
#define ull unsigned long long 
#define db double
#define pii pair<int, int>
#define mkp make_pair
using namespace std;
const int N = 5e5 + 7;
const int inf = 1e9 + 7;
int n, cnt[N << 1];
char s[N];
void Main() {
	scanf("%s", s + 1), n = strlen(s + 1);
	int now = 0;
	L(i, 1, n) {
		if(s[i] == '1') cnt[N + now] ++, now ++; 
		else now --, cnt[N + now] ++;
	}
	now = 0;
	L(i, 1, n) {
		if(cnt[N + now - 1] > 0 && (!cnt[N + now] || cnt[N + now - 1] > 1)) --now, cnt[N + now] --, putchar('0');
		else cnt[N + now] --, now ++, putchar('1');
	}
	puts("");
	L(i, -n, n) cnt[N + i] = 0;
}
int main() {
	int T; scanf("%d", &T);
	while(T--) Main();
	return 0;
}

祝大家学习愉快！