題意:兩個(gè)人玩游戲:初始時(shí)分別有n和m張牌变过,每張牌有一個(gè)顏色媚狰。你不能出對(duì)面出過的顏色阔拳,沒有牌可以出的失敗。問誰會(huì)贏
題解:想法很簡單辨宠,對(duì)于每一種顏色i嗤形,玩家A有Ai 張牌赋兵,玩家B有Bi張牌叶组,如果玩家A先出了其中的一種的一張牌,那么他就得到了Ai+Bi 的收益帕膜。反之亦然。所以我們按照這個(gè)東西排序之后模擬一遍這個(gè)操作就好了
但是這個(gè)題目由于數(shù)據(jù)出的很大,所以很卡常吞鸭。我們必須選擇常數(shù)小的東西比如避免使用map
(事實(shí)上刻剥,unordered_map
也不行)。另外由于很多的數(shù)據(jù)是按照題目給出的偽隨機(jī)數(shù)生成器生成的,所以如果能夠預(yù)先處理掉A和B獨(dú)有的顏色也可以節(jié)約很多時(shí)間
大體來說陶珠,除了排序以外都選用的操作才可以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;
}
}
}