CSPS2021-1 题解

题目大意

分析部分为了节省字数，把国内区叫做 A，国际区叫做 B。

$n$ 个廊桥分配给 A 和 B。A 有 $m_1$ 个飞机 B 有 $m_2$ 个飞机。每个飞机有一段区间表示停留时间。先到的飞机可以先占自己类的廊桥，使用到飞走，如果自己的类别没有可以使用的廊桥就只能停在飞机场。求最多能让多少飞机停在廊桥。

本博客包含一个错解和两个正解（准确地说是正解和骗分在冥间数据骗到满分的解）。错解三分查找中给出了错误原因和 Hack，正解和伪正解分别是真正的正解线段树和玄学乱糊模拟退火。两个正解都给出了带注释的代码，希望大家阅读愉快。

考场解法（错解）

考虑一组最优解 $a_1,a_2$ 表示给 A 类 $a_1$ 廊桥，B 类 $a_2$ 个廊桥，如果减小 $a_1$ 的值，A 类区间就要删除更多的区间，B 类区间会减少需要删除的区间（使得剩下的飞机都可以停廊桥）。但是因为 $a_1,a_2$ 已经是最优解了，B 类区间减少的要删除的区间数量不大于 A 类区间要增加的区间数量。

因此推测最后的答案呈单峰性质。考虑三分查找找到峰值。

现在的问题就是我已经确定了 $a_1,a_2$ ，如何用一个可以接受的复杂度去求解需要删除多少个区间。不难看出，如果按照区间的左端点排个序，显然可以按照顺序，加进一个区间时，如果区间左端点上没有被至少 $a_i$ 个区间覆盖，就加进去，否则删掉这个区间。用线段树维护区间的覆盖情况。

复杂度 $\operatorname{O}(n\log_{\frac{3}{2}}\log_2 n)$ ，空间复杂度 $\operatorname{O}($ 能过 $)$ 。

错误的原因是，可以证明这并不是单峰的。因为显然，有可能有多种方案，使得停在廊桥的飞机数量相同，而这多种方案的 $a_1,a_2$ 不一定是连续的。Hack 数据如下：

枚举所有的情况如下：

A类（国内）	B类（国际）	答案（飞机数）
0	4	4
1	3	5
2	2	4
3	1	5
4	0	4

如果把区间关系画下来，就会发现 A,B 类是一模一样的，而一类 $1$ 个另一类 $3$ 个是最优解，但是这里显然每类各两个不是最优解，因此出现了双峰。如果出题人造数据恶心一点，还会出现三峰四峰等等。

正解

初改题解法（乱搞糊正解）

既然并不是单峰的，那不就可以模拟退火吗？

朴素的贪心算法，我们找到一个点，每次贪心地走左边或者右边，如果当前这个点的函数值（即答案）更小就走这边。显然这是错误的，我们会卡死在一个局部最优的情况。这个贪心显然被假掉的原因就在于我们被拘束在一个局部凸包里面，无法跳出去。如果我们给一个概率使它可以跳出去呢？

这就是模拟退火有一定概率得到正确答案的原因。确切地说，考虑模拟物理降温的过程：

设定一个当前温度 $T$ 。
设定每次温度的变化比 $\Delta T$ 。
每次退火，找到一个向左的位置和向右的位置，求其函数值 $\operatorname{f}(x),\operatorname{f}(y)$ 。
如果一端比当前状态小的话，贪心地跳过去。
温度降到一定值以下截止。

找到的向左的位置和向右的位置不能乱定。原则上，越到后面，我们会越趋近于正解，所以应该逐渐稳定下来。本着越来越稳定的原则，温度越低波动应该越小，因此一般以 $T\times k\times rand$ 为左右发展长度，其中 $k$ 是根据题目不同自行设定的，一般直接设为 $n$ ， $rand$ 是属于区间 $(0,1]$ 的实数。

关于给定了 $a_1,a_2$ 如何判断几个飞机，肯定不能再用线段树维护了，这样要么时间爆炸要么答案准确率爆炸。我们考虑对于每一个区间 $[l,r]$ 会对时间轴产生两个贡献： $l$ 位置 $+1$ ， $r$ 位置 $-1$ （也就是区间和用差分维护了）。表示选择这个数这一段区间会多一个占用廊桥的区间。注意如果数量超过了给它分配的廊桥数，这个区间的贡献不能计算进时间轴。

冥间数据 AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=100005;
inline int read(){
   int x=0;bool w=0;char c=getchar();
   while(c<'0' || c>'9') w|=c=='-',c=getchar();
   while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
   return w?-x:x;
}
inline void write(int x){
   if(x<0) x=-x,putchar('-');
   if(x>9) write(x/10);
   putchar(x%10^48);
}

int n,m1,m2,q1[max_n*4],q2[max_n*4];
struct plane{
   int l,r;
   inline void init(int x,int y){
       l=x,r=y;
   }
}a[max_n],b[max_n];
inline bool cmp(plane a,plane b){ // 左端点排序
   return a.l<b.l;
}

int lisan[max_n*4],cntls;

int ans,nowans,R1,R2;

int In[max_n],a1[max_n*4],a2[max_n*4],ar[max_n],br[max_n];
// a1：国内飞机的差分贡献（左端点 +1 右端点 -1）
// In：记忆化
// ar：国内每个时间点如果有飞机进来，记录其出去的时间
// a2，br 同理，是针对国际飞机的
inline int check(int in){ // O(n) 判断几个飞机停桥
   if(In[in]) return In[in]; // 记忆化
   int out=n-in,res=0,tmp=0;
   for(register int i=1;i<=R1;++i) // 因为有修改飞机贡献所以要备份
   	a1[i]=q1[i];
   for(register int i=1;i<=R2;++i)
   	a2[i]=q2[i];
   for(register int i=1;i<=R1;++i){// 国内
   	if(a1[i]==1 && tmp<in) // 可以停进去
   		++res;
   	else if(a1[i]==1) // 停不进去要撤销飞机贡献
   		a1[i]=a1[ar[i]]=0;
   	tmp+=a1[i];
   }
   tmp=0;
   for(register int i=1;i<=R2;++i){// 国际，同理
   	if(a2[i]==1 && tmp<out)
   		++res;
   	else if(a2[i]==1)
   		a2[i]=a2[br[i]]=0;
   	tmp+=a2[i];
   }
   return In[in]=res;
}

int As[max_n];
const int tim=3;
const double tem=1145.141919810,delta=0.987654321,eps=1e-15;
// 随便怎么调参都能过冥间数据
inline void findans(){ // 模拟退火
   int anss=ans,nowanss=nowans;
   double nowt=tem;
   while(nowt>eps){
   	int len=1.0*nowt*n*rand()/RAND_MAX,L=nowanss-len,R=nowanss+len;
       // 找到一个左端点和右端点
   	if(L>=0){
   		int tmp=check(L);
   		if(tmp>anss){ // 更新当前答案
   			anss=tmp,
   			nowanss=L;
   			if(ans<anss){ // 更新全局答案
   				ans=anss,
   				nowans=nowanss;
   			}
   		}
   	}
   	if(R<=n){
   		int tmp=check(R);
   		if(tmp>anss){
   			anss=tmp,
   			nowanss=R;
   			if(ans<anss){
   				ans=anss,
   				nowans=nowanss;
   			}
   		}
   	}
   	nowt*=delta;
   }
   if(ans<anss){
   	ans=anss,
   	nowans=nowanss;
   }
}

signed main(){
   n=read(),m1=read(),m2=read();
   for(register int i=1;i<=m1;++i){
       int l=read(),r=read();
       a[i].init(l,r);
       lisan[++cntls]=l, // lisan 是离散化
       lisan[++cntls]=r;
   }
   sort(lisan+1,lisan+1+cntls),R1=cntls;
   for(register int i=1;i<=m1;++i){
       a[i].l=lower_bound(lisan+1,lisan+1+cntls,a[i].l)-lisan;
       a[i].r=lower_bound(lisan+1,lisan+1+cntls,a[i].r)-lisan;
       q1[a[i].l]=1,q1[a[i].r]=-1; // 统计飞机贡献
       ar[a[i].l]=a[i].r;
   }
   cntls=0;
   for(register int i=1;i<=m2;++i){ // 国际部同理
       int l=read(),r=read();
       b[i].init(l,r);
       lisan[++cntls]=l,
       lisan[++cntls]=r;
   }
   sort(lisan+1,lisan+1+cntls),R2=cntls;
   for(register int i=1;i<=m2;++i){
       b[i].l=lower_bound(lisan+1,lisan+1+cntls,b[i].l)-lisan;
       b[i].r=lower_bound(lisan+1,lisan+1+cntls,b[i].r)-lisan;
       q2[b[i].l]=1,q2[b[i].r]=-1;
       br[b[i].l]=b[i].r;
   }

   sort(a+1,a+1+m1,cmp), // 别忘记 sort
   sort(b+1,b+1+m2,cmp);

   ans=check(n/2),nowans=n/2;
   while(clock()<CLOCKS_PER_SEC*0.8)
   	findans();
   write(ans);
   return 0;
}

再改题解法（真正的正解）

上面这个模拟退火在 HydroOJ 的冥间数据上只有 $70$ 分，如果加上波动之类的，改成正经的模拟退火说不定会比较优秀，但是这些事情就留给后人吧。

需要考虑区间重叠情况，具备“先到先得”性质。进一步得到一个结论：假设 $a_1$ 是给 A 类区间的桥数， $a_1$ 增加的时候，原来在 A 类不会删除的区间还是不会被删除。B 类同理。也就是说，对于一个飞机如果需要 $k$ 个廊桥它才能停廊桥，那我给 $k+1$ 个，它还是可以停廊桥。

不妨假设廊桥不要钱，可以随便来。我们不妨尝试求出每一个飞机，我给多少个廊桥才可以让它停在飞机场。为什么要这么尝试呢？因为假设我们已经求出每一个飞机至少要给这一类几个廊桥它才能停了，那么就可以 $\operatorname{O}(n)$ 地求出给这一类几个廊桥，会有多少飞机可以停进来。于是就可以 $\operatorname{O}(n)$ 枚举给 A 类多少廊桥，给 B 类多少廊桥，得到一共多少飞机停进来，求结果最大值。

现在就只有唯一的一个问题：对于一个类（不妨假设为 A 类，因为 B 类部分做法和 A 类完全一致），的每一个飞机，我要给这个类多少廊桥，使得这个飞机可以进廊桥。

不妨画一个图，下面的区间 $a,b,c,d,e,f,g$ 都属于 A 类飞机对应的区间， $x$ 轴表示时间轴：

第一个进场的 $c$ 区间需要分配一个廊桥，记廊桥编号为 $1$ 。
第二个进场的 $b$ 区间，因为 $1$ 号廊桥还在被 $c$ 占用，所以要开一个廊桥 $2$ 。
随后 $f$ 区间进场，虽然廊桥 $2$ 被 $b$ 占用了，但是廊桥 $1$ 的 $c$ 已经用完飞走了，就没必要建新廊桥了，可以直接使用廊桥 $1$ 。
$g$ 区间进场，廊桥 $1,2$ 分别被 $f,b$ 占用，所以只能再建一个廊桥 $3$ 给 $g$ 用。
然后是 $a$ 区间，廊桥 $1,3$ 被 $f,g$ 占用，但是廊桥 $2$ 的 $b$ 已经走了，所以可以进廊桥 $2$ 。
轮到 $e$ 进场的时候，我们发现廊桥 $1,2$ 都可以使用，廊桥 $3$ 被 $g$ 占用。具体是选 $1$ 还是 $2$ ，我们不妨从简而谈，选择编号更小的廊桥，方便直接通过廊桥编号求出至少几个廊桥可以让它停进来。因此我们给 $e$ 选择 $1$ 号廊桥。
姗姗来迟的 $d$ 只有 $2$ 号廊桥一个选择。到此所有处理结束了。

总结手玩数据思路：

对于一个区间开始的时候，先判断是否所有的廊桥已经被占用。
如果所有廊桥已经被占用，新开一个廊桥给它。
否则找到编号最小的廊桥给它。

线段树维护各个时间轴的点上，没有被占用的廊桥编号的最小值即可。

#include<bits/stdc++.h>
using namespace std;
const int max_n=100005,inf=2100000000;
inline int read(){
   int x=0;bool w=0;char c=getchar();
   while(c<'0' || c>'9') w|=c=='-',c=getchar();
   while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
   return w?-x:x;
}
inline void write(int x){
   if(x<0) x=-x,putchar('-');
   if(x>9) write(x/10);
   putchar(x%10^48);
}

int lisan[max_n*4],cntls,R1,R2;

int n,m1,m2;
struct plane{
   int l,r;
   inline void init(int x,int y){
       l=x,r=y;
   }
}a[max_n],b[max_n];
inline bool cmp(plane a,plane b){
   return a.l<b.l;
}

struct segment_tree{ // 下标为时间，值为可用廊桥编号最小值
   int L[max_n*8],R[max_n*8];
   int mn[max_n*8];

   #define ls(x) (x<<1)
   #define rs(x) (x<<1|1)

   inline void pushup(int x){
   	mn[x]=min(mn[ls(x)],mn[rs(x)]);
   }
   inline void build(int x,int l,int r){ // 清空线段树
   	L[x]=l,R[x]=r,mn[x]=inf;
   	if(l==r) return;
   	int mid=(l+r)>>1;
   	build(ls(x),l,mid),
   	build(rs(x),mid+1,r);
   	pushup(x);
   }
   inline void upd(int x,int pos,int val){ // 单点赋值
   	if(L[x]==pos && R[x]==pos){
   		mn[x]=val;
   		return;
   	}
   	int mid=(L[x]+R[x])>>1;
   	if(pos<=mid) upd(ls(x),pos,val);
   	else upd(rs(x),pos,val);
   	pushup(x);
   }
   inline int ask(int x,int l,int r){ // 区间查询最小值
   	if(l<=L[x] && R[x]<=r) return mn[x];
   	int mid=(L[x]+R[x])>>1,res=inf;
   	if(l<=mid) res=min(res,ask(ls(x),l,r));
   	if(r>mid) res=min(res,ask(rs(x),l,r));
   	pushup(x);
   	return res;
   }
}seg;

int ls[max_n],id[max_n]; // id->廊桥编号 ls->这个廊桥的上一个使用者
int f1[max_n],f2[max_n];// f1-> A 类区间给 i 个廊桥，有 f1[i] 个飞机可以，f2 同理

inline void sol1(){ // 处理 A 类区间
   int cnt=0; // 目前有几个廊桥
   seg.build(1,1,R1);
   for(register int i=1;i<=m1;++i){
   	int l=a[i].l,r=a[i].r;
   	int ask=seg.ask(1,1,l);
   	if(ask==inf){ // 没有没被占用的廊桥
   		id[i]=++cnt,ls[cnt]=r;
   		seg.upd(1,r,cnt);
   	}
   	else{
   		id[i]=ask,seg.upd(1,ls[ask],inf); // 清空上个主人在这个廊桥的信息
   		ls[ask]=r,seg.upd(1,r,ask);// 占用这个廊桥
   	}
   }
   for(register int i=1;i<=m1;++i) ++f1[id[i]];
   for(register int i=1;i<=m1;++i) f1[i]+=f1[i-1];
}
inline void sol2(){ // 处理 B 类，同理
   int cnt=0;
   memset(ls,0,sizeof(ls));
   seg.build(1,1,R2);
   for(register int i=1;i<=m2;++i){
   	int l=b[i].l,r=b[i].r;
   	int ask=seg.ask(1,1,l);
   	if(ask==inf){
   		id[i]=++cnt,ls[cnt]=r;
   		seg.upd(1,r,cnt);
   	}
   	else{
   		id[i]=ask,seg.upd(1,ls[ask],inf);
   		ls[ask]=r,seg.upd(1,r,ask);
   	}
   }
   for(register int i=1;i<=m2;++i) ++f2[id[i]];
   for(register int i=1;i<=m2;++i)	f2[i]+=f2[i-1];
}

signed main(){
   n=read(),m1=read(),m2=read();
   for(register int i=1;i<=m1;++i){
   	int l=read(),r=read();
   	a[i].init(l,r);
   	lisan[++cntls]=l,lisan[++cntls]=r;
   }
   sort(lisan+1,lisan+1+cntls),R1=cntls; // 熟悉的离散化
   for(register int i=1;i<=m1;++i){
   	a[i].l=lower_bound(lisan+1,lisan+1+cntls,a[i].l)-lisan;
   	a[i].r=lower_bound(lisan+1,lisan+1+cntls,a[i].r)-lisan;
   }
   cntls=0;
   for(register int i=1;i<=m2;++i){
   	int l=read(),r=read();
   	b[i].init(l,r);
   	lisan[++cntls]=l,lisan[++cntls]=r;
   }
   sort(lisan+1,lisan+1+cntls),R2=cntls;
   for(register int i=1;i<=m2;++i){
   	b[i].l=lower_bound(lisan+1,lisan+1+cntls,b[i].l)-lisan;
   	b[i].r=lower_bound(lisan+1,lisan+1+cntls,b[i].r)-lisan;
   }

   sort(a+1,a+1+m1,cmp),
   sort(b+1,b+1+m2,cmp); // 记得要 sort

   sol1(),sol2();
   int ans=0;
   for(register int i=0;i<=n;++i)
   	ans=max(ans,f1[i]+f2[n-i]); // i 个给 A 类，n-i 个给 B 类
   write(ans);
   return 0;
}

题目大意

考场解法（错解）

正解

初改题解法（乱搞糊正解）

再改题解法（真正的正解）

感谢您的支持，我会继续努力的!