因为保证了这个路径必须是向下和向右,就可以考虑每一条 \(i + j = x\) 的斜线上的点,因为一条路径经过的点对应的 \(i + j\) 一定是每次 \(+ 1\) 的。
考虑到因为对于同一条直线,每个点是独立的,因为一条路径至多经过这条直线上的一个点。
于是可以考虑用 \(\text{Nim}\) 的思想把这条直线上的点权 \(\oplus\) 上,记其为 \(val_x\)。
根据 \(\text{Nim}\) 游戏可以知道如果 \(val_x = 0\) 则说明对应其必败。
于是若每条直线的 \(val_x = 0\) 则说明后手必胜,否则先手必胜。
证明可以考虑 \(\text{Nim}\) 游戏的分析:
第一个限制,若存在直线 \(val_x \not = 0\),则可以通过一次操作使得所有直线 \(val_x = 0\)。
考虑找到最小的 \(x\) 满足 \(i + j = x\) 的点权 \(val_x \not = 0\),可以知道肯定存在 \(a_{i, j}\ge a_{i, j}\oplus val_x\),那么就可以把 \(a_{i, j}\) 替换为 \(a_{i, j}\oplus val_x\)。
对于 \(y > x\) 的直线,随便选取一个点 \(a_{i, j}\) 替换为 \(a_{i, j}\oplus val_y\) 即可,因为后面的点随便加减都可以。
第二个限制,若不全局为 \(0\),对于任意直线 \(val_x = 0\),则可以通过一次操作使得存在直线 \(val_x\not = 0\)。
随便选一个非 \(0\) 的点减小即可。
时间复杂度 \(O(nm)\)。
#include<bits/stdc++.h>
const int maxn = 2e2 + 10;
int val[maxn];
inline void solve() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n + m; i++) val[i] = 0;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
int x; scanf("%d", &x);
val[i + j] ^= x;
}
bool f = 1;
for (int i = 1; i <= n + m; i++) f &= ! val[i];
puts(f ? "Jeel" : "Ashish");
}
int main() {
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}
标签:Nullify,val,直线,int,text,Nim,Codeforces,1451F,oplus
From: https://www.cnblogs.com/rizynvu/p/18035107