CF388C&&2018EC Final D题——博弈&&水题

一下两个题目都是按堆取石子，轮流取，每个人都贪心的取即可，感觉都不像博弈。

CF388C

有n排石子，每排有若干堆。Ciel可以选择一排，拿走这一排的第一堆石子。Jiro可以选择一排，拿走这一排的最后一堆石子。两个人都想要让自己的石子数量最多。问两个人最后的石子数量。Ciel先手。

分析：

先考虑Ciel，他肯定可以保证自己至少得到每排石子的左半边。只要按照下面的原则做就可以：

第一个石子先随便选，如果Jiro和自己拿同一排，那就随便再选一个。
如果Jiro没和自己拿同一排，那就去和Ciel拿同一排。

考虑Jiro，同样可以保证自己至少得到每排石子的右半边。只要每次都和Ciel选同一排即可。

综上，就可以确定Ciel和Jiro分别拿了左半边和右半边。

对于奇数排的中间那一堆，从大到小从Ciel开始轮流选就行了。

#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 100+10;
int a[maxn], cnt;
 
bool cmp(int x, int y)
{
    return x > y;
}
 
int main()
{
    int n;
    int ans1 = 0, ans2 = 0;
    scanf("%d", &n);
    for(int i = 0;i < n;i++)
    {
        int k, kk;
        scanf("%d", &k);
        kk = k/2;
        for(int i = 1;i <= kk;i++)
        {
            int tmp;
            scanf("%d", &tmp);
            ans1 += tmp;
        }
        if(k&1)
        {
            int tmp;
            scanf("%d", &tmp);
            a[cnt++] = tmp;
        }
        for(int i = 1;i <= kk;i++)
        {
            int tmp;
            scanf("%d", &tmp);
            ans2 += tmp;
        }
    }
    sort(a, a+cnt, cmp);
    for(int i = 0;i < cnt;i++)
    {
        if((i&1) == 0)  ans1 += a[i]; //&优先级比==还低。。。
        else  ans2 += a[i];
    }
    printf("%d %d\n", ans1, ans2);
}

View Code

2018EC Final D题

题意：有两名玩家，分别拥有n堆石子和m堆石子，他们可以从自己拥有的石子堆中选择一堆并移除任意正整数个，两人轮流，问先手是否会赢？

分析：

当然，这是一道签签到题。

显然，肯定是一堆一堆的取，而不会只取一堆中的一些。

所以，如果 n 小于等于 m，先手赢；否则，先手输。

 

 

参考链接：https://zhuanlan.zhihu.com/p/65207636