题解：P11890 [XRCOI Round 1] A. 相聚相逢本无意

别的不说，赛时硬控3h，赛后一摸马上出TnT

题面
形式化题意:给出 $n$ 个数字的出现次数，构造单调不减序列 $A$ ,使 $A$ 的 $前缀Mex$ 数组 $B$ 满足这 $n$ 个数字的约束条件~，无解输出 $-1$
MEX 为数列中不包含的最小非负整数。比如 MEX{1,2,3}=0,MEX{0,1,2,4}=3
比如我要让 $1$ 出现 $5$ 次,可以构建形如 $0\ 0\ 0\ 0\ 0$ 的序列，如果加上让 $2$ 出现 $5$ 次,序列就能变成

$0\ 0\ 0\ 0\ 0\ 1\ 1\ 1\ 1\ 1\$
什么时候无解呢？让 $1$ 出现 $0$ 次, $2$ 却出现要出现 $1$ 次, $A$ 是单调不减的,出现 $2$ 就必须出现 $1$ ......
好的,给出代码,完结撒花~

#include<bits/stdc++.h>
using namespace std;
int read(){//快读 
	int sum=0,k=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();
	}while(c>='0'&&c<='9'){sum=sum*10+c-48;c=getchar();
	}return sum*k;
}
bool vis[200];
int hp[200];
signed main(){
	int n=read(),maxx=-1000,ans=0;
	for(int i=1;i<=n;i++){
		int pos=read(),num=read();//这个数pos 与出现次数 num 
		maxx=max(maxx,pos);//记录最大数 
		vis[pos]=1;//这个数出现次数有约束...... 
		hp[pos]=num;//出现次数 
		ans+=num;//A数列的长度 
	}
	for(int i=1;i<maxx;i++)
	if(vis[i]&&hp[i]==0){//这个数有约束且出现次数为0
	//还有更大的数要出现，判断无解 
			printf("-1\n");
			return 0;
	}else if(!vis[i]) ans++,hp[i]=1;//这个数至少出现一次 
	printf("%lld\n",ans);
	for(int i=1;i<=maxx;i++)
		for(int j=1;j<=hp[i];j++) cout<<i-1<<" ";//输出 
	return 0;
}

$30pts$ 恭喜

很明显，

这个 $0$ 很重要,来分析一下这个 $0$ ~

如果最大数要出现 $0$ 次,就不管它了!
好的,给出代码,完结撒花~

#include<bits/stdc++.h>
using namespace std;
int read(){//快读 
	int sum=0,k=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();
	}while(c>='0'&&c<='9'){sum=sum*10+c-48;c=getchar();
	}return sum*k;
}
bool vis[200];
int hp[200];
signed main(){
	int n=read(),maxx=-1000,ans=0;
	for(int i=1;i<=n;i++){
		int pos=read(),num=read();//这个数pos 与出现次数 num 
		if(num!=0) maxx=max(maxx,pos);//记录最大数 
		vis[pos]=1;//这个数出现次数有约束...... 
		hp[pos]=num;//出现次数 
		ans+=num;//A数列的长度 
	}
	for(int i=1;i<maxx;i++)
	if(vis[i]&&hp[i]==0){//这个数有约束且出现次数为0
	//还有更大的数要出现，判断无解 
			printf("-1\n");
			return 0;
	}else if(!vis[i]) ans++,hp[i]=1;//这个数至少出现一次 
	printf("%lld\n",ans);
	for(int i=1;i<=maxx;i++)
		for(int j=1;j<=hp[i];j++) cout<<i-1<<" ";//输出 
	return 0;
}

~~double kill!~~

手膜一下,如果 $B$ 中要出现 $0$ ,那么一定不会出现 $1\ 2\ 3\ 4\ 5$ 这些数字了, $A$ 是单调不减的,出现了 $0$ 第一位一定是 $>0$ 的数,之后再也无法回到 $0$ 让 $Mex$ 为 $1$ 与之后的数了
梅开三度

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
	int sum=0,k=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();
	}while(c>='0'&&c<='9'){sum=sum*10+c-48;c=getchar();
	}return sum*k;
}
bool vis[200];
int hp[200];
bool flag = 0;
signed main(){
	int n=read(),maxx=-1000,ans=0;
	for(int i=1;i<=n;i++){
		int pos=read(),num=read();
		if(num!=0) maxx=max(maxx,pos);
		if(pos==0)//0出现了 
			flag=1;
		vis[pos]=1;
		hp[pos]=num;
		ans+=num;
	}
	for(int i=1;i<maxx;i++) if(vis[i]&&hp[i]==0){
			printf("-1\n");
			return 0;
	}else if(!vis[i]&&!flag) ans++,hp[i]=1;
	if(flag){
		if(ans!=hp[0]){//除了0还有别的数 
			cout<<-1<<endl;//无解 
			return 0;
		}
		cout<<hp[0]<<endl;
		for(int i=1;i<=hp[0];i++) cout<<1<<" ";
		return 0;	
	}
	printf("%lld\n",ans);
	for(int i=1;i<=maxx;i++)
		for(int j=1;j<=hp[i];j++) cout<<i-1<<" ";
	return 0;
}

hack:

2

1 1

0 0

0也可以不出现!!!!!!
~~四连,天下无双~~

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
	int sum=0,k=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();
	}while(c>='0'&&c<='9'){sum=sum*10+c-48;c=getchar();
	}return sum*k;
}
bool vis[200];
int hp[200];
bool flag = 0;
signed main(){
	int n=read(),maxx=-1000,ans=0;
	for(int i=1;i<=n;i++){
		int pos=read(),num=read();
		if(num!=0) maxx=max(maxx,pos);
		if(pos==0&&num!=0)
			flag=1;
		vis[pos]=1;
		hp[pos]=num;
		ans+=num;
	}
	for(int i=1;i<maxx;i++) if(vis[i]&&hp[i]==0){
			printf("-1\n");
			return 0;
	}else if(!vis[i]) ans++,hp[i]=1;
	if(flag){
		if(ans!=hp[0]){
			cout<<-1<<endl;
			return 0;
		}
		cout<<hp[0]<<endl;
		for(int i=1;i<=hp[0];i++) cout<<1<<" ";
		return 0;	
	}
	printf("%lld\n",ans);
	for(int i=1;i<=maxx;i++)
		for(int j=1;j<=hp[i];j++) cout<<i-1<<" ";
	return 0;
}