1.30 vp Codeforces Round #846 (Div. 2)

A - Hayato and School、

题意

给出长度为n的序列a，要求判断是否存在三个数之和为奇数，若有则输出YES且输出这三个数的下标，否则输出NO

思路

数字和为奇数的情况只有奇 + 偶， 而三个数就可以是奇奇奇，奇偶偶这两种情况。
将序列分为奇偶两个部分，然后判断是否存在这两种情况中的一种即可

void solve() {
	int n;
	cin >> n;
	vector<int> a (n + 1);
	vector<int> o, e;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		if (a[i] % 2 == 1) o.push_back(i);
		else e.push_back(i);
	}
	
	if (o.size() >= 3 || e.size() >= 2 && o.size() >= 1) {
		cout << "YES" << endl;
		if (o.size() >= 3) {
			for (int i = 0; i < 3; i ++) cout << o[i] << ' ';
			cout << endl;
		}else {
			cout << e[0] << ' ' << e[1] << ' ' << o[0] << endl;
		}
	}else {
		cout << "NO" << endl;
	}

}

B - GCD Partition

题意

给出一个长度为n的序列，你可以将他们分为k份（k > 1），每份之和为\(b_i\)
例如：
序列：123456
分为三份
12,34,56
则b1 = 3, b2 = 7, b3 = 11
问怎么分可以使b数组所有元素的gcd最大

思路

因为k > 1，故而整个数组一定是被分为2份以上的，其中分的时候是按原数组顺序
所以我们可以想到只需要把数组分为两段即可，因为若存在倍数关系，则在两段的时候一定会出现，例如1 2 1 1 1 3，我们可以将它分为12， 111， 3三份gcd是3，但是把它分为两份12， 1113时3， 6的gcd也是3
因此对于序列的前缀和剩余部分进行gcd即可

LL gcd(LL a, LL b) {
	return b ? gcd(b, a % b) : a;
}

void solve() {
	int n;
	cin >> n;
	vector<int> a(n + 1);
	LL sum = 0;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		sum += a[i];
	}
	
	LL tmp = 0, mx = 0;
	
	for (int i = 1; i < n; i ++) {
		tmp += a[i];
		mx = max(mx, gcd(tmp, sum - tmp));
	}
	
	cout << mx << endl;
}

D - Bit Guessing Game

题意（交互）

你要猜题目给出的数字。
玩法：最开始的时候，会给你给出数字二进制上1的数量
然后你可以向系统输入x，然后给出的数字将减去x，再给你新的数字的二进制上1的数量
要求提问次数不超过30次，输出给出的数字

思路

看的大佬思路是lowbit，每次提问减去上次提问的lowbit + 1，然后以新的数量t和之前剩下的数量比较，看多了多少个1，将他们减掉即可，这样每次都可以消掉lowbit上的1，所以每次只会操作n次（0 < n < 30）
例如：
101100
-1
101011
-（100）2
100111
-（1000）2
11111
-（100000）2
ans即为上面减去的二进制数之和

void ask(int x) {
	cout << "- " << x << endl;
}
 
void solve() {
	int ans = 0, last = 1;
	int cnt;
	cin >> cnt;
	while (cnt) {
		ask(last);
		int t;
		cin >> t;
		ans |= (1 << (t - cnt + 1));
		last = (1 << (t - cnt + 1));
		cnt --;
	}
	cout << "! " << ans << endl;
}

总结

思维较之前有增长，交互题可能比较简单，所以也有思路，但是没写出来