Codeforces Round #725 (Div. 3)

文章目录


A、Stone Game

传送门


1.思路

先找到最大值和最小值的下标,然后分3类讨论(只操作左端点,只操作右端点,和两端都操作)取最小值即可。


2.参考代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int n;
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int maxx = INT_MIN, maxi = 0, minn = INT_MAX, mini = 0;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			if (a[i] > maxx)
			{
				maxx = a[i];
				maxi = i;
			}
			if (a[i] < minn)
			{
				minn = a[i];
				mini = i;
			}
		}
		int sum1 = 0, sum2 = 0, sum3 = 0;
		sum1 = max(maxi, mini);
		sum2 = n - min(maxi, mini) + 1;
		sum3 = min(maxi, mini) + n - max(maxi, mini) + 1;
		printf("%d\n", min(sum1, min(sum2, sum3)));
	}
}



B、Friends and Candies

传送门


1.思路

要将每个a[i]值都变成相同,则需要将大于平均值的数取出来然后进行分配,知道这点就能轻松AC,但是注意要判断输出-1的情况(a[i]的和不能被n整除)。


2.参考代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 10;
ll a[maxn];
ll sum;
ll n;
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		sum = 0;
		scanf("%lld", &n);
		for (int i = 1; i <= n; i++)
		{
			scanf("%lld", &a[i]);
			sum += a[i];
		}
		if (sum % n != 0)printf("-1\n");
		else
		{
			ll avge = sum / n;
			int ans = 0;
			for (int i = 1; i <= n; i++)
				if (a[i] > avge)ans++;
			printf("%d\n", ans);
		}
	}
}



C、Number of Pairs

传送门


1.思路

要找到有多少对符合条件的数对,则我们可以通过for循环来枚举起点,至于终点要怎么得到呢?

继续for循环?如果继续for循环将喜提TLE,起点确定了来确定符合条件的一段区间可以通过二分来获取。先sort一下,然后二分下标找符合条件的数对对数。

二分可以巧用upper_boundlower_bound。用upper_bound来找到第一个大于**r - a[i]的下标,用lower_bound来找到第一个大于等于l - a[i]**的下标。在两个下标之间的个数就是全部符合条件的个数。注意upper_bound和lower_bound返回下标时可能小于了i,这是我们需要去掉这段区间


2.参考代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 10;
ll a[maxn];
ll n, l1, r1;
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%lld%lld%lld", &n, &l1, &r1);
		for (int i = 1; i <= n; i++)
			scanf("%lld", &a[i]);
		sort(a + 1, a + 1 + n);
		ll ans = 0;
		for (int i = 1; i <= n; i++)
		{
			ll x = upper_bound(a + 1, a + n + 1, r1 - a[i]) - a - 1;
			if (x <= i)continue;
			ans += x - i;
			ll y = lower_bound(a + 1, a + n + 1, l1 - a[i]) - a - 1;
			if (y <= i)continue;
			ans -= y - i;
		}
		printf("%lld\n", ans);
	}
}



D、 Another Problem About Dividing Numbers

传送门


1.思路

这题主要是找到符合a、b转换相同的次数的区间较难。

首先我们可以把a、b的最大公约数求出来。转化的时候就是最大公约数gcd可以转换2次,则最多可以转化2*(最大公约数的质因子个数)次。那a/gcd、b/gcd也可转化各自的质因子的个数次。

则转化为相同数的最多次数为2*(最大公约数的质因子个数)+a/gcd的质因子的个数+b/gcd的质因子的个数

最小的地方判断要更加细心,我由于粗心导致WA了两发。首先在ab的地方k一定是不能等于1的。其次ab的时候,最小转化次数为0。a % b ==0|| b % a == 0时,最小转化次数为1,那其余的情况则为2了。


2.参考代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn = 1e5 + 10;
ll a, b, k;
ll prime[maxn];
bool vis[maxn];
ll cnt;
ll gcd(ll x, ll y)
{
	return y == 0 ? x : gcd(y, x % y);
}
void Prime()
{
	for (int i = 2; i < maxn; i++)
	{
		if (vis[i] == false) prime[cnt++] = i;
		for (int j = 0; i * prime[j] < maxn; j++)
		{
			vis[i * prime[j]] = true;
			if (i % prime[j] == 0) break;
		}
	}
}
ll solve(ll h)
{
	ll ans = 0;
	for (int i = 0; i < cnt; i++)
	{
		if (prime[i] * prime[i] > h)break;
		if (h % prime[i] == 0)
		{
			ll sum = 0;
			while (h % prime[i]==0)
			{
				h /= prime[i];
				sum++;
			}
			ans +=sum;
		}
	}
	if (h != 1)ans += 1;
	return ans;
}
 
int main()
{
	int t;
	scanf("%d", &t);
	Prime();
	while (t--)
	{
		scanf("%lld%lld%lld", &a, &b, &k);
		if (a == b && k == 1)printf("NO\n");
		else if (a == 1 && b == 1 && k != 0)printf("NO\n");
		else
		{
			ll l, r;
			ll xx = gcd(a, b);
			ll yy = a / xx, zz = b / xx;
			if (a == b)l = 0;
			else if (a % b == 0 || b % a == 0)l = 1;
			else l = 2;
			r = 2 * solve(xx) + solve(yy) + solve(zz);
			if (k >= l && k <= r)printf("YES\n");
			else printf("NO\n");
		}
	}
}



F、Interesting Function

传送门


1.思路

思路极其简单,只需要判断l到r中,每一位数字变化的次数相加即可。(水题放这么后面,cf搞心态呀)


2.参考代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		ll ans = 0;
		ll l, r;
		scanf("%lld%lld", &l, &r);
		while (r)
		{
			ans += r - l;
			r /= 10;
			l /= 10;
		}
		printf("%lld\n", ans);
	}
}



上一篇:PIoU Loss|用于提高旋转目标检测器性能的新型损失函数


下一篇:力扣204题(如何高效寻找素数)