这场比赛让我上橙了。
前三题都是大水题，不说了。
第四题有点难想，即使想到了也不能保证是对的。（所以说下面D的做法可能是错的）
E的难度是 $2300$，但是感觉很简单啊？？？说好的歪果仁擅长构造的呢？？？
这次超常发挥过头了，下次肯定要掉了QwQ。
A
水题。不过分类讨论有点难受，结果8min才交，被别人甩了一大截。
时间复杂度 $O(1)$。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=,f=;
while(ch<'' || ch>'') f|=ch=='-',ch=getchar();
while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();
return f?-x:x;
}
int a,b,c;
int main(){
a=read();b=read();c=read();
ll ans=*c;
if(a>b) ans+=*b+;
else if(a<b) ans+=*a+;
else ans+=*a;
cout<<ans;
}
B
水题。枚举在前一种航线中删几个，明显是要删最小的几个。然后二分出此时在第二种航线中最早能乘坐哪个，再在这个基础上删几个。
注意特判第一种航线能被删完的情况。
时间复杂度 $O(n\log n)$。（实际上可以做到 $O(n)$，但是会稍难打，作为B题就不必要了）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=,f=;
while(ch<'' || ch>'') f|=ch=='-',ch=getchar();
while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();
return f?-x:x;
}
int n,m,ta,tb,k,a[maxn],b[maxn],ans;
int main(){
n=read();m=read();ta=read();tb=read();k=read();
if(k>=min(n,m)) return puts("-1"),;
FOR(i,,n) a[i]=read()+ta;
FOR(i,,m) b[i]=read();
sort(a+,a+n+);sort(b+,b+m+);
FOR(i,,k+){
int p=lower_bound(b+,b+m+,a[i])-b;
if(p+k-i+>m) return puts("-1"),;
ans=max(ans,b[p+k-i+]+tb);
}
printf("%d\n",ans);
}
C
水题。简单构造题。（以下的做法是能卡到 $5n$ 而且又臭又长的蒟蒻做法，应该会有更简洁或更优秀的做法）
每次考虑如何把数 $i$ 通过不超过 $5$ 次交换移到位置 $i$。
- 如果已经在，不用管。$0$ 次。
- 如果能直接交换（距离 $\ge\frac{n}{2}$），直接交换。$1$ 次。
- 如果 $i\le\frac{n}{2}$ 且 $at_i\le\frac{n}{2}$，用 $p_n$ 作为中介变量。$3$ 次。
- 如果 $i>\frac{n}{2}$ 且 $at_i>\frac{n}{2}$，用 $p_1$ 作为中介变量。$3$ 次。
- 如果都不满足，那么一个 $\le\frac{n}{2}$，一个 $>\frac{n}{2}$。把左边的与 $p_n$ 交换，右边的与 $p_1$ 交换。然后就能把 $p_1,p_n$ 交换。最后把左边的与 $p_n$ 交换，右边的与 $p_1$ 交换。$5$ 次。
（如果不能理解，建议手动模拟一下）
时间复杂度 $O(n)$。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=,f=;
while(ch<'' || ch>'') f|=ch=='-',ch=getchar();
while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();
return f?-x:x;
}
int n,p[maxn],id[maxn],m,a[maxn*],b[maxn*];
int tp(int x){return x<=n/?:;}
int main(){
n=read();
FOR(i,,n) id[p[i]=read()]=i;
FOR(i,,n){
if(p[i]==i) continue;
int x=i,y=id[i],t1=tp(x),t2=tp(y);
if(abs(x-y)*>=n){
m++;
a[m]=x;b[m]=y;
}
else if(t1==t2){
int ot=t1?:n;
m++;
a[m]=x;b[m]=ot;
m++;
a[m]=y;b[m]=ot;
m++;
a[m]=x;b[m]=ot;
}
else{
if(t1>t2) swap(x,y),swap(t1,t2);
m++;
a[m]=x;b[m]=n;
m++;
a[m]=;b[m]=y;
m++;
a[m]=;b[m]=n;
m++;
a[m]=;b[m]=y;
m++;
a[m]=x;b[m]=n;
}
swap(p[x],p[y]);
id[p[x]]=x;
id[p[y]]=y;
}
printf("%d\n",m);
FOR(i,,m) printf("%d %d\n",a[i],b[i]);
}
D
分两类讨论，第一种是 $a_1>b_1<a_2>b_2\cdots$，第二种是$%#!*&^@!。
这里以第一种为例。
这里就不会了。然后就按 $b$ 从小到大排序，贪心地选。过了？？？
等官方题解出来我再把这个坑（锅？）补一补吧。
upd：以第一种 $a_i>b_i$ 为例。如果按 $a$ 从小到大排序，那么 $a_{i_2}>a_{i_1}>b_{i_1}$，这是一定合法的。然而按 $b$ 排序就不知道为什么了。
upd2：还是以 $a_i>b_i$ 为例。如果按 $b$ 从小到大排序，那么 $b_{i_1}<b_{i_2}<a_{i_2}$。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=,f=;
while(ch<'' || ch>'') f|=ch=='-',ch=getchar();
while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();
return f?-x:x;
}
struct item{
int a,b,id;
bool operator<(const item &i)const{return b<i.b;}
}t1[maxn],t2[maxn];
int n,m1,m2,a[maxn],b[maxn],al1,ans1[maxn],al2,ans2[maxn];
int main(){
n=read();
FOR(i,,n) a[i]=read(),b[i]=read();
FOR(i,,n) if(a[i]>b[i]) t1[++m1]=(item){a[i],b[i],i};
sort(t1+,t1+m1+);
FOR(i,,m1) if(t1[i].a>t1[ans1[al1]].b) ans1[++al1]=i;
FOR(i,,n) if(a[i]<b[i]) t2[++m2]=(item){a[i],b[i],i};
sort(t2+,t2+m2+);
t2[].b=1e9;
ROF(i,m2,) if(t2[i].a<t2[ans2[al2]].b) ans2[++al2]=i;
if(al1>al2){
printf("%d\n",al1);
FOR(i,,al1) printf("%d ",t1[ans1[i]].id);
}
else{
printf("%d\n",al2);
FOR(i,,al2) printf("%d ",t2[ans2[i]].id);
}
}
E
很简单的构造题，为什么连那么多歪果仁都不会……
首先发现 $0\le 2d\le s_j-s_i$ 等价于 $i$ 和 $j$ 的大小关系不变。以下我们只要在大小不变的条件下构造。
upd：经CDW提醒，这不能直接互推（想象一下 $i$ 与一个更大的 $k$ 移动然后超过了 $j$ 到达 $i'$）。但是如果有解，肯定有一种方案使得最后的大小关系和原来的大小关系一样。如刚刚那个反例，可以先 $j$ 和 $k$ 操作，$j$ 移到 $i'$，然后 $i$ 和 $k$ 操作，$i$ 移到 $j$。
那么就可以把 $s$ 和 $t$ 从小到大排序。
求出每个元素的变化值。（$d_i=s_i-t_i$）如果变化值之和不为 $0$ 则无解。
从小到大枚举变化值。每枚举一个变化值我们就想法把它变为 $0$。
首先，如果 $d_i$ 是负数，由于之前的 $d$ 都是 $0$，所以这个变化值不可能再变大。无解。
否则就找到这后面的第一个负数。可以对这两个数进行操作。
重复以上操作直到 $d_i=0$ 为止。
发现第一个负数的位置不降。可以就用一个指针不停往后推。
时间复杂度 $O(n\log n)$。由于每枚举一个数或者指针往后推都至多用 $1$ 次操作，所以 $m\le 2n$。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
char ch=getchar();ll x=,f=;
while(ch<'' || ch>'') f|=ch=='-',ch=getchar();
while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();
return f?-x:x;
}
struct item{
int s,id;
bool operator<(const item &i)const{return s<i.s;}
}it[maxn];
int n,s[maxn],t[maxn],d[maxn],cur=,m,a[maxn],b[maxn],c[maxn];
ll sum;
int main(){
n=read();
FOR(i,,n) s[i]=read(),it[i]=(item){s[i],i};
FOR(i,,n) t[i]=read();
sort(it+,it+n+);sort(t+,t+n+);
FOR(i,,n) d[i]=t[i]-it[i].s,sum+=d[i];
if(sum) return puts("NO"),;
FOR(i,,n){
if(d[i]<) return puts("NO"),;
while(d[i]){
while(cur<=n && d[cur]>=) cur++;
int x=min(d[i],-d[cur]);
d[i]-=x;d[cur]+=x;
a[++m]=it[i].id;b[m]=it[cur].id;c[m]=x;
}
}
printf("YES\n%d\n",m);
FOR(i,,m) printf("%d %d %d\n",a[i],b[i],c[i]);
}
F,G,H
一个 $2500$，一个$3100$，一个 $3600$（史上第一道 $3600$ 题），完全不可做。以后再来填吧。