【LGR-065】洛谷 11 月月赛 III Div.2 题解

【LGR-065】洛谷 11 月月赛 III Div.2

基础字符串练习题

前缀和 + 贪心。

注意「非空子串」。

const int N = 1e5 + 7;
int n, ans = -1;
char s[N];

int main() {
	rds(s, n);
	for (int i = 1, o = 0, k = 0; i <= n; i++) {
		k += (s[i] == '0' ? 1 : -1);
		ans = Max(ans, k - o);
		o = Min(o, k);
	}
	print(ans);
	return 0;
}

基础最短路练习题

由于「保证 $G$ 中不存在简单环使得边权异或和不为 $0$」，因此随便找一条路径即可。

const int N = 1e5 + 7;
int n, m, q, v[N], d[N];
vector< pi > e[N];

void dfs(int x) {
	v[x] = 1;
	for (ui i = 0; i < e[x].size(); i++) {
		int y = e[x][i].fi;
		if (v[y]) continue;
		d[y] = d[x] ^ e[x][i].se;
		dfs(y);
	}
}

int main() {
	rd(n), rd(m), rd(q);
	for (int i = 1, x, y, z; i <= m; i++) {
		rd(x), rd(y), rd(z);
		e[x].pb(mp(y, z)), e[y].pb(mp(x, z));
	}
	dfs(1);
	for (int i = 1, x, y; i <= q; i++) {
		rd(x), rd(y);
		print(d[x] ^ d[y]);
	}
	return 0;
}

基础博弈练习题

首先只跟 $a$ 的奇偶性有关。

其次如果 $a_l$ 为偶数则先手必胜。

否则 $l \sim r$ 中最右边的一个先手必败的位置一定是最右边的奇数位置，而它上一个先手必败的位置一定是这个位置的 $m$ 个位置以前的最右边的奇数位置，依次类推。

可以发现这个关系形成一个树形结构，那么判断最右边的奇数位置在不在 $l$ 的子树中即可，可以用 dfs 序判断。

const ui N = 1e6 + 7;
int n, m, q, o, a[N], p[N], L[N], R[N], num, A, B, C, P;
ui ans;
vector< int > e[N];

inline int rnd() {
	return A = (A * B + C) % P;
}

void dfs(int x) {
	L[x] = ++num;
	for (ui i = 0; i < e[x].size(); i++) dfs(e[x][i]);
	R[x] = num;
}

int main() {
	rd(n), rd(m), ++m, rd(q), rd(o);
	for (int i = 1, j = 0; i <= n; i++) {
		rd(a[i]), a[i] &= 1;
		if (a[i]) {
			j = i;
			e[p[Max(0,i-m)]].pb(i);
		}
		p[i] = j;
	}
	dfs(0);
	if (o) rd(A), rd(B), rd(C), rd(P);
	for (int i = 1; i <= q; i++) {
		int l, r;
		if (o) {
			l = rnd() % n + 1, r = rnd() % n + 1;
			if (l > r) swap(l, r);
		} else rd(l), rd(r);
		if (!a[l] || L[l] > L[p[r]] || L[p[r]] > R[l]) ans += 1ll * i * i;
	}
	print(ans);
	return 0;
}

基础最优化练习题

首先不考虑 $a$ 的限制，那么一个位置是加是减取决于这个位置对答案的贡献是正是负，而对答案的贡献显然为 $w$ 的后缀和。

再考虑 $a$ 的限制，如果一个位置超出了限制，则应该不断地从之前贡献最小的位置减掉贡献，直到不超出，用一个堆维护即可。

时间复杂度 $\mathcal O(n \log n)$。

const int N = 1e6 + 7;
int n, k, a[N], now;
ll b[N], ans;
pq< pi > q;

int main() {
	rd(n), rd(k);
	for (int i = 1; i <= n; i++) rd(a[i]);
	for (int i = 1; i <= n; i++) rd(b[i]);
	for (int i = n; i; i--) b[i] += b[i+1];
	for (int i = 1; i <= n; i++) {
		if (b[i] >= 0) now += k, ans += k * b[i], q.push(mp(-b[i], k << 1));
		else now -= k, ans -= k * b[i];
		while (now > a[i]) {
			pi o = q.top();
			q.pop();
			int w = Min(o.se, now - a[i]);
			now -= w, ans += w * o.fi;
			if ((o.se -= w)) q.push(o);
		}
	}
	print(ans);
	return 0;
}