杭电多校第七场


J: Just Repeat

题意

小C和小Q打牌,两个人轮流出牌,小C先出,小C手中有n张牌,小Q有m张牌,两个人知道对方手中有什么牌,如果对手已经出过了某个数字的牌,那么自己就不能再出这种数字的牌,而对方可以一直出,问最后谁先不能出牌。

思路

首先对于双方都有的牌,我们肯定是要封对面尽量多的牌同时自己能出的牌也尽量多,我们我们就把这两个条件加一起把牌排一个序贪心拿即可,

AC代码

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 1e5 + 7;
const int inf = 0x3f3f3f3f;
typedef pair<int, int> pis;

int a[maxn], b[maxn];
int n, m, p, cnt, mod;
unordered_map<int, int> mp;
int num[2][maxn<<1];
vector<int> vec[maxn<<1];

int read(){ 
    int ans=0; char last=' ',ch=getchar();
    while(ch<'0' || ch>'9') {
        last=ch;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') {
        ans=ans*10+ch-'0'; 
        ch=getchar();
    }
    if(last=='-') ans=-ans; 
    return ans;
}

unsigned long long k1, k2;
unsigned long long rng() {
    unsigned long long k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= k3 << 23;
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

int gai(int x) {
    if(!mp[x]) mp[x] = ++cnt;   
    return mp[x];
}

int main() { 
    int t;
    scanf("%d", &t);
    while(t --) {
        mp.clear();
        for (int i = 1; i <= cnt; i ++) num[0][i] = num[1][i] = 0;
        cnt = 0;
        scanf("%d %d %d", &n, &m, &p);
        int sumn = n, summ = m;
        if(p == 1) {
            for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
            for (int i = 1; i <= m; i ++) scanf("%d", &b[i]);
        }else {
            scanf("%lld %lld %d", &k1, &k2, &mod);
            for (int i = 1; i <= n; i ++) a[i] = rng() % mod;
            scanf("%lld %lld %d", &k1, &k2, &mod);
            for (int i = 1; i <= m; i ++) b[i] = rng() % mod;
        }
        for (int i = 1; i <= n; i ++) 
            num[0][gai(a[i])] ++;
        for (int i = 1; i <= m; i ++)
            num[1][gai(b[i])] ++;
        int Max = 0;
        for (int i = 1; i <= cnt; i ++) {
            if(num[0][i] && num[1][i]) {
                sumn -= num[0][i];
                summ -= num[1][i];
                int sumc = num[0][i] + num[1][i]; 
                vec[sumc].push_back(num[0][i]);
                Max = max(Max, sumc);
            }
        }
        int cur = 0;
        for (int i = Max; i >= 1; i --) {
            for (int v: vec[i]) {
                if(!cur) sumn += v;
                else summ += i - v;
                cur ^= 1;
            }
            vec[i].clear();
        }
        if(sumn > summ) printf("Cuber QQ\n");
        else printf("Quber CC\n");
    } 
    return 0;
}

文章作者: Mug-9
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Mug-9 !
评论
  目录