CF1451F Nullify The Matrix

我们按照与对角线平行的线上的数来考虑。如果只考虑在一条这样的对角线上进行操作,那么就变成了一个普通的 Nim 游戏。而如果有很多对角线,不难发现在进行一次操作的时候,这个人可以把后面的所有对角线的状态改变。

于是我们考虑找出第一个异或和不为 $0$ 的对角线,这个对角线单看是先手必胜的。考虑先手对这个对角线进行一次操作把它的异或值变为 $0$ 。要么此时已经没有数了,先手胜利。要么后手会有一些选项:选择这条对角线或之前的对角线,这样的话必然会导致一条对角线的异或和变成非 $0$ ,先手可以继续操作。否则他会去选择这条对角线后面的对角线。但是后面的对角线可以由先手这一轮操作一下,使得后面的所有对角线的异或和都为 $0$ ,于是后手就没办法了。

于是就可以得出结论:后手必胜当且仅当所有对角线的异或和为 $0$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 136
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
int A[MAXN][MAXN];

void solve() {
cin >> n >> m;
rep( i , 1 , n ) rep( j , 1 , m ) scanf("%d",A[i] + j);
rep( t , 2 , n + m ) {
int s = 0;
rep( i , max( 1 , t - m ) , min( n , t - 1 ) ) {
int j = t - i;
s ^= A[i][j];
}
if( s ) { puts("Ashish"); return; }
}
puts("Jeel");
}

signed main() {
int T;cin >> T;while( T-- ) solve();
// solve();
}
文章作者: yijan
文章链接: https://yijan.co/cf1451f-nullify-the-matrix/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog