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<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; }