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