首页 > 试题广场 >

青草游戏

[编程题]青草游戏
  • 热度指数：50 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
牛牛和羊羊都很喜欢青草。今天他们决定玩青草游戏。
最初有一个装有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

输出

niu
yang
niu
算法知识视频讲解
添加回答
pein531头像 pein531
正常分析先枚举从1到4的情况
  1. 牛牛直接吃了，niu
  2. 牛牛吃一份草，羊羊吃了剩下的一份，yang
  3. 牛牛吃一份草，羊羊也只能吃一份，剩下一份牛牛吃，niu
  4. 牛牛吃4份草，niu
1~4的时候只有2是羊羊赢，其他的都是牛牛赢，所以对于牛牛而言，如果此时有n份草摆在它面前，它可以从1开始尝试n以内的4的次幂：4,16,64,……。然后把剩下的草扔给羊羊，然后羊羊重复这个步骤。
于是写了个递归版本如下： 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for(int i = 0; i < t; i++){
            int n = Integer.parseInt(br.readLine());
            System.out.println(winner(n));
        }
    }
    
    private static String winner(int n) {
        if(n < 5) return n == 2? "yang": "niu";
        int base = 1;
        // 牛牛不断尝试4的次方
        while(base <= n){
            // 牛牛吃base份然后往下扔给羊羊
            if(winner(n - base).equals("yang")) return "niu";
            // 防止乘以4后溢出
            if(base > n / 4) break;
            base *= 4;
        }
        // 尝试了各种方案牛牛都没赢，则羊羊赢
        return "yang";
    }
}
结果第二个case上来就给我个上亿的数据量，直接导致栈溢出。没办法，只能用骚操作——打表法，先尝试一下1~50的情况，打印出了如下结果
1:niu
2:yang
3:niu
4:niu
5:yang
6:niu
7:yang
8:niu
9:niu
10:yang
11:niu
12:yang
13:niu
14:niu
15:yang
16:niu
17:yang
18:niu
19:niu
20:yang
21:niu
22:yang
23:niu
24:niu
25:yang
26:niu
27:yang
28:niu
29:niu
30:yang
31:niu
32:yang
33:niu
34:niu
35:yang
36:niu
37:yang
38:niu
39:niu
40:yang
41:niu
42:yang
43:niu
44:niu
45:yang
46:niu
47:yang
48:niu
49:niu
50:yang
得到规律：每5个就是一组niu,yang,niu,niu,yang。所以改出一个复杂度为O(1)的算法 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for(int i = 0; i < t; i++){
            int n = Integer.parseInt(br.readLine());
            System.out.println(winner(n));
        }
    }
    
    private static String winner(int n) {
        return (n % 5 == 0 || n % 5 == 2)? "yang": "niu";
    }
}
像这种输入一个整数，输出也是一个整数的题目。左神表示大概3~4成的题目可以用这种方式找规律，刚开始不要纠结它的数学原理，只要这样暴力出来能AC，再去通过数学的方式解释这个策略。
编辑于 2021-12-10 11:50:35 回复(0)
提交观点

问题信息

模拟 爱奇艺 2018 数学 大数据开发工程师
来自：爱奇艺2018秋季校招...
上传者：小小
难度：
1条回答 2040浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号