巴什博弈

有一堆n个的物品，两个人都足够聪明，轮流从这堆物品中取走物品，规定每次只能取[1,m]个。

• 最后取光者胜 若n%（m+1）==0 则先手必败 否则先手必胜
  当n≤m时，这时先手的人可以一次取走所有的物品；（先手必胜）
  当n=m+1时，这时先手无论取走多少个，后手的人都能取走剩下所有的物品；（先手必输）
  当n=k∗(m+1)时，对于每m+1个石子，先手取i个，后手一定能将剩下的（m+1−i）个都取走；（先手必输）
  当n=k∗(m+1)+x（0<x<m+1）时，先手可以先取x个，之后的局势就回到了上一种情况，无论后手取i个，先手都能取走剩下的（m+1-i）个；（先手必胜）
• 最后取光者输 若（n-1）%（m+1)==0 则先手必败 否则先手必胜

威佐夫博弈

有两堆各若干的物品，两人轮流从其中一堆中取至少一件物品，最多不限，或从两堆中同时取相同件物品，规定最后取光者胜利

若两堆物品的初始值为（x，y）（x<y）
令z=y-x，w=(int)[(sqrt(5)+1)/2*z]（黄金分割率）
若w=x 则先手必败 否则先手必胜

1

Seek the Joker I

题目描述

长达数日的春日祭终于告一段落，作为巫女的朝野芳乃在打扫完神社本决定好好享受一下久违的宁静。然而守护了神刀数百年的丛雨难耐寂寞，希望芳乃能陪她一起玩扑克消解愁闷。
芳乃并不擅长市井的游戏，所以总是输多赢少。而昨日被芳乃的神乐舞深深吸引，以致一早就前来建实神社希望能再睹芳华的你碰巧听见了此事。尽管不知道为什么美丽的巫女要自言自语地为玩扑克而苦恼，但你毅然决然地毛遂自荐，希望能为芳乃一解眉间愁。
芳乃告诉了你丛雨准备了n张扑克牌作为牌堆，每人每次至多从牌堆顶部抽k张牌，至少抽1张牌。牌堆底部的最后一张牌作为乌龟，抽中的将输掉这一轮比赛。芳乃想知道在你的帮助下，她和丛雨都采取积极策略时，她自己是否一定能获胜。作为被丛雨邀请的一方，每轮游戏都是芳乃先抽。
因为看不见丛雨而误认芳乃罹患精神分裂的你在不由感叹红颜薄命的同时，决定尽全力帮助芳乃完成她的委托。
声明：本题中的所有角色在剧情发生时均已超过18岁。

输入描述:

第一行包含一个整数T，表示共有T组测试数据。
每组测试数据共一行，包含两个正整数n和k，分别表示牌堆中有n张牌和每次抽取最多抽取k张。
数据保证T,n,k≤1000000。

输出描述:

对于每组测试数据给出一行结果。
如果芳乃必胜，则输出“yo xi no forever!”，
否则输出 ”ma la se mi no.1!“。

示例输入

4
1 1
23 2
6 4
114 514

示例输出

ma la se mi no.1!
yo xi no forever!
ma la se mi no.1!
yo xi no forever!

分析

巴什博弈

代码

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    long long t,n,k;cin>>t;
    while(t--)
    {
        cin>>n>>k;
        if((n-1)%(k+1)==0) cout<<"ma la se mi no.1!"<<endl;
        else cout<<"yo xi no forever!"<<endl;
    }
}

2

Seek the Joker II

题目描述

长达数日的春日祭终于告一段落，作为巫女的朝野芳乃在打扫完神社本决定好好享受一下久违的宁静。然而守护了神刀数百年的丛雨难耐寂寞，希望芳乃能陪她一起玩扑克消解愁闷。
芳乃并不擅长市井的游戏，所以总是输多赢少。而昨日被芳乃的神乐舞深深吸引，以致一早就前来建实神社希望能再睹芳华的你碰巧听见了此事。尽管不知道为什么美丽的巫女要自言自语地为玩扑克而苦恼，但你毅然决然地毛遂自荐，希望能为芳乃一解眉间愁。
芳乃告诉了你丛雨准备了n张扑克牌作为牌堆，自牌顶向下数第x张牌作为乌龟，即“乌龟”的上方有x-1张牌，“乌龟”的下方有n-x张牌，抽中“乌龟”的将输掉这一轮比赛。每人每次可以同时在牌堆顶和牌堆底或者仅在牌堆顶或牌堆底其抽取任意张牌，至少抽1张牌。但若选择同时在牌堆顶和牌堆底抽牌，则抽牌数量需要相同。芳乃想知道在你的帮助下，她和丛雨都采取积极策略时，她自己是否一定能获胜。作为被丛雨邀请的一方，每轮游戏都是芳乃先抽。
因为看不见丛雨而误认芳乃罹患精神分裂的你在不由感叹红颜薄命的同时，决定尽全力帮助芳乃完成她的委托。
声明：本题中的所有角色在剧情发生时均已超过18岁。

输入描述:

第一行包含一个整数T，表示共有T组测试数据。
每组测试数据共一行，包含两个正整数n和x，分别表示牌堆中有n张牌和”乌龟“的位置。
数据保证，T≤1000000 和n,x≤3000000 ,。

输出描述:

对于每组测试数据给出一行结果。
如果芳乃必胜，则输出“yo xi no forever!”，
否则输出”ma la se mi no.1!“。

示例输入

8
1 1
10 3
17 6
12 5
4 3
9 6
12 8
17 11

示例输出

ma la se mi no.1!
yo xi no forever!
yo xi no forever!
ma la se mi no.1!
ma la se mi no.1!
ma la se mi no.1!
ma la se mi no.1!
ma la se mi no.1!

分析

威佐夫博弈

代码

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    double c=(1.0+sqrt(5.0))/2.0;
    int t;cin>>t;
    while(t--)
    {
        int n,x;cin>>n>>x;
        int a=x-1,b=n-x;
        if(a>b) swap(a,b);
        int temp=(b-a)*c;
        if(temp!=a) cout<<"yo xi no forever!\n";
        else cout<<"ma la se mi no.1!\n";
    }
}

未完待续~