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