自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 23:09:45，当前版本为作者最后更新于2025-02-13 14:42:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

明显可以枚举哪个位置的颜色会变，对于左上，右上，左下，右下四个 $2 \times 2$ 的正方形统计一下变化后的答案，和全局答案取个 $\max$ 即可。

实现有个小细节，对于 $k$ 比较小的情况可以暴力枚举换成哪种颜色，$k$ 比较大时换成一种没有出现过的颜色即可。

大概就是这样：

il void mian(){
	read(n, k);
	L(i, 1, n) L(j, 1, n) a[i][j] = read();
	int ans = 0;
	L(i, 1, n - 1){
		L(j, 1, n - 1){
			set<int> st;
			st.insert(a[i][j]), st.insert(a[i + 1][j]), st.insert(a[i][j + 1]), st.insert(a[i + 1][j + 1]);
			if (st.size() >= 3) ans++;
		}
	}
	int ret = 0;
	L(i, 1, n){
		L(j, 1, n){
			int cnt = ans;
			set<int> st, st1, st2, st3, st4;
			if (i > 1) st1.insert(a[i - 1][j]), st2.insert(a[i - 1][j]), st.insert(a[i - 1][j]);
			if (j > 1) st1.insert(a[i][j - 1]), st3.insert(a[i][j - 1]), st.insert(a[i][j - 1]);
			if (i < n) st3.insert(a[i + 1][j]), st4.insert(a[i + 1][j]), st.insert(a[i + 1][j]);
			if (j < n) st2.insert(a[i][j + 1]), st4.insert(a[i][j + 1]), st.insert(a[i][j + 1]);
			if (i > 1 && j > 1) st1.insert(a[i - 1][j - 1]), st.insert(a[i - 1][j - 1]);
			if (i > 1 && j < n) st2.insert(a[i - 1][j + 1]), st.insert(a[i - 1][j + 1]);
			if (i < n && j > 1) st3.insert(a[i + 1][j - 1]), st.insert(a[i + 1][j - 1]);
			if (i < n && j < n) st4.insert(a[i + 1][j + 1]), st.insert(a[i + 1][j + 1]);
			int tot = 0;
			if (k <= 5000 && st.find(k) != st.end()){
				L(c, 1, k){
					int rrt = 0;
					set<int> sst1 = st1, sst2 = st2, sst3 = st3, sst4 = st4;
					int flg1 = 0, flg2 = 0, flg3 = 0, flg4 = 0;
					if (st1.size() == 2) flg1++;
					if (st2.size() == 2) flg2++;
					if (st3.size() == 2) flg3++;
					if (st4.size() == 2) flg4++;
					if (st1.find(c) == st1.end()) sst1.insert(c);
					if (st2.find(c) == st2.end()) sst2.insert(c);
					if (st3.find(c) == st3.end()) sst3.insert(c);
					if (st4.find(c) == st4.end()) sst4.insert(c);
					if (sst1.size() == 3 && st1.find(a[i][j]) != st1.end() && flg1) rrt++;
					if (sst2.size() == 3 && st2.find(a[i][j]) != st2.end() && flg2) rrt++;
					if (sst3.size() == 3 && st3.find(a[i][j]) != st3.end() && flg3) rrt++;
					if (sst4.size() == 3 && st4.find(a[i][j]) != st4.end() && flg4) rrt++;
					// if (i == 4 && j == 5){
					// 	wtsp(c), wtln(rrt);
					// }
					ckmax(tot, rrt);
				}
				cnt += tot;
			}
			else{
				int flg1 = 0, flg2 = 0, flg3 = 0, flg4 = 0;
				set<int> sst1 = st1, sst2 = st2, sst3 = st3, sst4 = st4;
				sst1.insert(a[i][j]), sst2.insert(a[i][j]), sst3.insert(a[i][j]), sst4.insert(a[i][j]);
				if (sst1.size() == 2) flg1++;
				if (sst2.size() == 2) flg2++;
				if (sst3.size() == 2) flg3++;
				if (sst4.size() == 2) flg4++;
				// wtsp(flg1), wtsp(flg2), wtsp(flg3), wtln(flg4);
				// wtsp(st1.size()), wtsp(st2.size()), wtsp(st3.size()), wtln(st4.size());
				st1.insert(k), st2.insert(k), st3.insert(k), st4.insert(k);
				if (st1.size() == 3 && flg1) cnt++;
				if (st2.size() == 3 && flg2) cnt++;
				if (st3.size() == 3 && flg3) cnt++;
				if (st4.size() == 3 && flg4) cnt++;
			}
			// if (st1.size() == 3) cnt++;
			// if (st2.size() == 3) cnt++;
			// if (st3.size() == 3) cnt++;
			// if (st4.size() == 3) cnt++;
			// wtsp(i), wtsp(j), wtln(cnt);
			ckmax(ret, cnt);
		}
	}
	write(ret);
}