Codeforces Round 624 (Div. 3) 题解

还是div. 3比较适合我这种菜，不过最后一道题一个细节没调出来真的可惜了。

A. Add Odd or Subtract Even

题目链接

题目原文

题目大意

给出 $a$ 和 $b$ 两个正整数。每一次操作，你可以将 $a$ 做以下两种操作之一：

• 任选一个正奇数 $x$ ，将 $a$ 加上 $x$ 。
• 任选一个正偶数 $y$ ，将 $a$ 减去 $y$ 。

问至少操作多少次，可以使 $a$ 和 $b$ 的值相等。

思路

容易发现，有以下几种情况：

1. $a==b$ ，答案为 $0$ 。
2. $a<b$ 。如果 $a$ 和 $b$ 的差值是奇数，那么直接加上一个正奇数就可，答案为 $1$ ；如果差值是偶数，那么答案为 $2$ ，加两次正奇数或者加一次正奇数再减一次正偶数。
3. $a>b$ 。与2.同理且相反。

代码

#include < cstdio >
#include < cstring >
#include < algorithm >
using namespace std;
const int maxn=200005;

int main()
{
	long long T,x,y;
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld",&x,&y);
		long long ans;
		if(x==y) ans=0;
  		else if(x < y)
  		{
			long long temp=y-x;
			if(temp&1) ans=1;
			else ans=2;
		}
		else
		{
			long long temp=x-y;
			if(temp&1) ans=2;
			else ans=1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

B. WeirdSort

题目链接

题目原文

题目大意

给出 $n$ 个数和 $m$ 个位置 $pos_i$ ，可以让 $pos_i$ 和 $pos_i+1$ 交换任意次位置，求是否能通过交换，使这 $n$ 个数以非递减顺序排列。

思路

最开始还没有思路，把C题做了回来一想，因为冒泡排序的思想，所以同一块（可以交换的连通块）中的顺序是任意的，所以直接对每一内部可以互相交换的块内部排序，最后验证序列是否非递减即可。

代码

#include < cstdio >
#include < cstring >
#include < algorithm >
using namespace std;
const int maxn=105;
int T,n,m,p[maxn],a[maxn];
bool vis[maxn];
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		memset(vis,false,sizeof(vis));
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1,x;i<=m;i++)
		{
			scanf("%d",&x);
			vis[x]=true;
		}
		for(int i=1;i<=n;i++)
		{
			int s=i,t=i;
			while(vis[t]) t++;
			sort(a+s,a+t+1);
			i=t;
		}
		bool flag=false;
		for(int i=2;i<=n;i++)
		{
			if(a[i]<a[i-1]) flag=true;
		}
		if(flag) printf("NO\n");
		else printf("YES\n");
	}
	return 0;
}

C. Perform the Combo

题目链接

题目原文

题目大意

给出一个字符串，要求枚举一遍该字符串，再给出 $m$ 个错误操作，每次遇到错误操作就会从头开始重新枚举。求最后执行完 $m$ 个错误操作后，26个小写字母每个都被枚举了多少遍。

思路

直接前缀和，每次 $O(1)$ 查询，时间复杂度 $O(t\cdot max(n,m)\cdot26)$ 。

代码

#include < cstdio >
#include < cstring >
#include < algorithm >
using namespace std;
const int maxn=200005;
int cnt[maxn][26];
char s[maxn];
int p[maxn],n,m,T;
long long ans[26];
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		scanf("%s",s+1);
		for(int i=1;i<=n;i++)
			for(int j=0;j<26;j++) cnt[i][j]=0;
		for(int i=1;i<=n;i++) cnt[i][s[i]-'a']++;
		for(int i=1;i<=n;i++)
			for(int j=0;j<26;j++) cnt[i][j]+=cnt[i-1][j];
		memset(ans,0,sizeof(ans));
		for(int i=1,x;i<=m;i++)
		{
			scanf("%d",&x);
			for(int j=0;j<26;j++) ans[j]+=cnt[x][j];
		}
		for(int i=0;i<26;i++) ans[i]+=cnt[n][i];
		for(int i=0;i<26;i++) printf("%lld ",ans[i]);
		printf("\n");
	}
	return 0;
}

D. Three Integers

题目链接

题目原文

题目大意

给出 $A$ , $B$ , $C$ 三个正整数，每次可以将这三个数任意一个数加上 $1$ 或者减去 $1$ ，求最少操作多少次，能使 $C$ 能被 $B$ 整除， $B$ 能被 $A$ 整除。

思路

因为数据范围是 $10000$ ，直接枚举 $A$ ，再枚举 $B$ ，$C$ 就不要枚举了，直接除以枚举的 $B$ ，直接取最近的值就好。

代码

#include < cstdio >
#include < cstring >
#include < algorithm >
using namespace std;
const int maxn=200005;
int main()
{
	#ifdef lemon
	freopen("D.txt","r",stdin);
	#endif
	long long T,a,b,c;
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld%lld",&a,&b,&c);
		long long ans=1e18,ansa,ansb,ansc;
		for(long long i=1;i<=10000;i++)
		{
			for(long long j=1;j<=10000;j++)
			{
				if(i*j>50000) break;
				long long temp=0,tempa,tempb,tempc;
				temp+=abs(a-i)+abs(b-i*j);
				long long p=c/(i*j);
				tempa=i;tempb=i*j;
				if(p==0)
				{
					temp+=abs(c-i*j);
					tempc=i*j;
				}
				else
				{
					if(abs(c-i*j*p)<abs(c-i*j*(p+1)))
					{
						temp+=abs(c-i*j*p);
						tempc=i*j*p;
					}
					else
					{
						temp+=abs(c-i*j*(p+1));
						tempc=i*j*(p+1);
					}
				}
				if(temp &lt; ans)
				{
					ans=temp;
					ansa=tempa;
					ansb=tempb;
					ansc=tempc;
				}
			}
		}
		printf("%lld\n%lld %lld %lld\n",ans,ansa,ansb,ansc);
	}
	return 0;
}

E. Construct the Binary Tree

题目链接

题目原文

题目大意

给出 $n$ 和 $d$ ，求问存不存在 $n$ 个点的二叉树，其所有节点的深度之和为 $d$ ，如果存在，需要输出每一个节点的父节点（根节点为 $0$ ）。

思路

先把 $n$ 个点连成一条链，再不断地从链尾取下点按深度递增的顺序加在某些点后即可。

代码

#include < cstdio >
#include < cstring >
#include < algorithm >
using namespace std;
const int maxn=5005;
int T,n,d;
int point[maxn][maxn],fa[maxn],cnt[maxn];
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&d);
		for(int i=0;i < n;i++)
		{
			fa[i+1]=i;
			cnt[i]=1;
			point[i][0]=i+1;
		}
		int res=n*(n-1)/2-d;
		if(res<0)
		{
			printf("NO\n");
			continue;
		}
		int depth=1;
		for(int i=n-1;i;i--)
		{
			int delta=min(i-depth,res);
			res-=delta;
			int pos=i-delta;
			fa[i+1]=point[pos-1][cnt[pos]/2];
			point[pos][cnt[pos]++]=i+1;
			if(cnt[pos]>=(1 &lt; &lt; depth)) depth++;
			if(!res) break;
		}
		if(res!=0)
		{
			printf("NO\n");
			continue;
		}
		printf("YES\n");
		for(int i=2;i<=n;i++) printf("%d ",fa[i]);
	}
	return 0;
}

F. Moving Points

题目链接

题目原文

题目大意

在 $X$ 轴上有 $n$ 个点，每个点有一个初始坐标 $x_i$ 和一个速度 $v_i$ ，求问每每两个点对之间可能达到的最近距离之和，时间可以为正为负为零且不一定为整数。

思路

感觉这道题的变形都有好多了，看完题就知道肯定是和时间没有关系的。

所以对于任意两个点 $i$ , $j$ ，假使 $x_i<x_j$ 分两种情况讨论：

• $v_i\leq v_j$ ，那么最近的时候就是初始位置时，对答案贡献为 $x_j-x_i$ 。
• $v_i>v_j$ ，那么一定会相遇，对答案贡献为 $0$ 。

所以我们先对初始位置从小到大排序，再对速度离散化，用树状数组或者线段树维护一个前缀和，就好了。我没调出来的原因是计数的时候乘错地方了（后悔死）。

代码

#include < cstdio >
#include < cstring >
#include < algorithm >
#define lowbit(x) (x&(-x))
using namespace std;
const int maxn=200005;
struct node
{
	int x,v;
} a[maxn];
bool cmp(node a,node b) {return a.x<b.x;}
int cnt[maxn],n,b[maxn];
long long val[maxn];
void add(int x,int v)
{
	for(int i=x;i<=n;i+=lowbit(i))
	{
		cnt[i]++;
		val[i]+=(long long)v;
	}
}
long long get(int x)
{
	long long temp=0;
	for(int i=x;i;i-=lowbit(i)) temp+=val[i];
	return temp;
}
long long getc(int x)
{
	long long temp=0;
	for(int i=x;i;i-=lowbit(i)) temp+=cnt[i];
	return temp;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].x);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].v);
		b[i]=a[i].v;
	}
	sort(b+1,b+n+1);
	int cnt=unique(b+1,b+n+1)-(b+1);
	for(int i=1;i<=n;i++) a[i].v=lower_bound(b+1,b+cnt+1,a[i].v)-b;
	sort(a+1,a+n+1,cmp);
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=a[i].x*getc(a[i].v)-get(a[i].v);
		add(a[i].v,a[i].x);
	}
	printf("%lld\n",ans);
	return 0;
}