题意:两个人玩游戏:初始时分别有n和m张牌,每张牌有一个颜色。你不能出对面出过的颜色,没有牌可以出的失败。问谁会赢
题解:想法很简单,对于每一种颜色i,玩家A有Ai 张牌,玩家B有Bi张牌,如果玩家A先出了其中的一种的一张牌,那么他就得到了Ai+Bi 的收益。反之亦然。所以我们按照这个东西排序之后模拟一遍这个操作就好了
但是这个题目由于数据出的很大,所以很卡常。我们必须选择常数小的东西比如避免使用map
(事实上,unordered_map
也不行)。另外由于很多的数据是按照题目给出的伪随机数生成器生成的,所以如果能够预先处理掉A和B独有的颜色也可以节约很多时间
大体来说,除了排序以外都选用的操作才可以AC这道题
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define int uint64_t
using namespace std;
using pii = pair<int, int>;
const int maxn = 2e5+10;
int k1, k2;
int rng()
{
int k3 = k1, k4 = k2;
k1 = k4;
k3 ^= k3 << 23;
k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
return k2 + k4;
}
void init_read(pii ma[], int &n, bool gen)
{
static int tmp[maxn];
if (gen)
{
int mod;
cin >> k1 >> k2 >> mod;
for (int i = 0; i < n; i++)
{
tmp[i] = rng() % mod;
}
}
else
{
for (int i = 0; i < n; i++)
{
cin >> tmp[i];
}
}
sort(tmp, tmp + n);
int m = 0;
for(int i = 0, j = 0; i<n; i = j) {
for(; (j<n) && (tmp[j] == tmp[i]); ++j);
ma[m++] = make_pair(tmp[i], int(j - i));
}
n = m;
}
auto cmp = [](const pii &p1, const pii &p2) { return p1.first + p1.second > p2.first + p2.second; };
int32_t main()
{
ios::sync_with_stdio(false);
int _;
cin >> _;
while (_--)
{
static pii a[maxn], b[maxn], c[maxn];
int n, m, p;
cin >> n >> m >> p;
init_read(a, n, p == 2);
init_read(b, m, p == 2);
int sqq = 0, scc = 0, k = 0;
for (int i = 0, j = 0; i < n || j < m;)
{
if ((i < n) && (j < m) && (a[i].first == b[j].first))
{
c[k++] = make_pair(a[i++].second, b[j++].second);
}
else if (i == n || (j < m && b[j].first < a[i].first))
{
scc += b[j++].second;
}
else
{
sqq += a[i++].second;
}
}
sort(c, c + k, cmp);
for (int i = 0; i < k; i++)
{
if (i & 1)
{
scc += c[i].second;
}
else
{
sqq += c[i].first;
}
}
if (sqq > scc)
{
cout << "Cuber QQ" << endl;
}
else
{
cout << "Quber CC" << endl;
}
}
}