A - Limited Insertion
考虑从后往前做，插数变成了删数。可以发现，我们可以删去的只有 \(a_i=i\) 的数，如果有多个肯定删最后面的是最优的，因为这样影响到的数最少。每次扫一遍找出删什么数即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=105;
int n;
int b[N];
int pos[N];
int ans[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
pos[i]=i;
for(int k=n;k>=1;k--)
{
for(int i=n;i>=1;i--)
if(pos[i]==b[i])
{
ans[k]=i;
break;
}
if(!ans[k])
{
printf("-1");
return 0;
}
pos[ans[k]]=-1;
for(int i=ans[k]+1;i<=n;i++)
pos[i]--;
}
for(int i=1;i<=n;i++)
printf("%d\n",b[ans[i]]);
return 0;
}
B - Balanced Neighbors
手玩一下 \(n=3,4,5,6\) 的情况，可以发现：
- 如果 \(n\) 为奇数，可以按照和为 \(\lceil \frac{n}{2}\rceil\) 分组。
- 如果 \(n\) 为偶数，可以按照和为 \(\frac{n}{2}\) 分组。
每组中的点跟其他组中的其他点连边（即没有组中的点没有边相邻）。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n;
int main()
{
scanf("%d",&n);
vector<pair<int,int> >res;
if(n&1)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i<j&&i+j!=n) res.push_back(make_pair(i,j));
}
else
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i<j&&i+j!=n+1) res.push_back(make_pair(i,j));
}
int m=res.size();
printf("%d\n",m);
for(auto [x,y]:res)
printf("%d %d\n",x,y);
return 0;
}
C - Three Circuits
如果有奇数度数的点显然不合法。
如果有度数大于 \(4\) 的点显然合法。
如果度数为 \(4\) 的点的个数小于 \(2\) 个显然不合法，大于 \(2\) 显然合法。
有 \(2\) 个度数为 \(4\) 的点不合法的情况只有两个度数为 \(4\) 同时处在两个环中，否则一定合法。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=100005;
int n,m;
vector<int>G[N];
int in[N];
bool vis[N];
int s,t;
int cnt;
void dfs(int u)
{
vis[u]=true;
for(int v:G[u])
{
if(v==t)
{
cnt++;
continue;
}
if(vis[v]) continue;
dfs(v);
}
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
in[x]++,in[y]++;
}
for(int i=1;i<=n;i++)
if(in[i]&1)
{
printf("No");
return 0;
}
for(int i=1;i<=n;i++)
if(in[i]>4)
{
printf("Yes");
return 0;
}
vector<int>pos;
for(int i=1;i<=n;i++)
if(in[i]==4) pos.push_back(i);
if(pos.size()<2)
{
printf("No");
return 0;
}
if(pos.size()>2)
{
printf("Yes");
return 0;
}
s=pos.front(),t=pos.back();
dfs(s);
if(cnt>=4) printf("No");
else printf("Yes");
return 0;
}
D - Rotation Sort
不妨将操作看做将一个数插到某个位置上，插到前面需要花费 \(B\) 的代价，插到后面需要花费 \(A\) 的代价。
可以发现，一个数最多会被移动一次，否则一定不优。我们可以将点分成移动的和不移动的。不移动的点肯定形成了一个上升的序列。那么就可以 DP 了。
令 \(f_i\) 表示第 \(i\) 数为不移动的数，且前 \(i\) 个数已经为上升序列的最小花费。转移枚举上一个不移动的数 \(j\) 转移即可。
\[f_i=\min_{j< i,a_j< a_i}\left(f_j+A\left(\sum_{j< k< i} [a_k< a_i]\right)+B\left(\sum_{j< k< i} [a_k> a_i]\right)\right)
\]
暴力转移即可，可以用一些神必技巧做到 \(O(n\log n)\)。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=5005;
const long long INF=4557430888798830399;
int n,A,B;
int a[N];
long long dp[N];
int main()
{
scanf("%d%d%d",&n,&A,&B);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(dp,63,sizeof(dp));
dp[0]=0;
a[0]=0;
a[n+1]=n+1;
for(int i=1;i<=n+1;i++)
{
int cnta=0,cntb=0;
for(int j=i-1;j>=0;j--)
if(a[j]<a[i])
{
dp[i]=min(dp[i],dp[j]+1LL*cnta*A+1LL*cntb*B);
cntb++;
}
else if(a[j]>a[i]) cnta++;
}
printf("%lld",dp[n+1]);
return 0;
}
E - Modulo Pairing
可以发现，如果将 \(i,j\) 配对，\(a_i+a_j< M\) 的看做连了蓝色的边，\(a_i+a_j\ge M\) 的看做连了红色的边，那么图一定是下面这样子的：
暴力枚举分界点计算是 \(O(n^2)\) 的，可以发现分界点越左越优，二分合法的左端点即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200005;
int n,m;
int a[N];
bool check(int x)
{
int l=x+1,r=n*2;
while(l<r)
{
if(a[l]+a[r]<m) return false;
l++,r--;
}
return true;
}
int calc(int x)
{
int ans=0;
int l=x+1,r=n*2;
while(l<r)
{
ans=max(ans,a[l]+a[r]-m);
l++,r--;
}
l=1,r=x;
while(l<r)
{
ans=max(ans,a[l]+a[r]);
l++,r--;
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n*2;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+n+1);
int L=0;
int l=0,r=2*n;
while(l<=r)
{
int mid=(l+r)/2;
if(mid&1) mid++;
if(mid>r) break;
if(check(mid)) L=mid,r=mid-2;
else l=mid+2;
}
printf("%d",calc(L));
return 0;
}
F - One Third
咕咕咕。