20240112 A 组模拟赛 题解
前言
过于困难了，赛时还犯蠢忘了最小割是什么，但是没挂分。
T2
看起来像 flow 题，但是赛时犯蠢不会 50pts 暴力。
具体来说，设 \(f_i\) 表示以 \(i\) 结尾的 LIS 长度，并且整个序列的 LIS 为 \(F\)，对于所有 \(j>i,a_j>a_i,f_j=f_i+1\) 连一条有向边 \((i,j)\)，容易发现要求的就是最少删掉多少点使得所有长度恰好为 \(F\) 的路径都被截断。
那么就是最小割经典建模了，拆点后源点连所有 \(f_i=1\)，汇点连 \(f_i=F\)，跑最大流即可。据说复杂度是 \(O(n^2\sqrt{n})\) 可以过 50pts。
然后考虑 \(f_i\) 相等的集合 \(S_{k}=\begin{Bmatrix}i|f_i=k\end{Bmatrix}\)，容易发现若按 \(i\) 升序，那么 \(a_i\) 必定降序。观察除去 \(f_j=f_i+1\) 以外的两个连边限制，容易发现 \(S_{k-1}\) 的某个点必定连向 \(S_k\) 的某个连续的区间。线段树优化建图，据说复杂度是 \(O(n\sqrt{n}\log n)\)。
考虑模拟网络流（乐，不会）。容易发现对于 \(S_i\) 内的两点 \(u,v(u<v)\)，它们连向的 \(S_{i+1}\) 的区间分别是 \([l_u,r_u],[l_v,r_v]\)，容易发现有 \(l_u\le l_v,r_u\le r_v\)。那么每个点尽可能向下一层编号更小的点增广是显然不劣的。就可以维护一个不需要退流的网络流，再对每个 \(S\) 开一个指针复杂度就能做到 \(O(n)\) 了。此时瓶颈在于求 LIS。复杂度 \(O(n\log n)\)。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e6+5,inf=0x3f3f3f3f;
int n,a[N],f[N];
vector<int> vec[N];
int po[N];
int find(int x){
int ll=0,rr=n,mm;
while(ll<rr){
mm=(ll+rr+1)>>1;
if(a[vec[mm].back()]<x) ll=mm;
else rr=mm-1;
}
return ll;
}
int mx;
int dfs(int x,int y){
if(x==mx) return 1;
while(po[x+1]<(int)vec[x+1].size()&&vec[x+1][po[x+1]]<vec[x][y]) ++po[x+1];
while(po[x+1]<(int)vec[x+1].size()&&a[vec[x+1][po[x+1]]]>a[vec[x][y]]){
int gt=dfs(x+1,po[x+1]);++po[x+1];
if(gt){
return 1;
}
}
return 0;
}
signed main(){
n=read();
forup(i,1,n){
a[i]=read();
}
a[0]=inf;
forup(i,1,n) vec[i].push_back(0);
forup(i,1,n){
f[i]=find(a[i])+1;
mx=max(mx,f[i]);
vec[f[i]].push_back(i);
}
forup(i,1,mx) po[i]=1;
int ans=0;
while(po[1]<(int)vec[1].size()){
ans+=dfs(1,po[1]);
++po[1];
}
printf("%d\n",n-ans);
}