题解：P17022 [ROI 2026 Day2] 广义象棋

问题转化

统计最少需要重新涂色的格子数目是很困难的，所以我们考虑统计最多不需要重新涂色的格子数目。

用总格子数减去最多不需要重新涂色的格子数目即为最少需要重新涂色的格子数目。

计算最多不需修改数

我们记一个格子的坐标为 $(i,j)$，按照 $(i+j)$ 的奇偶性分为两类，目标每类的颜色必须相同，且两类的颜色不能相同。

我们可以记录每类颜色在类一与类二的数目，并取这两类的颜色出现数最大值和次大值。

我们考虑选择两种颜色进行保留，且两种颜色互不相同。

当两类的最大值颜色不相同，则取两个最大值；当两类的最大值颜色相同，就取一类的最大值和另一类的次大值。

当我们直接这么写完，会TLE。

::::info[TLE代码]

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define N 405

inline LL read(){
	char ch=getchar();
	int w=1;
	LL s=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')w*=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=(s<<3)+(s<<1)+(ch^48);
		ch=getchar();
	}
	return w*s;
}
inline void write(LL n){
	if(n<0)putchar('-'),n=-n;
	if(n>9)write(n/10);
	putchar(n%10+'0');
	return ;
}

LL a[N][N];
unordered_map<LL,LL>cnt1,cnt2;
struct node{
	LL col,num;
}ou1,ou2,ji1,ji2;
int main(){
	LL n=read();
	for(LL i=1;i<=n;i++)
		for(LL j=1;j<=n;j++)
			a[i][j]=read();
	for(LL i=1;i<=n;i++){
		ou1=ou2=ji1=ji2={0,0};
		for(LL j=1;j<=n;j++){
			for(LL k=1;k<=i;k++){
				if((k+j)%2==0){
					cnt2[a[k][j]]++;
					if(cnt2[a[k][j]]>=ou1.num){
						if(a[k][j]!=ou1.col)ou2=ou1;
						ou1={a[k][j],cnt2[a[k][j]]};
					}
					else if(cnt2[a[k][j]]>=ou2.num){
						ou2={a[k][j],cnt2[a[k][j]]};
					}
				}
				else{
					cnt1[a[k][j]]++;
					if(cnt1[a[k][j]]>=ji1.num){
						if(a[k][j]!=ji1.col)ji2=ji1;
						ji1={a[k][j],cnt1[a[k][j]]};
					}
					else if(cnt1[a[k][j]]>=ji2.num){
						ji2={a[k][j],cnt1[a[k][j]]};
					}
				}
			}
			LL ans=0;
			if(ou1.col!=ji1.col)ans=i*j-ou1.num-ji1.num;
			else if(ou1.col==ji1.col){
				ans=min(i*j-ou1.num-ji2.num,i*j-ou2.num-ji1.num);
			}
			printf("%lld ",ans);
		}
		putchar('\n'); 
		cnt1.clear();
		cnt2.clear();
	}
	return 0;
}

::::

优化

TLE的原因是 unordered_map 常数太大了，我们可以考虑离散化颜色。

ACcode

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define N 405

inline LL read(){
	char ch=getchar();
	int w=1;
	LL s=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')w*=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=(s<<3)+(s<<1)+(ch^48);
		ch=getchar();
	}
	return w*s;
}
inline void write(LL n){
	if(n<0)putchar('-'),n=-n;
	if(n>9)write(n/10);
	putchar(n%10+'0');
	return ;
}

LL a[N][N];
LL cnt1[N*N],cnt2[N*N];
unordered_map<LL,LL>id;
struct node{
	LL col,num;
}ou1,ou2,ji1,ji2;
int main(){
	LL n=read(),cnt=0;
	for(LL i=1;i<=n;i++)
		for(LL j=1;j<=n;j++){
			a[i][j]=read();
			if(!id[a[i][j]]){
				a[i][j]=id[a[i][j]]=++cnt;
			}
			else a[i][j]=id[a[i][j]];
		}
	for(LL i=1;i<=n;i++){
		ou1=ou2=ji1=ji2={0,0};
		for(LL j=1;j<=n;j++){
			for(LL k=1;k<=i;k++){
				if((k+j)%2==0){
					cnt2[a[k][j]]++;
					if(cnt2[a[k][j]]>=ou1.num){
						if(a[k][j]!=ou1.col)ou2=ou1;
						ou1={a[k][j],cnt2[a[k][j]]};
					}
					else if(cnt2[a[k][j]]>=ou2.num){
						ou2={a[k][j],cnt2[a[k][j]]};
					}
				}
				else{
					cnt1[a[k][j]]++;
					if(cnt1[a[k][j]]>=ji1.num){
						if(a[k][j]!=ji1.col)ji2=ji1;
						ji1={a[k][j],cnt1[a[k][j]]};
					}
					else if(cnt1[a[k][j]]>=ji2.num){
						ji2={a[k][j],cnt1[a[k][j]]};
					}
				}
			}
			LL ans=0;
			if(ou1.col!=ji1.col)ans=i*j-ou1.num-ji1.num;
			else if(ou1.col==ji1.col){
				ans=min(i*j-ou1.num-ji2.num,i*j-ou2.num-ji1.num);
			}
			printf("%lld ",ans);
		}
		putchar('\n');
		memset(cnt1,0,sizeof cnt1);
		memset(cnt2,0,sizeof cnt2); 
	}
	return 0;
}