Codeforces Round #767 (Div. 2)

A Download More RAM

题解代码 B GCD Arrays

题目题解

计算奇偶数的办法 代码 C Meximum Array

Mex (mathematics)题意题解

有n个软件，最初有k个内存，每个软件运行需要ai的内存，运行完可以获得bi个内存，问最后可以获得多少内存？
通过排序先运行所需内存小的软件以获得内存，即排序。

#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 111;
struct ab
{
	int a, b;
} arr[maxn];
bool cmp(ab a, ab b){
	return a.a < b.a;
}
int main(){
	int t; cin >> t;
	while(t--){
		int n, k; cin >> n >> k;
		for(int i = 0; i < n; i++) {
			cin >> arr[i].a;
		}
		for(int i = 0; i < n; i++){
			cin >> arr[i].b;
		}
		ll ans = k;
		sort(arr, arr + n, cmp);
		int pos = 0;
		while(arr[pos].a <= ans && pos < n){
			ans += arr[pos].b;
			pos++;
		}
		cout << ans << 'n';
	}
}

给你 l l l到 r r r这一段序列，在经过k次操作后，该段序列的最大公因数（即当前序列中的所有数字求解gcd）能否是大于1的数
操作：
从序列中取两个数字，将他们永久的从序列中删除，并加两者的乘积加入到队列中

计算连续数字奇数的个数，即为可操作的最大个数，举例如下
初始状态 3 ， 4 ， 5 ， 6 ， 7 3，4，5，6，7 3，4，5，6，7
第一次操作 3 ∗ 5 ， 4 ， 6 ， 7 3*5，4，6，7 3∗5，4，6，7
第二次操作 3 ∗ 5 ∗ 7 ， 4 ， 6 3*5*7，4，6 3∗5∗7，4，6
可以发现如上两次操作所得序列的gcd都是1
第三次操作 3 ∗ 5 ∗ 7 ∗ 4 ， 6 3*5*7*4，6 3∗5∗7∗4，6
第四次操作 3 ∗ 5 ∗ 7 ∗ 4 ∗ 6 3*5*7*4*6 3∗5∗7∗4∗6
显然从第三次操作起开始序列存在大于1的公因数了
那么解题思路就是所有奇数结合再加一个偶数序列即可得到大于1的公因数了

		ll odd  = (r - l + 1) / 2;
		ll even = (r - l + 1) / 2;
		if ((r - l + 1) % 2 == 1 && r % 2 == 1) odd ++;
		else even ++;

#include 
using namespace std;
typedef long long ll;
int main(){
	//freopen("in.txt","r",stdin);
	int t; cin >> t;
	while(t--){
		ll l, r, k;
		cin >> l >> r >> k;

		if (l == r)
		{
			if (l == 1)
				printf("NOn");
			else
				printf("YESn");

			continue;
		}
		ll odd  = (r - l + 1) / 2;
		ll even = (r - l + 1) / 2;
		if ((r - l + 1) % 2 == 1 && r % 2 == 1) odd ++;
		else even ++;
		//3个奇数可以操作三次
		
		//printf("%lldn", odd);
		if (odd <= k){
			printf("YESn");
		}
		else{
			printf("NOn");
		}
	}
}

补集的最小值

给你n个非负数字，你可以进行如下操作，每次选择连续的k个数字，求解这k个数字的Mex，然后放到b序列中，问最长长度为m的字典序的b序列里面的元素是什么？
输出数字m和m个元素