CF2069B Set of Strangers 解题报告

_mi_ka_ · 2025-02-21 15:54:39 · 题解

题目传送门

题目大意

对于一个 n\times m 的颜色板，每次操作只能选择若干个相同颜色且任意两个块都没有相邻的边的块，将这些块涂成同一种任意颜色，问要将这个颜色板的所有块的颜色统一，最少要进行多少次操作。

解题思路

选取一种最终颜色 c，对于其中的任意一种颜色 c'：

• 如果这种颜色的块中没有相邻的，那么一次以内的操作以定能将其变成颜色 c；
• 若果这种颜色的块中有相邻的，第一次操作对于相邻的块，选取其一进行修改，则第二次操作时剩余的块肯定都不相邻，那么最多两次操作一定能将其变成颜色 c。

综上，每一种颜色根据其有没有相邻的块可以分成一次和两次修改完，对于颜色板遍历一遍，标记出有相邻块的颜色和没有块的颜色即可。

对于要选取的最终颜色 c，只需贪心的选取要进行的操作次数最多的颜色即可。

AC Code

#include<bits/stdc++.h>
using namespace std;
int a[720][720];//颜色板 
int ans;//答案 
int tpe[500000];//每种颜色需要进行的操作数 
int re()//快读
void wr(int x)//快写
signed main(){
    int T=re();
    while (T--)
    {
        int n=re(),m=re();
        ans=0;
        for(int i=1;i<=n*m;i++)
            tpe[i]=0;
        for(int i=1;i<=n;i++)
            a[i][m+1]=0;
        for(int i=1;i<=m;i++)
            a[n+1][i]=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                a[i][j]=re();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                int flag=(a[i][j]==a[i-1][j]||a[i][j]==a[i][j-1]||a[i][j]==a[i+1][j]||a[i][j]==a[i][j+1]);
                //flag代表这种颜色是否有相邻 
                if(tpe[a[i][j]]==0)
                    ans+=tpe[a[i][j]]=int(flag)+1;//有相邻就是2，没相邻就是1 
                else if(tpe[a[i][j]]==1)
                    ans+=int(flag),(tpe[a[i][j]]+=int(flag));//flag==1则为2 
                else
                    continue;
            }
        int maxx=0;//选取操作次数最多的颜色 
        for(int i=1;i<=n*m;i++)
            maxx=max(maxx,tpe[i]);
        wr(ans-maxx),putchar('\n');
    }
    return 0;
}