https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1067
问题有点复杂，直接分析比较困难。 先算几个小数据找找规律？ 动态规划。转移： F[i]=(!F[i-1])||(!F[i-3])||(!F[i-4]) 从1开始前几个小数据的运行结果： 1,0,1,1,1,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,0,1,0,1,…
这个是打表的程序；
#include<iostream> #include<cstdio> #include<algorithm> #include<cstdlib> #define ll long long using namespace std; int f[100]; int main(){ f[1]=f[3]=f[4]=1; for(int i=5;i<=20;i++)if(!f[i-1]||!f[i-3]||!f[i-4])f[i]=1; for(int i=1;i<=20;i++)cout<<i<<' '<<f[i]<<endl; }石子数对7取余后的结果为0或2时先手必败，否则先手必胜。 考虑边界条件，显然F[0]=0,F[2]=0； 对于任何一个mod7结果为0或2的状态，如果先手取了3或4 个石子，那么后手可以取4或3个石子，将其mod7结果保持不变。 对于任何一个mod7结果为0的状态，如果先手取了1个石子， 那么后手可以取4个石子，将其mod7的结果变为2；对于任何一 个mod7结果为2的状态，如果先手取了1个石子，那么后手可以 取1个石子，将其mod7的结果变为0。 这也就意味着，如果先手面临的状态mod7结果为0或2，后 手能够一直使其处于这个状态之中，直到后手获胜。
就是说我们可以一直减7减7； 等到小于7了，为0或2输，另外先先手胜利；
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int x,y,m; int main() { scanf("%d",&m); while(m--){ scanf("%d",&x); if(x%7==0||x%7==2)cout<<'B'<<endl;else cout<<'A'<<endl; } }Bash游戏 V3
问题还是比较复杂，先动态规划看看小数据。 从1开始前几个小数据的运行结果： 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1… 难道如果N是3的倍数则先手必败？
-
考虑模3剩余系下的情况。每人每次取走一粒或者两粒石子， 最后不能取的人输。先手第一步必定先把石子取成3的倍数， 这样才可以控制局势；否则，后手必胜。
所以我们遇到博弈论的 题目先找规律再说
