C、牛牛爱博弈
牛牛爱博弈
https://ac.nowcoder.com/acm/contest/6885/C
题意:给定一堆石头,Frame和Alan轮流取石头,每次可以取个,不能取的人输,问谁必胜。
思路:
打表,得到的表如下(0代表Frame,1代表Alan):
1 1 2 1 3 0 4 1(可以转化为3 必败态给对手) 5 1(可以转化为3 必败态给对手) 6 0 7 1(可以转化为6 必败态给对手) 8 1(可以转化为6 必败态给对手) 9 0
看出规律,3的倍数时为必败态。
AC代码:
#include<cmath> #include<cstdio> #include<vector> #include<queue> #include<cstring> #include<iomanip> #include<stdlib.h> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 #define mod 1000000007 #define N 100005 #define fo(i, a, b) for(i=a;i<=b;i++) #define fd(i, a, b) for(i=a;i>=b;i--) using namespace std; int T; int a[N]; int main() { cin>>T; while(T--){ int n; cin>>n; if(n%3) cout<<"Alan\n"; else cout<<"Frame\n"; } }