Codeforces Round 779 (Div. 2) problem E.Gojou and Matrix Game

题目链接

题意

有一个$n\times n$的二维网格，每格上有一个正整数且互不相同。A与B进行一种轮流放置棋子的游戏，每次放置可以获得放置位置上数值的得分，两人轮流操作$10^{100}$轮，得分高的获胜。

放置规则： 除了第一次外，每次放置的位置要距离上次位置曼哈顿距离大于k。没有其他限制，也就是说可以放在之前被放过的格子上。

问A,B都按最优策略执行，哪些格子上先手必胜，哪些格子上先手必败。

数据范围

$3\leq n \leq 2000$

$1\leq k \leq n - 2$

$1\leq a_{ij} \leq n^2$

题解

通过观察，有以下结论：

1. 一旦一位玩家走到$n^2$格子上，无论另一位选手怎么走，该玩家下一步一定能走回$n^2$这一格，所以显然$n^2$为必胜态。所以所有距离$n^2$大于k的格子都是先手必败的。
2. 剩下只有跟$n^2$距离不超过k且不等于$n^2$的格子状态未知，假设这些格子的最大值为mx，由于这些格子都不能直接走到$n^2$（因为距离不超过$k$），所以情况同结论1相同。mx是一个必胜态，其他所有距离mx大于k的格子都是必败态。

重复2过程直到最后只剩下一个格子时迭代结束，就可以找到所有必胜态。

相当于拥有一个必胜态集合，将所有格子按照数值从大到小排序依次判断是否为必胜态，如果该点距离之前所有必胜态集合中的点距离都小于等于k，则该点也是一个必胜态，并加入集合，否则就是一个必败态。

剩下的问题就是如果快速判断某个点对于一个集合中所有点曼哈顿距离是否都小于等于k。

对于式子$|i - x| + |j - y|$可以分类讨论有：

$$|i - x| + |j - y| = \begin{cases}
(i + j) - (x - y) & i > x \ and\ j > y\\
(x + y) - (i - j) & i < x \ and \ j < y\\
(i - j) - (x - y) & i < x\ and\ j > y\\
(x - y) - (i - j) & i > x\ and\ j < y \end{cases}$$

也就可以将问题转化：

$|i - x| + |j - y| \leq k \Leftrightarrow max\{|(i + j) - (x + y)|, |(i - j) - (x - y)|\} \leq k$

于是只要维护$i+j,i-j$的最大最小值即可。

时间复杂度：$O(n^2)$，空间复杂度：$O(n^2)$。

代码

/*************************************************************************
    > File Name: 1.cpp
    > Author: Knowledge-Pig
    > Mail: 925538513@qq.com
    > Blog: https://www.cnblogs.com/Knowledge-Pig/
    > Created Time: 2022年03月28日 星期一 11时31分25秒
************************************************************************/

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define LL long long
#define pb push_back
#define fi first
#define se second
#define pr pair<int,int>
#define mk(a,b) make_pair(a,b)
#define endl '\n'
using namespace std;
int n, k, a[2022][2022];
pr p[2022 * 2022];
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
#endif
	cin >> n >> k;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j){
			cin >> a[i][j];
			p[a[i][j]] = mk(i, j);
		}
	int x = p[n * n].fi, y = p[n * n].se;
	int mx_s = x + y, mn_s = x + y, mx_d = x - y, mn_d = x - y;
	a[x][y] = 1;
	for(int i = n * n - 1, flag = 1; i >= 1; --i, flag = 1){
		x = p[i].fi, y = p[i].se;
		if(abs(mx_s - x - y) > k) flag = 0;
		if(abs(mn_s - x - y) > k) flag = 0;
		if(abs(mx_d - x + y) > k) flag = 0;
		if(abs(mn_d - x + y) > k) flag = 0;
		if(flag){
			mx_s = max(mx_s, x + y);
			mn_s = min(mn_s, x + y);
			mx_d = max(mx_d, x - y);
			mn_d = min(mn_d, x - y);
		}
		a[x][y] = flag;
	}
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j)
			cout << (a[i][j] ? 'M' : 'G');
		cout << endl;
	}
	return 0;
}