本题用 SG 定理（详见下文链接），推导出初始奇数中仅数值 的 SG 值为 ，其余大于 的奇数 SG 值均为 ，所以游戏胜负仅取决于数列中 的个数的奇偶性：如果 的个数为奇数则先手小蓝胜，否则后手小桥胜，那么只需统计 的个数即可。
详细解释
设偶数为 ，奇数为 。
设 为总 SG 值数列中 的个数。
- 那么 可变为 ，推导得 。
- 只能变为 ，所以 。
- 当 时，。
- 当 时，，那么 。
- 仅数值为 的项对应的 SG 值 ，其余奇数对应的值为 。那么总 SG 值为 。
AC Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int n;
cin>>n;
int ans=0;
for (int i=0;i<n;i++) {
int w;
cin>>w;
if(w==1) ans++;
}
if(ans%2!=0) cout<<"L"<<endl;
else cout<<"Q"<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--) solve();
exit(0);
}
感谢博客 IcyCheees 提供的资料。
感谢博客 Hypoc_ 提供的资料。
暂无评论