专栏文章

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

PPyrf_uqcat
P11890题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipwq2d0
此快照首次捕获于
2025/12/03 19:11
3 个月前
此快照最后确认于
2025/12/03 19:11
3 个月前
查看原文
赛时搞了好久，做法是将每个子任务逐个击破。

子任务一

子任务说明 x≠0x\ne 0 且 y≠0y\ne 0。
无需考虑太多，当有 yy 个 xx 时，只需要在序列中放 yy 个 x−1x-1 就可以了，在前面把 00 到 x−2x-2 都需要至少放 11 个以保证 MEX⁡\operatorname{MEX} 为 xx。
可以拿下子任务一得到三十分。
CPP
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=2e5+5;

int n,ans[N]={-1},k;

struct Node
{
	int x,y;
}a[N];

bool flag[N];

map<int,int> mp;

bool cmp(Node x,Node y)
{
	return x.x<y.x;
}

signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		for(int j=ans[k]+1;j<a[i].x-1;j++)
		{
			ans[++k]=j;
		}
		while(a[i].y--) ans[++k]=a[i].x-1;
		if(k>2e5) cout<<-1<<endl,exit(0);
	}
	cout<<k<<endl;
	for(int i=1;i<=k;i++)
	{
		cout<<ans[i]<<' ';
	}
	cout<<endl;
	return 0;
}

子任务二

现在 yy 可能会等于 00 了。
当 xx 一个都没有时，说明不会出现 x−1x-1。既然不会出现 x−1x-1，则当有 xx 大于出现 00 次的数时，这个序列无法构造出来。只需用一个变量进行标志是否出现过 00，即可实现优化。
通过子任务二拿到六十分。
CPP
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=2e5+5;

int n,ans[N]={-1},k,flagg;

struct Node
{
	int x,y;
}a[N];

bool flag[N];

map<int,int> mp;

bool cmp(Node x,Node y)
{
	return x.x<y.x;
}

signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		if(flagg&&a[i].y) cout<<-1<<endl,exit(0);
		if(a[i].y==0)
		{
			flagg=1;
			continue;
		}
		for(int j=ans[k]+1;j<a[i].x-1;j++)
		{
			ans[++k]=j;
		}
		while(a[i].y--) ans[++k]=a[i].x-1;
		if(k>2e5) cout<<-1<<endl,exit(0);
	}
	cout<<k<<endl;
	for(int i=1;i<=k;i++)
	{
		cout<<ans[i]<<' ';
	}
	cout<<endl;
	return 0;
}

子任务三

当要出现 x=0x=0 时，则说明第一个数不能是零。而这是一个不递减队列，说明后面永远不会出现 00，那么后面的所有 MEX⁡\operatorname{MEX} 都等于 00。只有当后面所有的数都出现零次才行，所以再来一个变量进行标记是否出现过 x=0x=0。
拿下子任务三得到九十分。
CPP
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=2e5+5;

int n,ans[N]={-1},k,flagg,flaggg;

struct Node
{
	int x,y;
}a[N];

bool flag[N];

map<int,int> mp;

bool cmp(Node x,Node y)
{
	return x.x<y.x;
}

signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		if(flagg&&a[i].y) cout<<-1<<endl,exit(0);
		if(flaggg&&a[i].y) cout<<-1<<endl,exit(0);
		if(a[i].y==0)
		{
			flagg=1;
			continue;
		}
		if(a[i].x==0)
		{
			flaggg=1;
			continue;
		}
		for(int j=ans[k]+1;j<a[i].x-1;j++)
		{
			ans[++k]=j;
		}
		while(a[i].y--) ans[++k]=a[i].x-1;
		if(k>2e5) cout<<-1<<endl,exit(0);
	}
	if(flaggg)
	{
		cout<<a[1].y<<endl;
		for(int i=1;i<=a[i].y;i++)
		{
			cout<<1<<' ';
		}
		cout<<endl;
		return 0;
	}
	cout<<k<<endl;
	for(int i=1;i<=k;i++)
	{
		cout<<ans[i]<<' ';
	}
	cout<<endl;
	return 0;
}

子任务四

经过前三个子任务但还是有几个点没过，这是因为漏了一个特殊的样例。当 x=0x=0 且 y=0y=0 时，这就和子任务一样了，可以理解为没有这一次输入，判断一下即可。

赛时通过代码

CPP
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=2e5+5;

int n,ans[N]={-1},k,flagg,flaggg;

struct Node
{
	int x,y;
}a[N];

bool flag[N];

map<int,int> mp;

bool cmp(Node x,Node y)
{
	return x.x<y.x;
}

signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		if(a[i].x==0&&a[i].y==0) continue;
		if(flagg&&a[i].y) cout<<-1<<endl,exit(0);
		if(flaggg&&a[i].y) cout<<-1<<endl,exit(0);
		if(a[i].y==0)
		{
			flagg=1;
			continue;
		}
		if(a[i].x==0)
		{
			flaggg=1;
			continue;
		}
		for(int j=ans[k]+1;j<a[i].x-1;j++)
		{
			ans[++k]=j;
		}
		while(a[i].y--) ans[++k]=a[i].x-1;
		if(k>2e5) cout<<-1<<endl,exit(0);
	}
	if(flaggg)
	{
		cout<<a[1].y<<endl;
		for(int i=1;i<=a[i].y;i++)
		{
			cout<<1<<' ';
		}
		cout<<endl;
		return 0;
	}
	cout<<k<<endl;
	for(int i=1;i<=k;i++)
	{
		cout<<ans[i]<<' ';
	}
	cout<<endl;
	return 0;
}
题外：
这辈子写过最长的题解，四千多字符，同时也是写过的最复杂的方法。其实应该是可以直接推得结果的，但是赛时搞了好久每个子任务都错了一两个，只能使用这么不聪明的方法了。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...