自动搬运

查看原文

来自洛谷，原作者为

	Aw顿顿 直须看尽洛城花，始共春风容易别

搬运于2025-08-24 22:22:12，当前版本为作者最后更新于2020-04-15 09:14:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

『JROI-1』蒟蒻火锅的盛宴-赛后题解

$\rm Description$ 题意解释

题面已经更改为了简化版题目

这里解释一下题意吧：

• 一共有 $n$ 个整数。

• 存在一个集合 $G$，初始情况含有给定的 $m$ 个整数。

• 若 $m\in G$，则必然存在 $(m+a)\in G$。

问至少增加几个元素可以保证此集合没有可以加入的元素。

$\rm Solution$ 解题思路

• 暴力 $n^2$ 模拟，使用 $\rm O_2$ 期望得分 $25pts$。

原本的思路是直接暴力模拟。

其核心思想为：

• 读入，如果 $a_i>mx$ 就 $mx=a_i$，这个东西其实只是做一个简单的优化而已。

• 对于每个 $b_i$，寻找其对应的 $a_i$ 是否存在：

  • 如果不存在此食材，跳过。

  • 否则 $ans=ans+1$。

这种方法的复杂度是 $O(n^2)$。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[50001],b[50001],m,mx=-1,x,ans,s;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]>mx)mx=a[i];
	}
	cin>>m;ans=m;
	for(int i=1;i<=m;i++)cin>>b[i];
	cin>>s;
	for(int i=1;i<=ans;i++){
		bool f=false;
		if(b[i]+s>mx)continue;
		for(int j=1;j<=n;j++)if(b[i]+s==a[j]){
			f=true;
			break;
		}
		if(!f)continue;
		f=false;
		for(int j=1;j<=ans;j++)if(b[i]+s==b[j]){
			f=true;
			break;
		}
		if(!f)b[++ans]=b[i]+s;
	}
	if(ans==m)puts("Great Set!");
	else cout<<ans-m<<endl;
    return 0;
}

加上快读和快输及八聚氧开启全部卡常技能也许可以拿到更高分（？）。

• 优化模拟倍数标记，期望得分 $60pts$。

比上面的稍微优化，其实是类似的。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
   register int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}int q[10000001],l=1,r=1; 
int n,m,ans,x,v,mx=-1;
bool t[600001];
int main(){
//	freopen("30.in","r",stdin);
//	freopen("30.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++){
		v=read();
		if(v>mx)mx=v;
	}m=read();
	for(int i=1;i<=m;++i){
		v=read();
		t[v]=1;
		q[r++]=v;
	}x=read();
	for(int i=1;i<r;i++){
		for(int j=q[i];j<=mx;j+=x)if(!t[j]){
			t[j]=1;
			q[r++]=j;
			ans++;
		}
	}if(ans)cout<<ans<<endl;
	else puts("Great Set!");
	return 0;
}

直接交不加八聚氧也可以拿到 $60pts$。

• 队列循环标记，期望得分：$100pts$。

有一个用空间换时间的办法：

我们的内部循环都是在寻找这个数是否存在，那么如果我们输入的时候做一个标记可以省下来一个循环。

简单来说，我们可以开 $2$ 个桶进行标记。

然后我们就只有一个 while 循环每次加入的过程了。

这个算法的时间复杂度大致为 $O(n)$。

输入 $n+m$ 次，循环最多 $n$ 次。

代码：

#include<bits/stdc++.h>
using namespace std;
queue<int>q;
int n,m,ans,x,l;
bool t1[600001],t2[600001];
int main(){
	cin>>n;
	for(register int i=1;i<=n;i++){
		cin>>l;
		t1[l]=1;
	}cin>>m;
	for(register int i=1;i<=m;++i){
		cin>>l;
		t2[l]=1;
		q.push(l);
	}cin>>x;
	while(!q.empty()){
		int l=q.front();
		if(!t1[l+x]){
			q.pop();
			continue;
		}if(!t2[l+x]){
			q.push(l+x);
			t2[l+x]=1;
			++ans;
		}q.pop();
	}
	if(ans)cout<<ans<<endl;
	else puts("Great Set!");
	return 0;
} 

当然也可以手写和快读实现，以达到更快的效果：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
   register int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}int q[600001],l=1,r=1,n,m,ans,x,v;
bool t1[600001],t2[600001];
int main(){
	n=read();
	for(register int i=1;i<=n;i++){
		v=read();
		t1[v]=1;
	}m=read();
	for(register int i=1;i<=m;++i){
		v=read();
		t2[v]=1;
		q[r++]=v;
	}x=read();
	while(l<r){
		int v=q[l];
		if(!t1[v+x]){
			++l;
			continue;
		}if(!t2[v+x]){
			q[r++]=v+x;
			t2[v+x]=1;
			++ans;
		}++l;
	}
	if(ans)cout<<ans<<endl;
	else puts("Great Set!");
	return 0;
} 

这样你就 AC 了一道十分简单的签到题。

最后附上一些挺有意思的赛时代码：

@Marser

#include<bits/stdc++.h>
#define reg register
typedef long long ll;
using namespace std;
int n,m,a;
set<int>S1,S2;
int main(){
	scanf("%d",&n);
	for(reg int i=1,x;i<=n;i++)
		scanf("%d",&x),S1.insert(x);
	scanf("%d",&m);
	for(reg int i=1,x;i<=m;i++)
		scanf("%d",&x),S2.insert(x);
	scanf("%d",&a);reg int Ans=0;
	for(auto x:S2)if(S1.count(x+a)&&!S2.count(x+a))Ans++,S2.insert(x+a);
	if(Ans)printf("%d\n",Ans);
	else puts("Great Set!");
	return 0;
}