526互联

AtCoder Grand Contest 032

发布时间 2023-09-27 19:00:14作者: Zhou_JK

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\) 的看做连了红色的边，那么图一定是下面这样子的：

AGC032E1.png

AGC032E2.png

暴力枚举分界点计算是 \(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

咕咕咕。