A - Limited Insertion
首先判断无解的情况
序列必须满足$num_{\leq a[i]} \geq a[i]$
之后每次从后面找到一个最靠后而且当前位置可以放置的，即前面正好放了$a_i-1$个数
Code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//******head by yjjr******
const int maxn=106;
int a[maxn],n,num[maxn];
bool vis[maxn];
int main(){
n=read();
rep(i,1,n)a[i]=read();
rep(i,1,n){
int num=0;
rep(j,1,i-1)if(a[j]<=a[i])num++;
if(num+1<a[i]){puts("-1");return 0;}
}
rep(i,1,n){
num[0]=0;
rep(j,1,n)num[j]=num[j-1]+vis[j];
dep(j,n,1)
if(!vis[j]&&num[j-1]+1==a[j]){
vis[j]=1;
cout<<a[j]<<endl;
break;
}
}
return 0;
}
B - Balanced Neighbors
分为奇偶讨论
如果为$N$为偶数，那么分为$N/2$组，$(1,n),(2,n-1)…$
如果为奇数的话，那么额外处理$N$为单独的一组，$(1,n-1),(2,n-2),…,(n,n)$
之后将相邻的两组之间连边即可
Code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//******head by yjjr******
const int maxn=106;
int n,num=0;
struct node{int x,y;}a[maxn],ans[maxn<<4];
void Wri(int X,int Y){
ans[++num]=(node){a[X].x,a[Y].x};
ans[++num]=(node){a[X].x,a[Y].y};
ans[++num]=(node){a[X].y,a[Y].x};
ans[++num]=(node){a[X].y,a[Y].y};
}
int main(){
n=read();
if(n%2==1){
rep(i,1,(n-1)/2)a[i]=(node){i,n-i};
a[n/2+1]=(node){n,n};
//rep(i,1,n/2+1)cout<<a[i].x<<' '<<a[i].y<<endl;
rep(i,1,n/2-1)Wri(i,i+1);
ans[++num]=(node){a[n/2].x,a[n/2+1].x};
ans[++num]=(node){a[n/2].y,a[n/2+1].x};
if(n/2+1>2)ans[++num]=(node){a[1].x,a[n/2+1].x},ans[++num]=(node){a[1].y,a[n/2+1].x};
}else{
rep(i,1,n/2)a[i]=(node){i,n-i+1};
rep(i,1,n/2-1)Wri(i,i+1);
if(n/2>2)Wri(n/2,1);
}
printf("%d\n",num);
rep(i,1,num)printf("%d %d\n",ans[i].x,ans[i].y);
return 0;
}
C - Three Circuits
分类讨论：
- 如果存在点的度数为奇数，那么不存在欧拉回路，输出
No - 如果存在大于$4$的度数的点，那么一定存在至少三条欧拉回路，输出
Yes - 如果存在不小于三个度数恰好等于$4$的点，那么输出
Yes - 如果存在小于$2$个度数等于$4$的点，那么输出
No - 如果恰好存在$2$个度数等于$4$的点，那么需要详细进行判断。将两点缩点后，如果两点之间只有$2$条路径，那么输出
Yes，否则为No，图片可以参见官方题解文档
Code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//******head by yjjr******
const int maxn=2e5+6;
struct edge{int to,next;}e[maxn<<1];
int now1=-1,now2=-1,tot=0,num=0,n,m,d[maxn],last[maxn],cnt=0;
void insert(int u,int v){e[++cnt]=(edge){v,last[u]};last[u]=cnt;}
void dfs(int x,int fr){
reg(i,x){
if(e[i].to==fr)continue;
if(d[e[i].to]==2)dfs(e[i].to,x);
else if(e[i].to==now1)tot+=2;
else if(e[i].to==now2)tot+=1;
}
}
int main(){
n=read(),m=read();
rep(i,1,m){
int u=read(),v=read();
d[u]++,d[v]++;
insert(u,v);insert(v,u);
}
rep(i,1,n)if(d[i]&1){puts("No");return 0;}
rep(i,1,n)if(d[i]>4){puts("Yes");return 0;}
rep(i,1,n)if(d[i]==4)num++;
if(num==0){puts("No");return 0;}
else if(num>2){puts("Yes");return 0;}
else if(num==1){puts("No");return 0;}
else{
rep(i,1,n)
if(d[i]==4){
if(now1==-1)now1=i;else now2=i;
}
dfs(now1,-1);
if(tot>5){puts("Yes");return 0;}
else{puts("No");return 0;}
}
return 0;
}
D - Rotation Sort
将每个点的坐标映射到实数轴上
根据位置进行DP
$ans=\sum A(a_i<b_i) + B(a_i>b_i)$
设状态$f[i][j]$表示处理完$i$，上一个不操作位置为$j$的最小代价
原本一开始想法是区间DP，但貌似出了些问题（不是最优解？？雾）
Code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//******head by yjjr******
const int maxn=5e3+6;
int n,p[maxn];
ll f[maxn][maxn],A,B;
int main(){
n=read(),A=read(),B=read();
rep(i,1,n){int x=read();p[x]=i;}
mem(f,0x20);
f[0][0]=0;
rep(i,1,n+1)rep(j,0,i)
if(p[i]>p[j]){
f[i][i]=min(f[i][i],f[i-1][j]);
f[i][j]=min(f[i][j],f[i-1][j]+B);
}else f[i][j]=min(f[i][j],f[i-1][j]+A);
cout<<*min_element(f[n],f[n]+n+1)<<endl;
return 0;
}
E - Modulo Pairing
将$a_i$升序排列，存在一个分界线$x(0\leq x\leq 2n)$
- 对于$1<i<x,a[i+1]+a[i]<M$
- 对于$x\leq i<2n, a[i]+a[i+1]\geq M$
- 按照$(x-1,x),(x-2,x+1)…$匹配可以得到最优解
可以二分寻找答案
结论题
证明参见官方题解
Code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//******head by yjjr******
const int maxn=2e5+6;
ll a[maxn],n,m,ans=1e18;
inline bool check(int x){
ll re=0;
for(int l=x+1,r=n;l<r;l++,r--){
if(a[l]+a[r]<m)return 0;
re=max(re,a[l]+a[r]-m);
}
for(int l=1,r=x;l<r;l++,r--)re=max(re,a[l]+a[r]);
ans=min(ans,re);
return 1;
}
int main(){
n=read(),m=read();
n=n*2;
rep(i,1,n)a[i]=read();
sort(a+1,a+1+n);
int l=0,r=n;
while(l<r){
int mid=(l+r)>>1;
if((n-mid)&1)mid--;
if(check(mid))r=mid;else l=mid+2;
}
check(l);
cout<<ans<<endl;
return 0;
}
