A：倒序考虑，每次删除最后一个合法数即可，正确性显然。好久没有atcoder比赛我又忘了评测机并没有define online_judge白交了一发。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 110
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,a[N],ans[N];
signed main()
{
n=read();
for (int i=1;i<=n;i++) a[i]=read();
for (int i=n;i>=1;i--)
for (int j=i;j>=1;j--)
if (a[j]==j)
{
for (int k=j;k<i;k++) a[k]=a[k+1];
ans[i]=j;
break;
}
for (int i=1;i<=n;i++) if (!ans[i]) {cout<<-1;return 0;}
for (int i=1;i<=n;i++) cout<<ans[i]<<endl;
return 0;
//NOTICE LONG LONG!!!!!
}
B：容易发现当n%4==0时，可以将图划分成一个二分图，使其两边和相等，然后中间所有边都连上即可。类似的可以发现，只要将图划分成若干和相同的集合即可。那么根据n的奇偶性讨论一下就好了，偶数时小的和大的两两匹配，奇数时把n单独列为一个集合同样两两匹配。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define N 110
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n;
vector<int> a[N];
signed main()
{
n=read();
int s=n*(n+1)/2;
if (n%2==0) for (int i=1;i<=n/2;i++) a[i].push_back(i),a[i].push_back(n-i+1);
if (n%2==1)
{
for (int i=1;i<=n/2;i++) a[i].push_back(i),a[i].push_back(n-i);
a[(n+1)/2].push_back(n);
}
int ans=0;
for (int i=1;i<=(n+1)/2;i++)
for (int j=i+1;j<=(n+1)/2;j++)
if (i!=j) ans+=a[i].size()*a[j].size();
cout<<ans<<endl;
for (int i=1;i<=(n+1)/2;i++)
for (int j=i+1;j<=(n+1)/2;j++)
if (i!=j)
for (int x=0;x<a[i].size();x++)
for (int y=0;y<a[j].size();y++)
cout<<a[i][x]<<' '<<a[j][y]<<endl;
return 0;
//NOTICE LONG LONG!!!!!
}
C：首先显然必须得存在欧拉回路。那么即要把跑出来的欧拉回路拆成三个回路。显然在欧拉回路所经过的点序列中，找到一个首尾点均相同的段抽出来，就是一个回路。那么检查序列中是否有点出现三次或以上，若有显然有解；否则检查出现两次的点，这样的点需要有两个或以上，如果其中两个点能构成不相交的段则有解。注意到若有至少三个点一定有解，稍微讨论一下即可证明。那么只需要考虑有两个点的情况，判一下是否相交。实际上并不需要跑欧拉回路，通过度数讨论一下即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 100010
#define id(i) (((i)+1)/2)
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,m,p[N],degree[N],cnt[N],t,stk[N<<1],top,tot;
struct data{int to,nxt;
}edge[N<<1];
bool flag[N];
void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
void dfs(int k,int t)
{
if (k==t) {tot++;return;}
flag[k]=1;
for (int i=p[k];i;i=edge[i].nxt)
if (!flag[edge[i].to]||edge[i].to==t)
{
dfs(edge[i].to,t);
}
}
signed main()
{
n=read(),m=read();
for (int i=1;i<=m;i++)
{
int x=read(),y=read();
degree[x]++,degree[y]++;
addedge(x,y),addedge(y,x);
}
for (int i=1;i<=n;i++) if (degree[i]&1) {cout<<"No";return 0;}
for (int i=1;i<=n;i++) if (degree[i]>=6) {cout<<"Yes";return 0;}
int cnt=0;
for (int i=1;i<=n;i++) if (degree[i]>=4) {cnt++;}
if (cnt>=3) {cout<<"Yes";return 0;}
if (cnt<=1) {cout<<"No";return 0;}
int x=0,y=0;for (int i=1;i<=n;i++) if (degree[i]>=4) if (x) y=i;else x=i;
dfs(x,y);
if (tot==2) cout<<"Yes";else cout<<"No";
return 0;
//NOTICE LONG LONG!!!!!
}
D：将移动序列看成移动一个数，进一步看成将一个数放到一个实数位置上，代价根据是向左还是向右还是不动不同。这样dp就很显然了，即将所有数从小到大排序（相同的数按初始位置排序）后，设f[i][j]为第i个数放在第j段时，前i个数的最小代价，转移显然。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 5010
#define inf 1000000000000000ll
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,A,B;
struct data
{
int x,y;
bool operator <(const data&a) const
{
return x<a.x||x==a.x&&y<a.y;
}
}a[N];
ll f[N][N<<1];
signed main()
{
n=read(),A=read(),B=read();
for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=i;
sort(a+1,a+n+1);
for (int i=1;i<=n;i++)
{
ll s=inf;
for (int j=0;j<=n*2;j++)
{
s=min(s,f[i-1][j]);
if (j&1)
{
f[i][j]=s+((j+1>>1)==a[i].y?0:((j+1>>1)<a[i].y?B:A));
}
else
{
f[i][j]=s+(((j>>1)<a[i].y?B:A));
}
}
}
ll ans=inf;
for (int i=0;i<=n*2;i++) ans=min(ans,f[n][i]);
cout<<ans;
return 0;
//NOTICE LONG LONG!!!!!
}
E：如果不考虑%m的话显然小的和大的配对。可以证明若将需要减m的对和不需要减m的对分成两组，一定存在最优方案使得不需要减m的是一段前缀而需要减m的是一段后缀，并且其分别满足上述贪心策略。具体讨论几种情况可以发现交换不会更劣。显然前后缀的分界点确定则方案确定，注意到分界点移动时两边答案单调移动且方向相同，那么二分找到最靠前的合法分界点（即满足上述条件）即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 200010
#define inf 2000000001
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,m,a[N],ans;
int calc_head(int k)
{
int s=0;
for (int i=1;i<=k/2;i++)
{
if (a[i]+a[k-i+1]>=m) return inf;
s=max(s,a[i]+a[k-i+1]);
}
return s;
}
int calc_tail(int k)
{
int s=0;
for (int i=k;i<=n;i++)
{
if (a[i]+a[n-(i-k)]<m) return inf;
s=max(s,a[i]+a[n-(i-k)]-m);
}
return s;
}
signed main()
{
n=read()*2,m=read();
for (int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+n+1);
int x;
int L=0,R=n/2;
while (L<=R)
{
int mid=L+R>>1;
if (calc_tail(mid*2+1)==inf) L=mid+1;
else R=mid-1,x=mid*2;
}
cout<<max(calc_head(x),calc_tail(x+1));
return 0;
//NOTICE LONG LONG!!!!!
}
F：咕
result：rank 177 rating +46