526互联

AtCoder Regular Contest 103

发布时间 2023-09-27 19:10:28作者: Zhou_JK

C - ////

如果奇数和偶数出现的颜色的最大值相同一边取最大值和一边取次大值，否则两边都选最大值即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int n,m;
int v[N];
int c[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&v[i]);
	m=*max_element(v+1,v+n+1);
	for(int i=1;i<=n;i+=2)
		c[v[i]]++;
	pair<int,int>fmx={0,0},fsmx={0,0};
	for(int i=1;i<=m;i++)
		if(make_pair(c[i],i)>fmx) fsmx=fmx,fmx={c[i],i};
		else if(make_pair(c[i],i)>fsmx) fsmx={c[i],i};
	for(int i=1;i<=n;i+=2)
		c[v[i]]=0;
	for(int i=2;i<=n;i+=2)
		c[v[i]]++;
	pair<int,int>smx={0,0},ssmx={0,0};
	for(int i=1;i<=m;i++)
		if(make_pair(c[i],i)>smx) ssmx=smx,smx={c[i],i};
		else if(make_pair(c[i],i)>ssmx) ssmx={c[i],i};
	for(int i=2;i<=n;i+=2)
		c[v[i]]=0;
	if(fmx.second!=smx.second) printf("%d\n",n-fmx.first-smx.first);
	else printf("%d\n",n-max(fsmx.first+smx.first,fmx.first+ssmx.first));
	return 0;
}

D - Robot Arms

可以发现将一个操作更改方向 \(x+y\) 的奇偶性是不会变的，所以如果 \(x_i+y_i\) 的奇偶性不同的话就不能满足条件。

然后考虑 \(x+y\) 为奇数的情况，一种构造方式就是从大到小考虑每个机械臂。对于当前的机械臂拜访在。若有多个则可以随便摆放。不难发现，这样一定能构造出解。

\(x+y\) 的偶数的情况会出一点小偏差，先将人移动到 \((1,0)\) 再操作即可。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=1005;
int n;
int x[N],y[N];
vector<int>d;
int main()
{
	scanf("%d",&n);
	int c0=0,c1=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		if((x[i]+y[i])%2==0) c0++;
		else c1++;
	}
	if(c0&&c1)
	{
		printf("-1");
		return 0;
	}
	if(c0) d.emplace_back(1);
	for(int i=30;i>=0;i--)
		d.emplace_back(1<<i);
	int m=d.size();
	printf("%d\n",m);
	for(int c:d)
		printf("%d ",c);
	printf("\n");
	for(int i=1;i<=n;i++)
	{
		int nowx=x[i],nowy=y[i];
		for(int c:d)
			if(labs(nowx)>labs(nowy))
			{
				if(nowx>=0) nowx-=c,printf("R");
				else nowx+=c,printf("L");
			}
			else
			{
				if(nowy>=0) nowy-=c,printf("U");
				else nowy+=c,printf("D");
			}
		printf("\n");
	}
	return 0;
}

E - Tr/ee

可以发现，合法的树一定要满足 \(s_1=1,s_n=0\)，且 \(s_i=s_{n-i}\)。

考虑当前已经构造出一棵 \(i\) 个点的树，满足了 \(s_{1\sim i-1}\) 的条件，且 \(s_i=1\)。令下一个 \(1\) 的位置为 \(j\)，我们可以新建一个根，然后将原来 \(i\) 个点的树挂上去，这样就满足了 \(s_i=1\) 的条件，然后再在新根上挂上 \(j-i-1\) 个一个点的儿子，可以发现这样构造是正确的。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100005;
int n;
char s[N];
void add_edge(int u,int v)
{
	printf("%d %d\n",u,v);
	return;
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	if(s[1]=='0'||s[n]=='1')
	{
		printf("-1");
		return 0;
	}
	for(int i=2;i<=n-1;i++)
		if(s[i]!=s[n-i])
		{
			printf("-1");
			return 0;
		}
	int rt=1,tot=1;
	for(int i=1,j=1;i<=n-1;i=j)
	{
		j=i+1;
		while(j<=n-1&&s[j]=='0') j++;
		int pre=rt;
		rt=++tot;
		add_edge(rt,pre);
		for(int k=1;k<=j-i-1;k++)
			add_edge(rt,++tot);
	}
	return 0;
}

F - Distance Sums

显然 \(d_i\) 最小的点为重心，\(d_i\) 最大的点为叶子。

考虑不妨以重心为根，从叶子节点往上构造，注意到如果图中存在一条边 \((u,v)\)（\(u\) 为 \(v\) 的父亲），则有 \(d_u=d_v-(n-siz_v)+siz_v\)，这样一直往上构造到根为止。最后再判一下就好了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N=100005;
int n;
int id[N]; 
long long d[N],dis[N];
int siz[N];
unordered_map<long long,int>vis;
vector<pair<int,int>>G;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&d[i]);
	for(int i=1;i<=n;i++)
		id[i]=i,vis[d[i]]=i,siz[i]=1;
	sort(id+1,id+n+1,[=](const int &x,const int &y){return d[x]>d[y];});
	for(int i=1;i<=n-1;i++) 
	{
		long long nd=d[id[i]]-(n-siz[id[i]])+siz[id[i]];
		if(!vis[nd])
		{
			printf("-1");
			return 0;
		}
		int fa=vis[nd];
		G.emplace_back(id[i],fa);
		siz[fa]+=siz[id[i]];
		dis[fa]+=dis[id[i]]+siz[id[i]];
	}
	if(d[id[n]]!=dis[id[n]])
	{
		printf("-1");
		return 0;
	}
	for(auto [u,v]:G)
		printf("%d %d\n",u,v);
	return 0;
}