欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

51 Nod 1430 奇偶游戏(博弈)

程序员文章站 2022-05-11 14:12:13
...

1430 奇偶游戏
题目来源: CodeForces
基准时间限制:1 秒 空间限制:131072 KB 分值: 160 难度:6级算法题 收藏 关注
有n个城市,第i个城市有ai个人。Daenerys和Stannis是两个恶魔。他们在玩一个游戏,他们轮流去破坏城市。每一轮破坏一个城市并杀光里面所有的人。直到剩下k个城市为止。
如果最后剩下的总人数是偶数那么Daenerys获得胜利,否则Stannis获得胜利。
现在给定一个局面,要求你来判断一下谁会赢,Stannis先出手。
Input
单组测试数据。
第一行包含两个整数n,k (1 ≤ k ≤ n ≤ 2*10^5)表示刚开始的城市数目和最后剩下的城市数目。
第二行有n个整数a1,a2,a3,…,an。 (1 ≤ ai ≤ 10^6),表示每个城市里面的人数。
Output
对于每一组数据输出胜者。
Input示例
3 1
1 2 1
3 1
2 2 1
Output示例
Stannis
Daenerys

/*
博弈.
具体讨论第k+1个是谁取的.
n==k的时候特判一下.
否则算出每个人的可操作次数.
然后讨论就好.
*/
#include<iostream>
#include<cstdio>
#define MAXN 10001
using namespace std;
int n,k,num1,num0,k0,k1;
int main()
{
    int x;
    while(~scanf("%d%d",&n,&k))
    {
        num1=num0=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            if(x&1) num1++;
            else num0++;
        }
        if(n==k)
        {
            if(num1&1) printf("Stannis\n");
            else printf("Daenerys\n");
            continue;
        }
        k1=(n-k+1)/2;
        k0=n-k-k1;
        if(num1<=k0) printf("Daenerys\n");
        else if(num0<=k0&&(num1-num0)&1&&k0!=k1)
        {
            printf("Daenerys\n");
        }
        else if(num0<=k0&&(num1-num0)%2==0&&k1==k0)
        {
            printf("Daenerys\n");
        }
        else if(num0>k0&&num1>k0&&k1==k0)
        {
            printf("Daenerys\n");
        }
        else {
            printf("Stannis\n");
        }
    }
    return 0;
}