题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=6655

题目

QQ和CC两个人玩牌，QQ先出牌，数字标记牌上的颜色，每个人不能出另一个人出过的牌，但是可以出自己出过的牌，若轮到某人出牌，但是某人手里没牌了或者不能出牌了，那么那个人就输了。问最后的赢家是谁。

样例t， QQ手里n≤1e5张牌，CC手里m≤1e5张牌，p=1是给出每个人手里的牌对应的数字<2^64(要用unsigned long long)， p=2用程序生成每个人手里的牌对应的数字。n+m不超过1e7

 

解题思路：

suma：QQ能出的牌数，sumb：CC能出的牌数

对每个人统计每张牌的牌数，对于自己有但对方没有的牌，肯定是可以全部出掉的，加入对应的suma/sumb中。

找出双方都有的牌，若对于牌i，QQ有张，CC有张，组成pair， 对pair按照+从大到小排序，统计QQ和CC分别能出的牌数。

给出的标准题解如下：

我想是让+越大， 那么有和都相对比较大，两者不仅大而且很均衡，因为对于i不知道是轮到A拿还是轮到B拿，要让无论谁拿拿到的收益都比较大才比较公平吧，这才是最优策略。当然不排除一些极端情况。

 

ac代码：

unordered_map也这么慢吗，还是我哪里写的很慢。。。1900ms左右，在超时的边缘徘徊?

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef unsigned long long ll;
typedef unordered_map<ll, ll> MAP;
typedef pair<ll, ll> PAIR;
ll k1, k2, mod, x, suma, sumb, cnt1, cnt2, cnt3;
ll A[maxn], B[maxn];
PAIR same[maxn];
int t, n, m, p;
ll rng() {
    unsigned long long k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= k3 << 23;
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}
void getArray(int p, MAP &a, MAP &b) // a,b 记录出现次数
{
    MAP vis1, vis2;
    if(p == 1)
    {
        for(int i = 0; i < n; i++)
        {
            scanf("%llu", &x);
            a[x]++;
            if(vis1[x] == 0) vis1[x] = 1, A[cnt1++] = x;
        }
        for(int i = 0; i < m; i++)
        {
            scanf("%llu", &x);
            b[x]++;
            if(vis2[x] == 0)vis2[x] = 1, B[cnt2++] = x;
        }
    }
    else
    {
        scanf("%llu %llu %llu", &k1, &k2, &mod);
        for(int i = 0; i < n; i++)
        {
            x = rng() % mod;
            a[x]++;
            if(vis1[x] == 0) vis1[x] = 1, A[cnt1++] = x;
        }
        scanf("%llu %llu %llu", &k1, &k2, &mod);
        for(int i = 0; i < m; i++)
        {
            x = rng() % mod;
            b[x]++;
            if(vis2[x] == 0) vis2[x] = 1, B[cnt2++] = x;
        }
    }
}
bool cmp(PAIR a, PAIR b)
{
    return a.first + a.second > b.first + b.second;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &t);
    while(t--)
    {
        MAP a, b;
        cnt1 = cnt2 = cnt3 = 0;
        scanf("%d %d %d", &n, &m, &p);
        suma = n, sumb = m;
        getArray(p, a, b);
        for(int i = 0; i < cnt1; i++)
            if(b[A[i]])
            {
                same[cnt3++] = {a[A[i]], b[A[i]]};
                suma -= a[A[i]], sumb -= b[A[i]];
            }
        sort(same, same + cnt3, cmp);
        for(int i = 0; i < cnt3; i++)
        {
            if(i % 2 == 0) suma += same[i].first;
            else sumb += same[i].second;
        }
        if(suma > sumb) printf("Cuber QQ\n");
        else printf("Quber CC\n");
    }
    return 0;
}

附上一个800ms左右的代码，它没有直接记录每个数出现的次数，一个for循环专门统计了出现的次数，而且只用了pair。ORZ

博客地址https://blog.csdn.net/qq_41117236/article/details/99442068

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef pair<int, int> P;
const int N=2e5+10;
P A[N],B[N],C[N];
ULL a[N];
ULL k1,k2;
ULL rng(){
    ULL k3=k1,k4=k2;k1=k4;k3^=k3<<23;k2=k3^k4^(k3>>17)^(k4>>26);
    return k2+k4;
}
void init(P T[],int& n,int p)
{
    if(p==1){
        for(int i=0;i<n;i++) scanf("%llu",&a[i]);
    }
    else{
        int mod; scanf("%llu%llu%d",&k1,&k2,&mod);
        for(int i=0;i<n;i++) a[i]=rng()%mod;
    }
    sort(a,a+n);
    int l=0;
    for(int i=0,j=0;i<n;i=j){
        while(j<n&&a[j]==a[i]) j++;
        T[l++]=P(a[i],j-i);
    }
    n=l;
}
bool cmp(const P& a, const P& b)
{
    return a.first+a.second>b.first+b.second;
}
int main()
{
    int T; scanf("%d",&T);
    while(T--){
        int n,m,p; scanf("%d%d%d",&n,&m,&p);
        init(A,n,p); init(B,m,p);
        int SA=0,SB=0,k=0;
        int p1=0,p2=0;
        while(p1<n||p2<m){
            if(p1<n&&p2<m&&A[p1].first==B[p2].first) C[k++]=P(A[p1++].second,B[p2++].second); //双方手里的相同颜色的牌的数目
            else if(p1==n||(p2<m&&A[p1].first>B[p2].first)) SB+=B[p2++].second; //如果B[p2].first比较小，那么说明不可能有相同颜色了
            else if(p2==m||(p1<n&&A[p1].first<B[p2].first)) SA+=A[p1++].second; //同上，所以直接加上贡献，这是互不影响的
        }
        sort(C,C+k,cmp); //按照贡献和排序
        for(int i=0;i<k;i++){
            if(i%2==0) SA+=C[i].first;
            else SB+=C[i].second;
        }
        if(SA>SB) puts("Cuber QQ"); //Cuber QQ 先手
        else puts("Quber CC");
    }
	return 0;
}