杭电多校第七场

J: Just Repeat

题意

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

思路

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

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#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;
}
---------Thanks for your attention---------