题解 P3940 分组

有些梦想虽然遥不可及,但不是不可能实现。只要我足够的强。

前言

调了挺长时间的,并查集合并的时候需要 find 一下,不然会炸内存。。。。

解题思路

参考了题解区一篇思路非常好的题解,在这里讲一下自己的见解。

首先明确一下 K 的取值只有 1 或者 2 这里看数据范围非常重要!,对于 \(K=1\),\(K=2\) 的情况要分开来做。

K=1

对于 \(K=1\) 的情况,为了保证字典序最小,我们需要倒着枚举序列了。

然后再次观察数据范围,发现\(131072 \times2=512^2\),因此我们可以枚举 \(1 \sim 512\) ,令 vis[i] 表示在当前扫到的组里颜色为 i 的是否存在,查看是否访问过 \(x^2-s_i\) 。

  • 如果访问过,表示和第 i 只兔子发生矛盾的已经在这个组里了,因此需要再次分一个组,并且记录下分组的边界,清空 vis 数组。

  • 如果没有访问过,把该种颜色的标记成 true 记录就好了。

K=2

几乎同样的思路,我们仍然需要倒着枚举序列。

对于同一组的兔子,状态之可能有两种:同一小团体或者在敌对小团体,因此我们用并查集维护。

  • \(\operatorname{find}(1 \sim n)\) 表示 \(1\sim n\)的兔子所在的小团体。

  • \(\operatorname{find}(n+1 \sim 2 \times n)\) 表示 \(1\sim n\)的兔子所在的小团体的敌对小团体。

然后开一个 vector 数组记录同一颜色的序号,然后分别对于发生矛盾的兔子进行判断,同时更新该兔子所在组以及小团体和敌对小团体。

同样的,如果矛盾无法避免,那就重新开一个组,并清空标记,记录分割点就好了。

code

#include<bits/stdc++.h>
using namespace std;
const int M=131080;
int n,m,K,las,s[M],fa[M<<1];
vector<int> ans,v[M<<1];
bool vis[M];
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
void work_1()
{
	for(int i=n;i>=1;i--)
	{
		bool flag=true;
		for(int j=1;j<=512;j++)
			if(j*j>=s[i])
				if(vis[j*j-s[i]])
				{
					flag=false;
					break;
				}
		if(!flag)
		{
			for(int j=i+1;j<las;j++)
				vis[s[j]]=false;
			ans.push_back(i);
			las=i+1;
		}
		vis[s[i]]=true;
	}
	printf("%d\n",ans.size()+1);
	for(int i=ans.size()-1;i>=0;i--)
		printf("%d ",ans[i]);
}
int update(int l,int r)
{
	for(int i=l+1;i<r;i++)
		vector <int>().swap(v[s[i]]);
	ans.push_back(l);
	return l+1;
}
void work_2()
{
	for(int i=1;i<=(n<<1);i++)
		fa[i]=i;
	for(int i=n;i>=1;i--)
	{
		for(int j=1;j<=512;j++)
			if(j*j>=s[i])
				if(v[j*j-s[i]].size())
					for(int k=0;k<v[j*j-s[i]].size();k++)
					{
						int temp=v[j*j-s[i]][k];
						if(find(temp)==find(i))
						{
							las=update(i,las);
							break;
						}
						else
						{
							fa[find(i+n)]=find(temp);
							fa[find(temp+n)]=find(i);
						}
					}
		v[s[i]].push_back(i);
	}
	printf("%d\n",ans.size()+1);
	for(int i=ans.size()-1;i>=0;i--)
		printf("%d ",ans[i]);
}
int main()
{
	scanf("%d%d",&n,&K);
	las=n+1;
	for(int i=1;i<=n;i++)
		scanf("%d",&s[i]);
	if(K==1)
		work_1();
	else
		work_2();
	return 0;
}
上一篇:【洛谷7016】[CERC2013] Captain Obvious and the Rabbit-Man(手动高斯消元)


下一篇:iOS 14.7 Developer Beta 2 登场双卡出现请勿故障更新?