icontofig | 发布于 2019-08-13 00:35:49 | 阅读量 443 | 博弈论 贪心 思维题
发布于 2019-08-13 00:35:49 | 博弈论 贪心 思维题

题目大意

先手有n张牌,后手有m张牌,如果某人打出了某种颜色的牌,那么另一个人就不能打这种颜色的牌,最后不能出牌的人输。求问是先手胜还是后手胜。

题解

两人都是按最优策略取的博弈,不过和SG函数并没有什么关系。

两个人肯定每回合都是贪心的取对自己最有利的方案。

首先我们将两人都有的颜色的牌抽出来,剩下的就是两人各自独立的牌集,不会受对方出牌的影响。

然后我们考虑被抽出来的牌,怎样取能使得局面变得对自己有利。

如果对于某种颜色,两人共有的这种颜色的牌比较大,那么当前的出牌者选择出这种颜色的牌的优先级肯定就更高。

然后当前的人出一种颜色的牌,就可以看成是把自己原有的这种颜色的牌全部收回,把对方原有的这种颜色的牌全部丢掉。

所以我们需要离散化颜色,然后对于公共颜色的牌全部抽出,然后按照两人手中的这种颜色的牌的总数从大到小排序,然后让先手先选,后手后选直到全部选完。

选完后我们比较一下两人手里的牌的总数。

如果先手手中的牌比后手多,则先手必胜,否则先手必败。

(对于我取消流同步的cin比自己写的快读要快这件事,我真的很疑惑……)

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int maxn = 1e5+5;
int a[maxn],b[maxn];
unsigned long long mod;
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 t;
int n,m,p;
int cnt = 0;
int c[maxn<<1];
int q[maxn<<1];
int com[maxn<<1];
struct point{
    int val,id;
}e[maxn];
bool cmp(point a,point b){
    return a.val > b.val;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--){
        cin >> n >> m >> p;
        cnt = 0;
        if(p == 1){
            for(int i = 1;i <= n;++i){
                cin >> a[i];
                c[i] = a[i];
            }
            for(int i = 1;i <= m;++i){
                cin >> b[i];
                c[i+n] = b[i];
            }
        }
        else{
            cin >> k1 >> k2 >> mod;
            for (int i = 1; i <= n; ++i)
                a[i] = rng() % mod,c[i] = a[i];
            cin >> k1 >> k2 >> mod;
            for (int i = 1; i <= m; ++i)
                b[i] = rng() % mod,c[i+n] = b[i];
        }
        sort(c+1,c+n+m+1);
        int tot = unique(c+1,c+n+m+1) - (c + 1);
        for(int i = 1;i <= tot;++i){
            com[i] = q[i] = 0;
        }
        for(int i = 1;i <= n;++i){
            a[i] = lower_bound(c+1,c+tot+1,a[i]) - c;
            q[a[i]]++;
        }
        for(int i = 1;i <= m;++i){
            b[i] = lower_bound(c+1,c+tot+1,b[i]) - c;
            if(q[b[i]]){
                com[b[i]]++;
            }
        }
        for(int i = 1;i <= tot;++i){
            if(com[i]){
                n -= q[i];
                m -= com[i];
                e[++cnt].val = q[i] + com[i];
                e[cnt].id = i;
            }
        }
        sort(e+1,e+cnt+1,cmp);
        for(int i = 1;i <= cnt;++i){
            if(i % 2 == 1){
                n += q[e[i].id];
            }
            else m += com[e[i].id];
        }
        if(n > m)cout << "Cuber QQ\n";
        else cout << "Quber CC\n";
    }
    return 0;
}



内容更新于: 2019-08-13 00:35:50
链接地址: http://blog.leanote.com/post/icontofig/2019-Multi-University-Training-Contest

上一篇: 2019 Multi-University Training Contest 8 1008 Andy and Maze 状压DP + color coding

下一篇: 2019 Multi-University Training Contest 7 1006 Final Exam 思维题

443 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航