2021 ICPC昆明站——L

2021 ICPC昆明站——L

题意：

给出一个长度为 n 的全排列数，对于每个逆序对之间连一条边，构成一个图（可能不连通） n≤1e6。
现要将该图染色，满足任意相邻两点颜色不同。
问最少用多少种颜色？输出染色方案。

T组测试样例，T≤1e6； sum{n} ≤ 1e6。

思路：

如果建边跑的话，最坏情况下光是建边就是 N 2 N^2 N2，所以建边不可行。
最多1e6个测试样例，所以应该是思维题。

对于一个位置 i 上的数 x，其需要和后面比 x 小的数所在位置相连，两个位置上颜色不能相同。
为了使得染色种类最少，而且保证相邻位置不能同一颜色，所以对于一个位置 i，其染色编号为其后面所有相连位置的染色最大编号+1。
又因为数列为全排列，所以一个数对应一种颜色，也就是说，一个位置上的数 x，其染色编号为：数 [1,x-1] 中，其染色编号最大值 +1。

可以用线段树或树状数组求 区间最大值。

Code：

const int N = 1000010, mod = 1e9 + 7;
int T, n, m;
struct Node{int l,r;int maxa;
}a[4*N];
int ans[N], b[N], f[N];void build(int u,int l,int r)
{a[u].l=l,a[u].r=r,a[u].maxa=0;if(l==r) return;else{int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);}
}int query(int u,int l,int r)
{if(a[u].l>=l&&a[u].r<=r){return a[u].maxa;}else{int mid=a[u].l+a[u].r>>1;int max1=0,max2=0;if(l<=mid) max1=query(u<<1,l,r);if(r>mid) max2=query(u<<1|1,l,r);return max(max1,max2);}
}void pushup(int u){a[u].maxa=max(a[u<<1].maxa,a[u<<1|1].maxa);
}void modify(int u,int x,int y)
{if(a[u].l==a[u].r){a[u].maxa=y;}else{int mid=a[u].l+a[u].r>>1;if(x<=mid) modify(u<<1,x,y);else modify(u<<1|1,x,y);pushup(u);}
}int main(){Ios;cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++) cin>>b[i], f[i]=0;build(1,1,n);int ans=0;for(int i=n;i>=1;i--){int maxa=query(1,1,b[i]-1)+1;f[b[i]]=maxa;modify(1,b[i],maxa);ans=max(ans,maxa);}cout<<ans<<"n"; //换成endl超时。。for(int i=1;i<=n;i++) cout<<f[b[i]]<<" ";cout<<"n";}return 0;
}

但是好像有LIS的做法？明天看一下。

思路2：LIS。

从后往前求最长上升子序列，记录当前位置在其所在最长上升子序列中的位置。该位置便是该点的染色编号。

朴素做法N^2，二分优化做法NlogN。

观察数列5 3 4 2 ，我们会发现其染色规律：
对于一个数，其染色编号为：其所在的 最后位置到当前位置所构成的最长上升子序列 中的位置。（因为在上升子序列中，一个位置后面的所有位置都是互相连线的，当前位置也要和后面所有位置连线，为了让连线两端颜色不同，该位置的染色编号就要+1；只有这种状态时，才需要新用一种颜色，其他情况不会新增，所以这种方式染色编号最少。）

Code：

typedef pair <int, int> PII;
unordered_map <int, int> mp;const int N = 1000010, mod = 1e9 + 7;
int stk[N];
vector<int> v;
int T, n, m;
int a[N];
int cnt;
int f[N], ans;bool check(int mid,int i)
{if(stk[mid]>=a[i]) return 1;return 0;
}void pd(int i)
{int l=1,r=cnt+1;stk[cnt+1]=1e9;while(l<r){int mid=l+r>>1;if(check(mid,i)) r=mid;else l=mid+1;}if(l==cnt+1) cnt++;stk[l]=a[i];f[a[i]]=l;ans=max(ans,f[a[i]]);
}int main(){Ios;cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i],f[i]=0;cnt=0,ans=0;for(int i=n;i>=1;i--){pd(i);}cout<<ans<<"n";for(int i=1;i<=n;i++) cout<<f[a[i]]<<" ";cout<<"n";}return 0;
}

现在看好似不太难，但赛时卡了两个小时。。