队伍配置：

和我这个菜鸡。

膜拜另外两个大佬

赛况：

\(PS:\) 看高二的在那边打感觉挺有趣的我们也跑过来打了。

首先我把 \(A\) 签到题给签了，然后去看 \(D\) ， \(gsc\) 去看 \(C\) ，这时候 \(lyq\) 大佬还没有加入战场，还在调自己的题，不过问题不大。

我很快看出了 \(D\) 的贪心，然后这时候 \(lyq\) 加入战场，直接开 \(F\) ，\(\%\%\%\) 。我很快写完 \(D\) ，结果死活过不去，吃了两发罚时还没有做出来， \(gsc\) 也发现自己看错题了，然后 \(lyq\) 已经开码 \(F\) 的树套树了。

没过多久 \(gsc\) 的 \(C\) 写完了，过来帮我调 \(D\) ，然后我看 \(I\) 很多人过了，就去写 \(I\) ，让 \(gsc\) 坐牢帮我调题。然后很快 \(lyq\) 的树套树写好了，结果发现 \(\log^2\) 跑不过去，只好换线段树二分。然后我很快写了 \(I\) ，结果又是罚时，有没有过，然后又是坐牢调题。

过了一会， \(gsc\) 说他帮我找到了 \(hack\) 数据，然后我自己就在那边改， \(gsc\) 又去帮我调 \(I\) ，然后我也不知道他怎么改，帮我过掉了 \(I\) 。然后我改我的 \(D\) ，结果还是过不去，吃了 \(4\) 发罚时了，恼羞成怒。拍案而起，润去写 \(B\) 。

一个小时多一点的时候， \(lyq\) 大佬凭借强大的码力通过了那个大数据结构题，然后来帮忙我写 \(D\) 。

过了 \(20\) 分钟， \(gsc\) 把 \(K\) 切了，然后又过了 \(10\) 分钟，我把 \(B\) 写了。

这时候改签的到差不多签完了，还剩 \(D,E\) 是比较可做的题。

这时候 \(lyq\) 写好了 \(D\) ，但是没过，让我帮他调，帮他调的时候我突然意识到自己哪里写错了，然后把我的 \(D\) 改了一下交上去就过了，这样我们就还差 \(E\) ，就基本上可以打卡下班了。

一开始 \(E\) 我以为是 \(sa\) ，然后乱搞，然后 \(lyq\) 大佬 \(trie\) 树排排序，然后二分就秒了，他写了差不多一个小时写完了，这时候赛事排名已经来到了 \(29\) 。

这时候 \(gsc\) 大佬在做 \(M\) ，他直接现场学习旋转卡壳，然后后来发现假了。

我就看看 \(G\) 看看 \(H\) 发现都不会做，然后摆烂，提前下班。

然后就结束了，最后排名这鸟样。

这把 \(D\) 属实是有点坑逼了。

来写写题解：

\(A\)

这题还要题解？？？

点击查看代码

#include<bits/stdc++.h>
typedef long long Ll;

using namespace std;
const int MAXN=1e5+10;
int T,sta,n,a[MAXN],vis[MAXN];
int main () {
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&sta);
		scanf("%d",&n);
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;++i) {
			scanf("%d",&a[i]);
			vis[a[i]]=1;
		}
		int ed;
		scanf("%d",&ed);
		int ans=0;
		for(int i=sta;i<=ed;++i) ans+=(!vis[i]);
		printf("%d\n",ans);
	}
	return 0;
}

\(B\)

记一个状态 \(f_i\) 表示前 \(i\) 个选完且满足了那些已经结尾的区间且第 \(i\) 个必选的最小代价。

\(f_i=\min f_j+a_i\)

如果一个区间结束了，那么这个区间左端点左边的那些决策的都不能选，赋值成无限大即可。

然后我就写了一个线段树去优化他，实际上不用，直接单调队列即可。

点击查看代码

#include<bits/stdc++.h>
typedef long long LL;

using namespace std;
const int MAXN=5e5+10;
const LL inf=1e18+10;
int T,n;
int a[MAXN];
vector<int> e[MAXN];
struct ddl {
	LL a;
	LL lb;
}tr[MAXN*4];
void psup(int u) {
	tr[u].a=min(tr[(u<<1)].a,tr[(u<<1|1)].a);
}
void build(int u,int l,int r) {
	tr[u].lb=0;
	if(l==r) {
		tr[u].a=inf;
		return ;
	}
	int mid=(l+r)/2;
	build((u<<1),l,mid);
	build((u<<1|1),mid+1,r);
	psup(u);
}
void zx(int x) {
	tr[x].lb=1;
	tr[x].a=inf;
}
void psdn(int u) {
	if(tr[u].lb) {
		zx((u<<1));
		zx((u<<1|1));
		tr[u].lb=0;
	}
}
void update(int u,int l,int r,int x,LL y) {
	if(l>x||r<x) return ;
	if(l==r) {
		tr[u].a=min(tr[u].a,y);
		return ;
	}
	int mid=(l+r)/2;
	psdn(u);
	update((u<<1),l,mid,x,y);
	update((u<<1|1),mid+1,r,x,y);
	psup(u);
}
void modify(int u,int l,int r,int x,int y) {
	if(l>y||r<x) return ;
	if(l>=x&&r<=y) {
		zx(u);
		return ;
	}
	int mid=(l+r)/2;
	psdn(u);
	modify((u<<1),l,mid,x,y);
	modify((u<<1|1),mid+1,r,x,y);
	psup(u);
}
LL query(int u,int l,int r,int x,int y) {
	if(l>y||r<x) return inf;
	if(l>=x&&r<=y) return tr[u].a;
	int mid=(l+r)/2;
	psdn(u);
	return min(query((u<<1),l,mid,x,y),query((u<<1|1),mid+1,r,x,y));
}
int main () {
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&n);
		for(int i=1;i<=n;++i) {
			scanf("%d",&a[i]);
			e[i].clear();
		}
		int q;
		scanf("%d",&q);
		for(int i=1;i<=q;++i) {
			int l,r;
			scanf("%d%d",&l,&r);
			e[r].push_back(l);
		}
		build(1,0,n);
		update(1,0,n,0,0);
		for(int i=1;i<=n;++i) {
			LL xi=query(1,0,n,0,i-1);
			for(auto t:e[i]) {
				modify(1,0,n,0,t-1);
			}
			update(1,0,n,i,xi+a[i]);
		}
		printf("%lld\n",query(1,0,n,0,n));
	}
	return 0;
}

\(C\)

直接贪心即可，排个序，从大往小选。

\(D\)

贪心，记 \(c_i=b_i-a_i\) 那么我们把 \(a\) 数组按 \(c\) 排序，然后能尽量选就选，然后判一下情况即可。

点击查看代码

#include<bits/stdc++.h>
typedef long long LL;

using namespace std;
const int MAXN=5e5+10;
int T,n,m;
struct ddl {
	int a,b,c;
}a[MAXN];
bool cmp(ddl a,ddl b) {
	return a.c>b.c;
}
int main () {
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&n,&m);
		LL sum=0;
		for(int i=1;i<=n;++i) {
			scanf("%d%d",&a[i].a,&a[i].b);
			a[i].c=a[i].b-a[i].a;
			sum+=a[i].a;
		}
		if(n==1) {
			printf("%d\n",a[1].b);
			continue;
		}
		sort(a+1,a+1+n,cmp);
		int p=m-n,ll=min(p,n),lt=0;
		for(int i=1;i<=ll;++i) {
			if(a[i].c<0) break;
			sum+=a[i].c; lt=i;
		}
		if(lt==n-1) {
			sum+=a[n].c;
			sum=max(sum,sum-a[n].c-a[n-1].c);
		}
		printf("%lld\n",sum);
	}
	return 0;
}

\(E\)

给你 \(n\) 个串，选 \(k\) 个串，使其中两两 \(lcp\) 的最大最小。

一开始我以为选数一定是相邻的最优，然后想用 \(sa\) 乱搞，实则不然，你选不相邻的可以使得可能的最大小一点。

看到最大最小我们可以考虑二分我们最后的答案的字典序，就是把所有串排序，然后答案只可能是他们的前缀，然后二分这些前缀就可以了。

每次能选就选，因为肯定是当前穿串与上一个串越远越好，然后这题就做完了。

不过还有一个细节，怎么排序，可以用字典树排序，当然你用 \(sa\) 也不是不行。

\(I\)

二分 \(mex\) ，然后排序，时间复杂度 \(O(nm\log^2(nm))\)

实际上不需要排序，可以直接枚举所有小于等于 \(mid\) 的值，这样得到的数其实已经拍好序了。

时间复杂度 \(O(nm\log (nm))\)

我实现的没有那么精细，写了 \(\log^2\) 的。

点击查看代码

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN=1e6+10;
int T,n,m;
int a[MAXN],b[MAXN];
struct ddl {
	int x,y;
}d[MAXN];
int cnt;
bool cmp(ddl a,ddl b) {
	if(a.x!=b.x) return a.x<b.x;
	return a.y<b.y;
}
bool check(int x) {
	cnt=0;
	for(int i=0;i<=x;++i) {
		d[++cnt].x=a[i];
		d[cnt].y=b[i];
	}
	sort(d+1,d+1+cnt,cmp);
	int y=0;
	for(int i=1;i<=cnt;++i) {
		if(y>d[i].y) return false;
		y=d[i].y;
	}
	return true;
}
int erfind() {
	int l=0,r=n*m,mid;
	while(l+1<r) {
		mid=(l+r)/2;
		if(check(mid)) l=mid;
		else r=mid;
	}
	return l;
}
int main () {
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=m;++j) {
				int x;
				scanf("%d",&x);
				a[x]=i; b[x]=j;
			}
		}
		printf("%d\n",erfind()+1);
	}
	return 0;
}