https://codeforces.com/contest/1323

C. Unusual Competitions

 

题意：括号序列，每次可以选一段，内部自由调整，花费为这段的长度，问调整成正确序列的最小花费。

直接贪心找错的一段调整。如果右括号左边的左括号不够的话一定是要调整的，就看调整到哪里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int n;
int sum, l, r;
char s[N];
int ans;
int main() {
	scanf("%d", &n);
	scanf("%s", s + 1);
	for (int i = 1; s[i]; i++) {
		sum += (s[i] == '(' ? 1 : -1);
		if (sum == -1 && l == 0) {
			l = i;
		}
		else if (sum == 0 && l != 0) {
			ans += i - l + 1;
			l = 0;
		}
	}
	if (sum != 0)puts("-1");
	else cout << ans << endl;
	return 0;
}

 

D. Present

 

题意：给定数组 aa，计算

(a1+a2)⊕(a1+a3)⊕…⊕(a1+an)⊕(a2+a3)⊕…⊕(a2+an)…⊕(an−1+an)(a_1 + a_2) \oplus (a_1 + a_3) \oplus \ldots \oplus (a_1 + a_n) \\ \oplus (a_2 + a_3) \oplus \ldots \oplus (a_2 + a_n) \\ \ldots \\ \oplus (a_{n-1} + a_n) \\

按位枚举+二分

O(30n)O(30n)

枚举每一位，再枚举每个数，二分计算它后面有几个数和它的和在这一位为1.

首先把所有数高于这一位的部分都去掉，因为没影响且去掉才能排序。

两个数的范围都在 [0,2i+1)[0,2^{i+1})，所以和的范围在 [0,2i+2)[0,2^{i+2})。

这个范围里第 ii 位为 1 的数只有两个范围，[2i,2i+1)[2^i,2^{i+1}) 和 [2i+1+2i,2i+2)[2^{i+1}+2^i,2^{i+2})

那么二分找到这两个区间里数的个数就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int n;
int a[N], b[N], ans;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 0; i < 30; i++) {
		for (int j = 1; j <= n; j++)b[j] = a[j] % (1 << (i + 1));
		sort(b + 1, b + n + 1);
		int l, r, s = 0;
		for (int j = 1; j <= n; j++) {
			l = lower_bound(b + 1, b + n + 1, (1 << i) - b[j]) - b;
			r = lower_bound(b + 1, b + n + 1, (1 << (i + 1)) - b[j]) - b - 1;
			s += r - l + 1;
			l = lower_bound(b + 1, b + n + 1, (1 << (i + 1)) + (1 << i) - b[j]) - b;
			r = lower_bound(b + 1, b + n + 1, (1 << (i + 2)) - b[j]) - b - 1;
			s += r - l + 1;
			if ((b[j] + b[j])&(1 << i))s--;
		}
		s /= 2;
		if (s & 1)ans |= (1 << i);
	}
	cout << ans << endl;
	return 0;
}