『JROI-1』蒟蒻火锅的盛宴-赛后题解
『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 。
-
这种方法的复杂度是
代码：
#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;
}直接交不加八聚氧也可以拿到
- 队列循环标记，期望得分：
100pts 。
有一个用空间换时间的办法：
我们的内部循环都是在寻找这个数是否存在，那么如果我们输入的时候做一个标记可以省下来一个循环。
简单来说，我们可以开
然后我们就只有一个 while 循环每次加入的过程了。
这个算法的时间复杂度大致为
输入
代码：
#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;
}