Codeforces Round #582 (Div. 3) 解析

A. Chips Moving

题意：有一个 $n$ 个数的数列，第 $i$ 个数的位置是 $x_i$ ，有些数可能放在相同的位置。你可以对每个数做以下两种操作：

将第 $i$ 个数向左或向右移动 $2$ 个位置(即用 $x_i-2$ 或 $x_i+2$ 替换当前坐标 $x_i$ )；
将第 $i$ 个数向左或向右移动 $1$ 个位置(即用 $x_i-1$ 或 $x_i+1$ 替换当前坐标 $x_i$ )，花费 $1$ 个硬币。

注意，所有数可以移动到任意整数坐标位置，包括负数和 $0$ 。

你的任务是找到一个最小的花费硬币数，使所有 $n$ 个数移动到同一个位置。

解析：考虑奇偶性，很明显，一个数可以移动到任意同奇偶的位置，花费 $1$ 硬币移动到另外一个奇偶性的位置，所以只用统计开始奇数和偶数位置的数的个数，求最小值即可。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,sum1,sum2;
int x[110];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x[i]);
		if(x[i]&1)
			sum1++;
		else
			sum2++;
	}
	printf("%d",min(sum1,sum2));
	return 0;
}

B. Bad Prices

题意：给你一个 $n$ 个数的序列，如果序列中，一个数的后面有其他数比他小，那么这个数就是不好的数，求序列中不好的数的个数，你要回答 $t$ 个问题。

解析：两种解法，第一种倒序遍历，记录当前已遍历的最小值，如果比遍历到的新数小，那么新数就是一个不好的数，统计加 $1$ ；第二种直接用树状数组求出后面比他小的数的个数，如果非 $0$ ，统计加 $1$ 。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int t,n,a[151010],b[151010],q[151010],tree[151010];
int lowbit(int x)
{
	return x&(-x);
}
void update(int x,int val)
{
	for(int i=x;i<=n;i+=lowbit(i))
		tree[i]+=val;
}
int query(int x)
{
	int sum=0;
	for(int i=x;i;i-=lowbit(i))
		sum+=tree[i];
	return sum;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		int ans=0;
		memset(tree,0,sizeof(tree));
		memset(a,0,sizeof(a));
		scanf("%d",&n);
		int now=0,cnt=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			b[i]=a[i];
		}
		sort(b+1,b+n+1);
		cnt=unique(b+1,b+n+1)-b-1;
		for(int i=1;i<=n;i++)
			q[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
		for(int i=n;i>=1;i--)
		{
			update(q[i],1);
			now=query(q[i]-1);
			if(now)
				ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}

C. Book Reading

题意：有一本 $n$ 页的书，你决定每次读 $m$ 页，你每次把读的最后一页的页码的尾数记录下来相加，求你所相加的和，你要回答 $q$ 个问题。

解析：相加得到的只与尾数相关，且尾数是循环出现的，我们只用预处理 $0\sim 9$ 的尾数循环节的和，直接用 $\frac{n}{m}$ 算出循环次数求出答案即可。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int q;
long long n,m;
int len[10]={1,10,5,10,5,2,5,10,5,10};
int sum[10]={0,45,20,45,20,5,20,45,20,45};
int main()
{
	scanf("%d",&q);
	while(q--)
	{
		long long ans=0,now=0;
		scanf("%lld%lld",&n,&m);
		now=n/m;
		ans=now/len[m%10]*sum[m%10];
		int q=now%len[m%10],r=m%10,s=r;
		for(int i=1;i<=q;i++)
		{
			ans+=s;
			s=(s+r)%10;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

D. Equalizing by Division

题意：有一个 $n$ 个数的序列，你每次可以选择序列中一个数除以 $2$ (向下取整)，询问最少需要操作多少次，使序列中出现 $k$ 个相同的数。

解析：直接把序列内的所有数预处理，用 $vector$ 记录每个数需要操作多少次的到另一个数，然后对 $vector$ 排序，选出前 $k$ 个数，相加他们的次数即可得到最小值。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
int n,k;
int a[201010];
vector<int> s[201010];
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		int x=a[i];
		s[x].push_back(0);
		for(int j=1;x;j++)
		{
			x/=2;
			s[x].push_back(j);
		}
	}
	for(int i=0;i<=2e5;i++)
		sort(s[i].begin(),s[i].end());
	int ans=2e9;
	for(int i=0;i<=2e5;i++)
	{
		int len=s[i].size();
		if(len>=k)
		{
			int r=0;
			for(int j=0;j<k;j++)
				r+=s[i][j];
			ans=min(ans,r);
		}
	}
	printf("%d",ans);
	return 0;
}

E. Two Small Strings

题意：给你两个长度为 $2$ 且只由 $a,b,c$ 三个字符构成的两个字符串 $s,t$ ，你需要找到一个长度为 $3n$ 的字符串，其中 $a,b,c$ 分别出现 $n$ 次，且 $s,t$ 不是这个字符串的子串。先输出 $YES$ 或 $NO$ ，代表有没有这样的字符串，如果有，则输出这个字符串，如果有多个答案，你只需输出其中一种。

解析：首先肯定存在这样的字符串。分类讨论，如果两个字符串的两个字母都不同，则只用输出类似于这种样式的字符串： $aaabbbccc$ ，否则则输出类似于这样的字符串： $abcabcabc$ 。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,book[4][4];
char s[3],t[3];
int main()
{
	scanf("%d",&n);
	scanf("%s%s",s+1,t+1);
	printf("YES\n");
	if(s[1]!=s[2]&&t[1]!=t[2])
	{
		memset(book,0,sizeof(book));
		book[s[1]-'a'+1][s[2]-'a'+1]=1;
		book[t[1]-'a'+1][t[2]-'a'+1]=1;
		int a,b,c;
		for(int i=1;i<=3;i++)
			for(int j=1;j<=3;j++)
				for(int k=1;k<=3;k++)
				{
					if(i==j||j==k||i==k)
						continue;
					if(book[i][j]==0&&book[j][k]==0)
					{
						a=i;
						b=j;
						c=k;
						break;
					}
				}
		for(int i=1;i<=n;i++)
			printf("%c",a+'a'-1);
		for(int i=1;i<=n;i++)
			printf("%c",b+'a'-1);
		for(int i=1;i<=n;i++)
			printf("%c",c+'a'-1);
		return 0;
	}
	else if(s[1]==s[2]&&t[1]==t[2])
	{
		for(int i=1;i<=n;i++)
			printf("abc");
		return 0;
	}
	else if(s[1]==s[2]&&t[1]!=t[2])
	{
		memset(book,0,sizeof(book));
		book[t[1]-'a'+1][t[2]-'a'+1]=1;
		int a,b,c;
		for(int i=1;i<=3;i++)
			for(int j=1;j<=3;j++)
				for(int k=1;k<=3;k++)
				{
					if(i==j||j==k||i==k)
						continue;
					if(book[i][j]==0&&book[j][k]==0&&book[k][i]==0)
					{
						a=i;
						b=j;
						c=k;
						break;
					}
				}
		for(int i=1;i<=n;i++)
			printf("%c%c%c",a+'a'-1,b+'a'-1,c+'a'-1);
		return 0;
	}
	else if(t[1]==t[2]&&s[1]!=s[2])
	{
		book[s[1]-'a'+1][s[2]-'a'+1]=1;
		int a,b,c;
		for(int i=1;i<=3;i++)
			for(int j=1;j<=3;j++)
				for(int k=1;k<=3;k++)
				{
					if(i==j||j==k||i==k)
						continue;
					if(book[i][j]==0&&book[j][k]==0&&book[k][i]==0)
					{
						a=i;
						b=j;
						c=k;
						break;
					}
				}
		for(int i=1;i<=n;i++)
			printf("%c%c%c",a+'a'-1,b+'a'-1,c+'a'-1);
		return 0;
	}
	return 0;
}