P8108 [Cnoi2021]绀珠传说 解题报告

P8108 [Cnoi2021]绀珠传说 解题报告：

更好的阅读体验

题意

给定一个 \(n\times n\) 的网格，用 \(n\) 种颜色染色，每种颜色恰好染 \(n\) 次，保证染色均匀随机。

你每次可以选择底端某一行连续的一个同色段，并将其消除，其上面的颜色都会因为重力掉下去。（感性理解一下）

最小化操作次数。

\(1\leqslant n\leqslant 1000\)。

分析

很有意思的题。

考虑每次消除的时候，将相邻的格子连边，考察它在游戏开始前的形态：

我们发现只有相邻的列之间有连边，且连边一定是不交的；反之，如果连边满足前面的约束，一定存在一种消除方式使得连边的格子在一次操作内被消除。

那么我们需要最大化连边数量，而由于第一条性质，不同列的连边之间互不影响，于是我们只用考虑两列之间的连边。

我们将边 \((i,a)-(i+1,b)\) 作为二维平面上的点 \((a,b)\)，可以发现可以共存的边一定两两满足偏序关系，那么直接树状数组扫一遍即可。

由于颜色是均匀随机的，每一列期望的颜色数量是 \(O(1)\) 的，那么总复杂度为 \(O(n^2\log n)\)。

代码

记得不要把行和列写反（

#include
#include
#define lowbit(x) (x&-x)
using namespace std;
const int maxn=1005;
int n,ans;
int a[maxn][maxn],t[maxn],tmp[maxn];
vectorv[maxn][maxn];
vectorp[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