Educational Codeforces Round 106 (Rated for Div. 2)ABCD题解

69 阅读 0 评论 46 点赞

我是靠谱客的博主欢喜羊，最近开发中收集的这篇文章主要介绍Educational Codeforces Round 106 (Rated for Div. 2)ABCD题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A题，按照题意判断一下就行了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int t,n,m,a[N],b[N];
bool vis[N];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		int k1,k2,w,b;
		scanf("%d%d%d%d%d",&n,&k1,&k2,&w,&b);
		int kmi=min(k1,k2),kma=max(k1,k2);
		if(kmi+(kma-kmi)/2>=w&&(n-kma)+(kma-kmi)/2>=b)puts("YES");
		else puts("NO");		
	}
	return 0;
}

B题，看能不能把字符串变成前面是0后面是1，但是不能同时改变相邻的2个

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int t,n,m,a[N],b[N];
bool vis[N];
string s;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		cin>>s;
		int n=s.size();
		bool f=0;
		for(int i=0;i<n;i++)
		{
			if(!f&&s[i]=='1')
			{
				s[i]='0';
				if(s[i+1]=='1')f=1;
				i++;
			}
			else if(f&&s[i]=='0')
			{
				s[i]='1';
				i++;
			}
		}
		bool ff=0;
		for(int i=1;i<n;i++)if(s[i]-s[i-1]<0)
		{
			ff=1;
			break;
		}
		if(ff)puts("NO");
		else puts("YES");
	}
	return 0;
}

C题，把奇数位当作是往右走，把偶数位当作往上走
最优解的情况一定是把最多的步数放再最小段上，其他段只走一步
预处理 $s u m a$ ，和 $s u m b$ ，然后遍历更新 $a n s$ ，在最后遍历出最小花费

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int t,n,m;
ll a[N],b[N],ans[N],suma[N],sumb[N];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			ll x;
			scanf("%lld",&x);
			if(i&1)a[i]=x,suma[i]=suma[i-1]+x,sumb[i]=sumb[i-1];
			else b[i]=x,sumb[i]=sumb[i-1]+x,suma[i]=suma[i-1];
		}
		ans[2]=a[1]*n+b[2]*n;
		ll ma=a[1],mb=b[2];
		for(int i=3;i<=n;i++)
		{
			if(i&1)
			{
				ll k=i/2;
				if(a[i]<ma)ans[i]=ans[i-1]-(n-k)*(ma-a[i]);
				else ans[i]=ans[i-1]-ma+a[i];
			}
			else
			{
				ll k=(i-1)/2;
				if(b[i]<mb)ans[i]=ans[i-1]-(n-k)*(mb-b[i]);
				else ans[i]=ans[i-1]-mb+b[i];
			}
			if(i&1)ma=min(ma,a[i]);
			else mb=min(mb,b[i]);
		}
		ll res=(1ll<<60);
		for(int i=2;i<=n;i++)
		res=min(res,ans[i]);
		cout<<res<<'n';
	}
	return 0;
}

D题，首先要知道 $l c m (a, b)$ = $a * b / g c d (a, b)$ ，下面用 $g$ 表示 $g c d (a, b)$
即求 $a * b * c / g - d * g = x$ ，而 $a$ 可以表示成 $g * k 1$ ， $b$ 可以表示成 $g * k 2$ ，其中 $k 1$ 和 $k 2$ 互质。
用令 $k = k 1 * k 2$ ，那么上式就变成了 $g * (k * c - d) = x$ ，那么 $k = (x / g + d) / c$ ，其中 $x$ % $g = 0$ ， $(x / g + d)$ % $c = 0$ ，这题就变成了求有多少 $(k 1, k 2)$ 对，因为 $k$ 是2个互质的数的乘积，那么就需要知道 $k$ 有多少个质因子。
比如 $k = 2 * 2 * 3 * 5$ ，有3个质因子 $(k 1, k 2)$ 可以为 $(1, 2 * 2 * 3 * 5)$ , $(2 * 2, 3 * 5)$ , $(3, 2 * 2 * 5) . . . .$
不难发现规律, $(k 1, k 2)$ 的组数为 $C(3,0)+C(3,1)+C(3,2)+C(3,3)=2^3$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e7+10;//k1*k2的最大值为2e7
int prim[N],cnt[N],cc;//cnt[i]表示i这个数有多少个质因子
bool vis[N];
ll ans=0;
int c,d,x;
void init(int n){
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])prim[++cc]=i,cnt[i]=1;
		for(int j=1;prim[j]<=n/i;j++)
		{
			vis[i*prim[j]]=1;
			if(i%prim[j]==0)//如果i含有prim[j]这个因子
			{
				cnt[i*prim[j]]=cnt[i];
				break;
			}
			else cnt[i*prim[j]]=cnt[i]+1;
		}
	}
}
void work(int k)
{
	if(((x/k)+d)%c)return;
	int p=((x/k)+d)/c;
	ans+=1<<cnt[p];
}
int main()
{
	int t;
	scanf("%d",&t);
	init(N-1);
	while(t--)
	{
		ans=0;
		scanf("%d%d%d",&c,&d,&x);
		for(int i=1;i*i<=x;i++)
		{
			if(x%i==0)
			{
				work(i);
				if(i*i!=x)work(x/i);
			}
		}
		cout<<ans<<'n';
	}
	return 0;
}