自动搬运

查看原文

来自洛谷，原作者为

	xcms txz

搬运于2025-08-24 22:57:00，当前版本为作者最后更新于2024-04-10 21:47:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10330 [UESTCPC 2024] 黑白珠串

这道题我刚看到时也很懵，不知道从何入手。结果一分析样例，我发现了规律，于是秒切了这道题。

我们发现样例输出的字符串都是先一些 1，再是一些 0。发现 1 的数量刚好是 $y$ 序列中的最大值，0 的数量是 $x_i-y_i$ 的最大值。

$y_i$ 指长度为 $x_i$ 的子串中 1 的数量，所以 $y$ 序列中的最大值，就是 1 的数量。而 $x_i-y_i$ 指长度为 $x_i$ 的子串中 0 的数量，所以 $x_i-y_i$ 的最大值，就是 0 的数量。

最后起始点输出只需输出 1 的总数 $-$ $y_i$ 即可。

std

#include <iostream>
using namespace std;
const int N=1e5+10;
int x[N],y[N];
int main(){
	int k;
	cin>>k;
	int n=-1e9,m=-1e9;
	for(int i=1;i<=k;i++){
		cin>>x[i]>>y[i];
		n=max(n,y[i]);
		m=max(m,x[i]-y[i]);
	}
	cout<<n+m<<"\n";
	for(int i=1;i<=n;i++)cout<<"1";
	for(int i=1;i<=m;i++)cout<<"0";
	cout<<"\n";
	for(int i=1;i<=k;i++)cout<<n-y[i]<<"\n";
	
	return 0;
}