P8108 [Cnoi2021]绀珠传说 解题报告:
更好的阅读体验
题意
给定一个 n\times n 的网格,用 n 种颜色染色,每种颜色恰好染 n 次,保证染色均匀随机。
你每次可以选择底端某一行连续的一个同色段,并将其消除,其上面的颜色都会因为重力掉下去。(感性理解一下)
最小化操作次数。
## 分析
很有意思的题。
考虑每次消除的时候,将相邻的格子连边,考察它在游戏开始前的形态:
我们发现只有相邻的列之间有连边,且连边一定是不交的;反之,如果连边满足前面的约束,一定存在一种消除方式使得连边的格子在一次操作内被消除。
那么我们需要最大化连边数量,而由于第一条性质,不同列的连边之间互不影响,于是我们只用考虑两列之间的连边。
我们将边 $(i,a)-(i+1,b)$ 作为二维平面上的点 $(a,b)$,可以发现可以共存的边一定两两满足偏序关系,那么直接树状数组扫一遍即可。
由于颜色是均匀随机的,每一列期望的颜色数量是 $O(1)$ 的,那么总复杂度为 $O(n^2\log n)$。
## 代码
记得不要把行和列写反(
```
#include<stdio.h>
#include<algorithm>
#define lowbit(x) (x&-x)
using namespace std;
const int maxn=1005;
int n,ans;
int a[maxn][maxn],t[maxn],tmp[maxn];
vector<int>v[maxn][maxn];
vector<int>p[maxn];
void update(int x,int v){
for(int i=x;i<=n;i+=lowbit(i))
t[i]=max(t[i],v);
}
int query(int x){
int res=0;
for(int i=x;i;i-=lowbit(i))
res=max(res,t[i]);
return res;
}
int main(){
scanf("%d",&n),ans=n*n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]),v[j][a[i][j]].push_back(i);
for(int i=1;i<n;i++){
for(int j=1;j<=n;j++)
for(int a=0;a<v[i][j].size();a++)
for(int b=0;b<v[i+1][j].size();b++)
p[v[i][j][a]].push_back(v[i+1][j][b]);
int res=0;
for(int j=1;j<=n;j++){
for(int k=0;k<p[j].size();k++)
tmp[k]=query(p[j][k]-1)+1,res=max(res,tmp[k]);
for(int k=0;k<p[j].size();k++)
update(p[j][k],tmp[k]);
p[j].clear();
}
ans-=res;
for(int j=1;j<=n;j++)
t[j]=0;
}
printf("%d\n",ans);
return 0;
}
```