[作业题] #8 CF578E

Walking

题目描述

点此看题

解法

首先考虑转化问题：我们可以把原序列划分成若干个 \(01\) 交替的子序列，然后再把 \(01\) 子序列交替拼起来，要求最小化 \(01\) 子序列的数量。

如果不考虑第二问，那么可以贪心地划分，假设现在要加入 \(1\)，如果有结尾为 \(0\) 的子序列，那么直接插到它后面去，否则新开一个子序列（如果为 \(0\) 类似）

因为贪心求出的是一个较好的下界，我们考虑直接用贪心的结果构造。首先观察到 \(01\) 可以自身合并（以 \(0\) 开头 \(1\) 结尾的子序列），也就是若干个 \(01\) 拼起来结果还是 \(01\)，\(10\) 也可以自身合并。

那么如果存在 \(11\) 或者 \(00\)，如果 \(11\) 的数量更多，那么可以构造出 10 11 01 00 11 00... 这样的结果，这是因为 \(00\) 和 \(11\) 数量之差不超过 \(1\)（如果 \(00\) 的数量更多，或者数量相等都类似）

如果不存在 \(11\) 或者 \(00\)，考虑调整出它们。如果全是 \(01/10\) 可以直接出解，否则我们可以那一组 \((01,10)\) 把他们调整成 \((00,11)\)，只需要判断结尾位置的大小关系即可。

#include 
#include 
#include 
#include 
using namespace std;
const int M = 100005;
#define pb push_back 
#define pp pop_back
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m;char s[M];vector v[M],id[2],z[2][2];
void adjust()
{
	if(!z[1][0].empty() || !z[1][0].empty()) return ;
	if(z[0][0].empty() || z[0][1].empty()) return ;
	int a=z[0][0].back(),b=z[0][1].back();
	if(v[a].back()z[0][1].size();
	while(!z[0][f^1].empty())
		print(z[0][f^1].back()),z[0][f^1].pp();
	while(!z[1][f].empty())
	{
		print(z[1][f].back());z[1][f].pp();
		while(!z[0][f].empty())
			print(z[0][f].back()),z[0][f].pp();
		f^=1;
	}
}