爱奇艺-笔试刷题2018-07-14

题目描述：

/**
牛牛和羊羊都很喜欢青草。今天他们决定玩青草游戏。
最初有一个装有n份青草的箱子,牛牛和羊羊依次进行,牛牛先开始。在每个回合中,每个玩家必须吃一些箱子中的青草,所吃的青草份数必须是4的x次幂,比如1,4,16,64等等。不能在箱子中吃到有效份数青草的玩家落败。假定牛牛和羊羊都是按照最佳方法进行游戏,请输出胜利者的名字。
输入描述:
输入包括t+1行。
第一行包括一个整数t(1 ≤ t ≤ 100),表示情况数.
接下来t行每行一个n(1 ≤ n ≤ 10^9),表示青草份数
输出描述:
对于每一个n,如果牛牛胜利输出"niu",如果羊羊胜利输出"yang"。
输入例子1:
3
1
2
3
输出例子1:
niu
yang
niu
*/

思路如下：

方案一：DFS暴力枚举情况求解（超时）
方案二：暴力DFS先找写，然后打表找规律为没5个niu yang niu niu yang

打表代码（找规律）：

#include<stdio.h>
#include<iostream>
 
#define MAX_T 101
//#define MAX_N 1000000001
#define MAX_N 100001
 
using namespace std;
 
int queryNum[MAX_T];
bool marked[MAX_N];
//false表示先手胜 true表示后手胜利
bool dp[MAX_N];
 
bool DFS(int n)
{
    if(marked[n])
        return dp[n];
    int mult=1;
    while(mult<n)
    {
        mult<<=2;
    }
    //mult>=n
    if(mult==n)
    {
        marked[n]=true;
        dp[n]=false;
        return dp[n];
    }
    else if(mult>n)
        mult>>=2;
    //mult<n
    for(; mult>=1; mult>>=2)
    {
        if(DFS(n-mult))
        {
            marked[n]=true;
            dp[n]=false;
            return dp[n];
        }
    }
    marked[n]=true;
    dp[n]=true;
    return dp[n];
}
 
int main()
{
//    int T, maxQueryNum=-1;
//    scanf("%d", &T);
//    for(int i=0; i<T; i++)
//    {
//        scanf("%d", queryNum+i);
//        if(queryNum[i]>maxQueryNum)
//            maxQueryNum=queryNum[i];
//    }
//    DFS(maxQueryNum);
//    for(int i=0; i<T; i++){
//        if(!dp[queryNum[i]])
//            printf("niu\n");
//        else
//            printf("yang\n");
//    }
    DFS(55);
    for(int i=1; i<=50; i++)
    {
        printf("i: %d ", i);
        if(!dp[i])
            printf("niu\n");
        else
            printf("yang\n");
    }
    return 0;
}

最终代码：

#include<stdio.h>
#include<iostream>
 
using namespace std;
 
int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        int n;
        scanf("%d", &n);
        if(n%5==2 || n%5==0)
            printf("yang\n");
        else
            printf("niu\n");
    }
    return 0;
}