P8887 [DMOI-R1] 柯基棋 题解

Vct14 · 2022-12-06 13:48:09 · 题解

题目传送门 || 更好的阅读体验 || 更新日志

思路

以下用黑棋代表小 A 下的“柯基”，用白棋代表小 B 下的“柯基”。黑棋先手。

通过探索，我们可以发现以下规律：

• 当棋盘边长为奇数时，黑棋先下棋盘中心（一个交叉点），然后以棋盘的中心对称，那么白棋能下的地方，黑棋也能下，那么最后一步一定是黑棋下的，即黑棋获胜；

• 当棋盘边长为偶数时，以棋盘的中心线对称，无论黑棋下哪里，白棋就下它的对称点，那么黑棋能下的地方，白棋也能下，那么最后一步一定是白棋下的，即白棋获胜。这里中心线指将棋盘对折一次形成的折痕（这么说有点奇怪，不过理解意思就行（逃））。

由 x_i 的生成器中的 x[i]=x[i-1]+((xor_shift(seed)%(unsigned long long)(2*2)+1))*2; 可知 x_i 为偶数，即小 C 捣乱时先后手的顺序不变。

由于捣乱时，棋盘的中心和中心线、棋盘边长的奇偶性、先后手顺序都不变，所以捣乱前和捣乱后赢家是不变的。

综上所述，

• 当棋盘的边长为奇数时，小 A 胜；
• 当棋盘的边长为偶数时，小 B 胜。

代码

#include<bits/stdc++.h>
using namespace std;

int main(){
    int T;
    cin>>T;
    while(T--){
        int n,q,seed;
        cin>>n>>q>>seed;
        if(n%2) cout<<"A won";
        else cout<<"B won";
        cout<<"\n";
    }   
    return 0;
}

提示：

• 本题为多组测试数据。
• 虽然本题的 q 和 seed 没有用上，但是不要漏输入。