传送门:Problem - D - Codeforces
题意:
思路:博弈论
打表找规律( 递推 )
如果 ans[i] 为 true ,则 Alice 能赢 ans[i] 为 false,则 Bob 会赢
数字 n 的一个因子 为 x , 如果 ans[ n - x ] 为 false ( 必输态 ) ,则 ans[n] 是 true ( 必胜态 )
所以打表代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
bool ans[N];
bool test(int x)
{for (int i = 2; i <= x / i; i++){if (x % i == 0){if (!ans[x - i]) return true;if (!ans[x - x / i]) return true;}}return false;
}
signed main()
{for (int i = 1; i <= 110; i++){ans[i] = test(i);}for (int i = 1; i <= 110; i++)if (ans[i]) cout << i << " " << "Alice" << endl;else cout << i << " " << "Bob" << endl;
}
接下来观察结果,你会发现 当 n % 2 == 0 时,基本上就是 Alice,当有例外 2 8 32 等,你会发现这些数字都是 2 的奇数次幂
所以得到结论 当 if ( n % 2 == 1 || n 为 2 的奇数次幂 时 ) ,puts("Bob");
else puts("Alice");
AC代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
set<int> st;
void solve(){int n; cin >> n;if( n % 2 == 1 || st.count(n) )puts("Bob");else puts("Alice");
}
signed main()
{for( int i = 1 ; ( 1ll << i ) <= 1e9 ; i += 2 ){int temp = ( 1ll << i );st.insert( temp );}int tt; cin >> tt;while(tt--)solve();return 0;
}