B题 随机化写法

赛时看到B题第一个想到的是随机化。因为没get到hh和ww可以交换，wa了好久都没过，后面换了另一种写法（单调队列压缩矩阵）。

但是比赛结束后发现，随机化竟然过了94%的数据！然后swap了一下hh和ww，在重复一次随机化过程就过了。

这个随机化也很简单。将矩阵中的每一个数随机映射到一个其他的数。

然后对这个矩阵做一下二维前缀和，之后枚举每一个h×wh\times w的矩形，判断里面的和是否整除(h×w)(h\times w)。如果无法整除说明该矩形一定不合法；如果能整除说明该矩形可能合法，但是不合法的概率应该是比较小的，可以多重复一下上述过程以减小出错概率。

（值得一提的是，我试了试将随机次数调整为1竟然也能过）

代码如下：

#include <bits/stdc++.h>
#define len(x) int(x.size())
#define all(x) begin(x),end(x)
#define debug(x) cout<<#x<<": "<<x<<endl;
using namespace std;
using ll = long long;
const int inf = 0x3f3f3f3f;
const int N = 1e6 + 10;

template <typename T>
inline void read(T &x) {
	x = 0; int f = 1;
	char ch = getchar();
	while (!isdigit(ch))  { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch))  x = x * 10 + ch - '0', ch = getchar();
	x *= f;
}

template <typename T, typename ...Args>
inline void read(T &t, Args &...args) {
	read(t); read(args...);
}

template <typename T>
inline void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9)   write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T>  
inline void write(T x, char ch) {
	write(x), putchar(ch);
}

int n, m, h, w;
ll cnt, b[N];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	read(n, m);
	vector<vector<ll>> g(n + 1, vector<ll>(m + 1));
	
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++) {
			read(g[i][j]);
			b[cnt ++] = g[i][j];
		}
	read(h, w);
	// 离散化
	sort(b, b + cnt);
	cnt = unique(b, b + cnt) - b;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			g[i][j] = lower_bound(b, b + cnt, g[i][j]) - b;
	
	auto chk = [&](int h, int w) {
		if (h > n or w > m)	return false;
		mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
		vector<vector<bool>> ok(n + 1, vector<bool>(m + 1, true));

		int T = 10;  // 随机次数
		while (T --) {
			for (int i = 1; i <= n; i ++)
				for (int j = 1; j <= m; j ++)	b[g[i][j]] = rng();
			
			vector<vector<ll>> sum(n + 1, vector<ll>(m + 1));
			for (int i = 1; i <= n; i ++)
				for (int j = 1; j <= m; j ++) {
					sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + b[g[i][j]];
				}

			for (int i = h; i <= n; i ++)
				for (int j = w; j <= m; j ++) {
					ll tot = sum[i][j] - sum[i][j - w] - sum[i - h][j] + sum[i - h][j - w];
					if (tot % (h * w))	ok[i][j] = false;
				}
		}

		bool succes = false;
		for (int i = h; i <= n; i ++)
			for (int j = w; j <= m; j ++) {
				if (ok[i][j])	return true;
			}
		return false;
	};

	if (chk(h, w) or chk(w, h))	cout << "YES" << '\n';
	else	cout << "NO" << '\n';
	
	return 0;
}