牛客练习赛67-C、牛牛爱博弈牛客

题意：给定一堆石头，Frame和Alan轮流取石头，每次可以取 1 , 2 , 2 2 , 2 3 , . . . , 2 k 1,2,2^2,2^3,...,2^k 1,2,22,23,...,2k个，不能取的人输，问谁必胜。
思路：
打表，得到的表如下（0代表Frame，1代表Alan）：

n n n a n s ans ans

1 1

2 1

3 0

4 1（可以转化为3 必败态给对手）

5 1（可以转化为3 必败态给对手）

6 0

7 1（可以转化为6 必败态给对手）

8 1（可以转化为6 必败态给对手）

9 0

n n n	a n s ans ans
1	1
2	1
3	0
4	1（可以转化为3 必败态给对手）
5	1（可以转化为3 必败态给对手）
6	0
7	1（可以转化为6 必败态给对手）
8	1（可以转化为6 必败态给对手）
9	0

【牛客练习赛67-C、牛牛爱博弈】看出规律，3的倍数时为必败态。
AC代码：

#include #include #include #include #include #include #include #include #include#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"; } }