队伍配置：
和我这个菜鸡。
膜拜另外两个大佬
赛况：
\(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;
}
\(K\)
暴力 \(dfs\) 即可。
标签：Provincial,lyq,Contest,int,Programming,然后,gsc,MAXN,include From： https://www.cnblogs.com/ddl1no2home/p/17705737.html