题解：P14118 [SCCPC 2021] Hotpot

简单的奇偶性问题。

因为

n\le10^5

且

m\le10^9

，用

\mathcal{O}(n^2)

的暴力就行不通了。

看到模数，想到~~约瑟夫环~~奇偶性判断。

容易看出，在每一次循环中，若喜欢某个食材的总人数为偶数，喜欢其的第奇数个人吃不到，喜欢其的第偶数个人能吃到；若喜欢某个食材的总人数为奇数，喜欢其的第奇数个人在第偶数个循环能吃到，喜欢其的第偶数个人在第奇数个循环能吃到。

于是我们就发现了

\mathcal{O}(n)

的方法。

注意，

i \in [0,n-1]

，所以 for 循环应从 0 开始！

AC Code：

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m,k,a[maxn],b[maxn],c[maxn],ans[maxn];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(c,1,sizeof(c));
		memset(ans,0,sizeof(ans));
		scanf("%d%d%d",&n,&k,&m);
		for(int i=0;i<n;++i){
			scanf("%d",&a[i]);
			b[a[i]]++;
		}
		int u=m/n,v=m%n;
		for(int i=0;i<n;++i){
			if(b[a[i]]%2==0){
				if(c[a[i]]%2==0) ans[i]=u+(i<v?1:0);
				else ans[i]=0;
			}else{
				int h=u%2;
				if(c[a[i]]%2==0) ans[i]=(u+1)/2+(!h&&i<v?1:0);
				else ans[i]=u/2+(h&&i<v?1:0);
			}
			c[a[i]]++;
		}
		for(int i=0;i<n-1;++i) cout<<ans[i]<<" ";
		cout<<ans[n-1]<<'\n';
	}
	return 0;
}

题解：P14118 [SCCPC 2021] Hotpot

文章操作

AC Code：

相关推荐

评论

题解：P14118 [SCCPC 2021] Hotpot