Codeforces Round #626 (Div. 1, based on Moscow Open Olympiad in Informatics) 题解

Codeforces Round #626 (Div. 1, based on Moscow Open Olympiad in Informatics)

Unusual Competitions

前缀和一下，从前缀和为 $0$ 的位置将序列分成若干段。

对于每一段，如果它是负的，则这一段必须要重排，否则不用。

const int N = 1e6 + 7;
int n, c[2], a[N], ans;
char s[N];

int main() {
	rd(n), rds(s, n);
	for (int i = 1; i <= n; i++)
		if (s[i] == '(') c[0]++;
		else c[1]++;
	if (c[0] != c[1]) return print(-1), 0;
	for (int i = 1, p = 0; i <= n; i++) {
		if (s[i] == '(') a[i] = a[i-1] + 1;
		else a[i] = a[i-1] - 1;
		if (!a[i]) {
			bool ok = 0;
			for (int j = p + 1; j <= i; j++)
				if (a[j] < 0) ok = 1;
			if (ok) ans += i - p;
			p = i;
		}
	}
	print(ans);
	return 0;
}

Present

按位考虑。

对于第 $k$ 位，我们只关心每个数对 $2^{k+1}$ 取模后的值。

对于两个取模后的数，如果要在第 $k$ 位为 $1$，和必须在 $[2^k, 2^{k+1}-1]$ 或 $[2^k + 2^{k+1}, 2^{k+2}-2]$ 中。

排序之后双指针扫一遍即可，时间复杂度 $\mathcal O(n \log n \log w)$。

const int N = 4e5 + 7;
int n, a[N], b[N], ans;

inline bool calc(int L, int R) {
	if (L > R) return 0;
	ll ret = 0;
	for (int i = n, l = 1, r = 1; i; i--) {
		while (l <= n && b[i] + b[l] < L) ++l;
		while (r <= n && b[i] + b[r] <= R) ++r;
		ret += r - l - (l <= i && i < r);
	}
	return (ret >> 1) & 1;
}

inline bool solve(int k) {
	for (int i = 1; i <= n; i++) b[i] = a[i] & ((1 << (k + 1)) - 1);
	sort(b + 1, b + n + 1);
	return calc(1 << k, (1 << (k + 1)) - 1) ^ calc(3 << k, (1 << (k + 2)) - 2);
}

int main() {
	rd(n), rda(a, n);
	for (int i = 0; i < 26; i++) ans |= solve(i) << i;
	print(ans);
	return 0;
}

Instant Noodles

对于右部点 $i$，设 $S(i)$ 表示所有与其相连的左部点的集合。

对于 $i$，若 $|S(i)| = 0$，则可以直接扔掉。

对于 $i,j$，若 $S(i) = S(j)$，则这两个点可以合并为一个，合并后的点的权值为原先两点权值之和。

合并后，所有点的 $S(i)$ 均不为空集且互不相同，此时对所有点的权值求 $\gcd$ 即可。

判断 $S(i) = S(j)$ 时需要 hash 一下。

const int N = 5e5 + 7;
int n, m, B, P;
ll a[N];
vi e[N];

inline int h(vi p) {
	sort(p.begin(), p.end());
	int ret = 0;
	for (int x : p) ret = (1ll * ret * B + x) % P;
	return ret;
}

inline void solve() {
	rd(n), rd(m), rda(a, n);
	for (int i = 1; i <= n; i++) e[i].clear();
	for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), e[y].pb(x);
	map<int, ll> p;
	for (int i = 1; i <= n; i++)
		if (e[i].size()) p[h(e[i])] += a[i];
	ll d = 0;
	for (auto o : p) d = d ? __gcd(d, o.se) : o.se;
	print(d);
}

int main() {
	srand(time(0));
	P = rdm((int)1e8, (int)1e9);
	B = rdm((int)1e7, (int)1e8);
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}

Reality Show

题目太神仙了，先咕咕咕着。

Median Mountain Range

题目太神仙了，先咕咕咕着。

Assigning Fares

题目太神仙了，先咕咕咕着。