2020 CCPC-Wannafly Winter Camp Day3 Div.12——E 棋技哥【二维后缀数组、构造】

题目传送门

题目描述

火山哥和鸡老八在下棋。
这张棋盘是 $n\times m$ 的。每一个格子要么是黑色的，要么是白色的。
两个人轮流进行操作。火山哥先手。每一次可以选择一个黑色的格子，以这个格子为右下角，棋盘左上角为左上角，将这个矩阵的所有格子的颜色由黑变成白，由白变成黑。如果找不到一个黑色的格子，那么那个人就输了。
现在两个人都想让火山哥赢，请问谁能赢呢。

输入描述:

第一行一个整数 $T$,表示有 $T$ 组数据。
每组数据第一行两个整数 $n,m$ 表示棋盘的大小。
接下来 $n$ 行每行 $m$ 个字符 $0$（白色）或者 $1$（黑色），描述了这个棋盘的初始状态。
$1\le n,m\le 500$ ,$1\le T\le 20$

输出描述:

对于每组的每个询问，输出一行，如果火山哥赢输出$“call”$，鸡老八赢输出$“aoligei”$(不含引号)。

输入

3
2 2
11
11
3 2
01
10
11
2 2
00
11

输出

call
aoligei
aoligei

题解

• 考虑当前状态不被任何其他黑子控制的黑子，一定会被按下一次。
• 对于任意一个黑子，按下之后，可能会被右面、下面的黑子改变状态。
• 很容易看出，最优解就是从右、下依次按下黑子，每次按下的是不被任何其他黑子控制的黑子。
• 利用后缀数组维护操作次数即可

AC-Code

#include <bits/stdc++.h>
using namespace std;int mp[505][505];
int d[505][505];
int main(){
    int T;for(cin >> T; T; T--){
    memset(d, 0, sizeof d);int n, m;cin >> n >> m;for(int i = 0; i < n; ++i){
    string s;cin >> s;for(int j = 0; j < m; ++j){
    if(s[j] == '0')    mp[i+1][j+1] = 0;else mp[i+1][j+1] = 1;}}for(int i = n; i > 0; --i){
    for(int j = m; j > 0; --j){
    d[i][j] = d[i+1][j] + d[i][j+1] - d[i+1][j+1];if((d[i][j] + mp[i][j]) % 2)++d[i][j];}}if(d[1][1] & 1)    cout << "call" << endl;else    cout << "aoligei" << endl;}return 0;
}