Codeforces Round 725 (Div. 3)

A.Stone Game

题目链接Stone Game

题意

给出一个长度为$n$的序列，每次可进行一次操作，求达成目标的最小操作数。

操作：每次可以删除序列的头元素或尾元素。

目标：最小值以及最大值被删除。

思路

枚举三种可行的操作，取最小值。

1、从序列头开始删，删到需要删除的数停止。然后从序列尾开始删，删到需要删除的数停止。

2、从序列头开始删，直至删除两个需要删除的数。

3、从序列尾开始删，直至删除两个需要删除的数。

代码

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
using namespace std;
int n;
const int N = 10010;
int a[N];
int main(){
	int t;
	cin >> t;
	while (t--){
		int maxc = -1,minc = 110;
		cin >> n;
		int p,q;
		for (int i = 0; i < n; i++) cin >> a[i];
		for (int i = 0; i< n; i ++){
			if (minc > a[i]) minc = a[i], p = i;
			if (maxc < a[i]) maxc = a[i], q= i;
		}
		if(p > q) swap(p,q);
		int cnt = 0,idx = 0,ans = 0;
		ans = min(p + 1, n - p)+min(n - q, q + 1);
		cnt = q + 1;
		idx = n - p;
		ans = min(ans,cnt);
		ans = min(ans,idx);
		cout << ans << '\n';
	}
	return 0;
}

B. Friends and Candies

题目链接Friends and Candies

题意：

共有$n$个人，每个人有数量为$a[i]$的物品，求使所有人物品数量相同的最小操作数。

操作：拿出一个人的东西分给其他人。

思路：

$a[i]$大于平均值的，对答案的贡献为$1$

代码

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
using namespace std;
int n;
const int N = 2e5 + 7;
int a[N];
int main(){
	int t;
	cin >> t;
	while (t--){
		cin >> n;
		long long sum = 0;
		for (int i = 0; i < n; i++) cin >> a[i],sum += a[i];
		if (sum % n != 0){
			puts("-1");continue;
		}else {
			long long cnt = sum / n;
			int idx = 0;
			for (int i = 0; i< n; i++){
				if (a[i] > cnt ) idx++;
			}
			cout << idx << '\n';
		}
	}
	return 0;
}

C. Number of Pairs

题目链接Number of Pairs

题意：

给出一个数组$a$以及一个区间$[l,r]$，求满足$l<=a[i]+a[j]<=r$的数对$pair(i,j)$的数量

思路：

这题的$i,j$顺序其实没什么关系，可以直接排序。

二分找边界。

代码：

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
using namespace std;
int n;
const int N = 2e5 + 7;
int a[N];
int main(){
	int t;
	cin >> t;
	while (t--){int l,r;
		cin >> n >>l >> r;
		for (int i = 0; i < n; i++) cin >> a[i];
		sort(a,a+n);
		long long ans = 0;
		for (int i =0 ; i< n; i ++){
			int x = lower_bound(a,a+n,l-a[i])-a;
			int y = upper_bound(a,a+n,r-a[i])-a;
			if (x <= i) x = i +1;
			if (y <= i) y = i + 1;
			ans += (y - x);
		}
		cout << ans << '\n';
	}
	return 0;
}

D. Another Problem About Dividing Numbers

题目链接Another Problem About Dividing Numbers

题意：

给出两个整数$a$和$b$，每次可以进行一次操作，将a除上一个数$c$，或者将b除上一个数$c$，$c$能够整除$a$或者$b$，并且$c$大于1。问是否能通过恰好$k$次操作使得$a$和$b$相等。

思路：

讨论出使得$a$和$b$相等所需要的最小次数$Mincnt$，以及所需要的最大次数$Maxcnt$。

最小次数：

如果$a=b$,不需要进行操作，$Mincnt=0$；

如果$a|b$或者$b|a$，我们可以通过一次操作使得$a=b$，$Mincnt =1$；

如果以上两种情况都不满足，则需要两次操作，即二者都除上他们本身，$Mincnt = 2$。

最大次数：

分解质因数，使$a$和$b$变成1的操作次数即最大次数

因为只需最小次数$Mincnt$就能使$a=b$，其他$k-Mincnt$次无论怎么操作，都能符合题意。

所以如果给出的$k$在$Mincnt--Maxcnt$之间，$k$就一定能满足题目要求。

需要注意当$k=1$时，这意味着我们只能对其中一个数进行一次操作，需要保证$a|b$或者$b|a$，即$Mincnt=1$。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int n;
const int N = 2e5 + 7;
int prime[N],v[N],m;
void getprime(int n){
	for (int i = 2; i <= n; i ++){
		if (!v[i]) {
			prime[++m] = i;
			v[i] = i;
		}
		for (int j = 1; j <= m; j ++){
			if (prime[j] > v[i] || prime[j] > n / i) break;
			v[i*prime[j]] = prime[j];
		}
	}
}
int f(int n){
	int cnt = 0;
	for (int i = 1; i <= m; i ++){
		while (n % prime[i] == 0){
			n /= prime[i];
			cnt++;
		}
		if(n == 1) break;
		if(n < prime[i]) break;
	}
	if(n > 1) cnt++;
	return cnt;
}
int main(){
	int t;
	cin >> t;
	int M = sqrt(1e9);
	getprime(M);
	while (t--){
		int x,y,k, Mincnt,Maxcnt;
		cin >> x >> y >> k;
		if (x > y) swap(x,y);
		int gcd = __gcd(x,y);
		if (gcd == x && x != y) Mincnt = 1;
		else if (x == y) Mincnt = 0;
		else Mincnt = 2;
		Maxcnt = f(x) + f(y);
		if (Mincnt <= k && k <= Maxcnt && (k != 1 || k == 1 && Mincnt == 1 ) ) puts("YES");
		else puts("NO");
	}
	return 0;
}

F. Interesting Function

题目链接：Interesting Function

题意：

给出一个初始数$l$，和终点数$r$。$l$自增到$r$，求各位数字变化了多少次。

比如$1——4$，变化了三次，个位三次$(1->2->3->4)$；

$8——12$，变化了六次，个位五次$(8->9->0->1->2)$，十位一次$(0->1)$。

思路：

先计算出除了进位的各位数字的变化，不难发现除了进位的变化就是这个数字本身(从0开始)。

观察进位的变化，对于十位上的数来说，每加上$10$，对答案的贡献就加一，只需要计算出加了多少个$10$即可，其他位数同理。

代码：

#include <iostream>
using namespace std;
int main(){
	int t,L,R;
	cin >> t;
	while (t--){
		cin >> L >> R;
		int idx = R ,cnt = L;
		while (R){
			R /= 10;
			idx += R;
		}
		while (L){
			L /= 10;
			cnt += L;
		}
		cout << idx - cnt << '\n';
	}
}

G. Gift Set

题目链接：Gift Set

题意：

有$x$个红糖果和$y$个蓝糖果，将这些糖果按固定的分配方案分组。要求：每组包含$a$个红糖果，$b$个蓝糖果；或者$a$个蓝糖果，$b$个红糖果。输出能分的最大组数。

思路：

二分答案要分的组数$n$。

其中一组为$k$ ，另外一组为$n-k$。

$x,y,k$需满足以下条件

$$\begin{cases} x <= a*k+b*(n-k)\\ y <= a*(n-k)+b*k\\ 0 <= k <=n \end{cases}$$

整理得：

$$\begin{cases} k >= (y-n*a)/(b-a)\\ k<= (n*b - x)/(b-a)\\ k >= 0\\ k <= n \end{cases}$$

二分检查是否满足上式即可。

另外如果$a==b$，可以直接得出答案。

注意二分模板的使用，以及区间左端点向上取整，右端点向下取整。

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
ll a,b,x,y;
bool check(ll n){
    ll l2 = ceill((y - n*a)*1.0/(b-a)), r2 = floorl((b*n -x )*1.0 / (b-a));
    l2 = max(0ll,l2), r2 = min( n, r2);
    return l2 <= r2;
}
int main(){
    int t;
    cin >> t;
    while (t--){
        //cout << t << endl;
        cin >> x >>y >> a >> b;
        if(a < b) swap(a,b);
        if (a == b) {
            cout << min(x,y) / a << '\n';continue;
        }
        else {
            ll l = 0 ,r = 1e9 + 7;
            while (l < r) {
                ll mid = l + r +1>> 1;
                if (check(mid)) l  = mid;
                else r = mid - 1;
            }
            cout << l << '\n';
        }
    }
}