题目链接

一直觉得巴什博奕是最简单的博弈遇到肯定没问题，结果被虐惨了，看完标程错了10多遍都没反应过来，当然标程题解和代码的意思也写反了，但是还是想对自己说一句mdzz，傻啊！！！这道题很不错，我觉得很有必要拿来写一篇博客。

题意：n个石子，两个人轮流取，q次询问，每次询问给定k和l，取的石子数目在k到l之间，假设两个人的取法都为最佳即向着自己赢的目标取，问一共能取多少次。

题解：巴什博奕，接下来的叙述中用a和b代替k和l。根据巴什博奕，首先ans=n%(a+b)*2是肯定的，问题就在于余数p。之前我一直以为余数p大于0就ans++，不是这样的，p>=m才ans++，注意不是p>m。四个分割点把余数分成了三种情况，[0,a)，[a,b)，[b,a+b)。第一种不用说，先手取什么后手就取a+b-先手取的，最后剩下一点点谁也取不了后手赢，答案不变。第二种就要ans++了，因为先手可以直接取走那些然后先后手转换，这个用巴什博奕的思想就很容易解释。第三种要注意，先手直接拿走b个，那么现在剩的余数q一定是跑到第一个区间里去了，这就变成了第一种情况，先后手已经转换，ans++。

结论：1. n%(a+b) < a时 ans = 2 * (n/(a+b));        

　　　  2. n%(a+b) >= a时 ans = 2 * (n/(a+b)) + 1; 

个人习惯这样写感觉比较稳，代码可以简化，cin不会超时，数据不会超int，直接套公式即可。

#include <cstdio>#include <cstring>using namespace std;int data[100050],cnt;int main(){    int n,m,q;    while(scanf("%d%d",&n,&q)!=EOF)    {        memset(data,0,sizeof(data));        cnt=0;        int k,l;        while(q--)        {            m=n;            scanf("%d%d",&k,&l);            int a=k+l;            int ans=m/a*2;            m%=a;            if(m>=k) ans++；            data[cnt++]=ans;        }        for(int i=0;i<cnt-1;i++)        printf("%d ",data[i]);        printf("%d\n",data[cnt-1]);    }    return 0;}

http://codeforces.com/gym/100694/problem/M The Fifth Season (巴什博奕)