题解：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：

#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;
}