我写代码找的规律：如果这个n是斐波那契数，那么它是P态，如2,3,5,8....。
找规律的代码：
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
const int maxn = 100 + 5;
int dp[maxn][maxn];
int main() {
memset(dp, inf, sizeof(inf));
memset(dp[0], 0, sizeof(dp[0]));
memset(dp[1], 1, sizeof(dp[1]));
dp[1][0] = 0;
for(int i = 2; i < 100; ++i) {
dp[i][0] = 0; //P态
for(int j = 1; j < i; ++j) {
//取了j个石子,剩余i-j个石子
if(j*2 >= i-j) dp[i-j][j] = 1;
else dp[i-j][j] = dp[i-j][0];
if(dp[i-j][j] == 0) dp[i][0] = 1; //N态
}
printf("%d ", dp[i][0]);
}
return 0;
}
AC代码
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
const int maxn = 200 + 5;
set<LL>ha;
LL f[maxn];
void deal() {
ha.insert(2);
ha.insert(3);
f[0] = 2, f[1] = 3;
for(int i = 2; i < 110; ++i) {
f[i] = f[i-1] + f[i-2];
ha.insert(f[i]);
}
}
int main() {
deal();
LL n;
while(scanf("%lld", &n) == 1) {
if(!ha.count(n)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
如有不当之处欢迎指出！