AtCoder Grand Contest 029 题解

AtCoder Grand Contest 029

Irreversible operation

最后的字符串一定是所有 W 在 B 前面，于是考虑对应位置下标差之和即可。

const int N = 2e5 + 7;
int n, p[N], t;
char s[N];
ll ans;

int main() {
	rds(s, n);
	for (int i = 1; i <= n; i++)
		if (s[i] == 'B') p[++t] = i;
	for (int i = 1; i <= t; i++)
		ans += n - t + i - p[i];
	print(ans);
	return 0;
}

Powers of two

注意到 $\le x$ 且能与 $x$ 匹配的数是唯一的，于是从大到小贪心即可。

const int N = 2e5 + 7, M = 31;
int n, a[N], b[N], ans;
map<int, int> c;

int main() {
	rd(n), rda(a, n);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		++c[a[i]], b[i] = 1;
		while (b[i] <= a[i]) b[i] <<= 1;
		b[i] -= a[i];
	}
	for (int i = n; i; i--)
		if (c[a[i]]) {
			--c[a[i]];
			if (c[b[i]]) --c[b[i]], ++ans;
		}
	print(ans);
	return 0;
}

Lexicographic constraints

题意

• 有 $n$ 个字符串 $s_{1\dots n}$，对于 $i \in [1,n-1]$，满足 $s_i < s_{i+1}$。
• 现在你不知道 $s_{1\dots n}$，但你知道 $s_i$ 的长度为 $a_i$。
• 求最小的字符集大小，可以构造出合法的 $s_{1\dots n}$。
• $n \le 2 \times 10^5$，$a_i \le 10^9$。

题解

显然答案具有可二分性，先二分答案。

如果 $a_i > a_{i-1}$，则就是在 $s_{i-1}$ 的基础上后面加一堆 $a_i - a_{i-1}$ 个 $1$；否则，就是砍掉 $s_{i-1}$ 中 $> a_i$ 的部分然后 $+1$。

用栈维护 $s$ 中的每个相同字符连续段以及 $+1$ 操作，根据势能分析复杂度为 $\mathcal O(n)$。

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

代码

const int N = 2e5 + 7, M = 31;
int n, a[N], p[N], c[N], s[N], t;

inline void add(int x, int k) {
	if (x == p[t]) c[t] += k, s[t] += k;
	else p[++t] = x, c[t] = k, s[t] = c[t] + s[t-1];
}

inline bool add1(int m) {
	if (t == 1 && p[t] == m) return 0;
	if (p[t] != m) {
		if (c[t] == 1) --t, add(p[t+1] + 1, 1);
		else --c[t], --s[t], add(p[t] + 1, 1);
	} else {
		int k = c[t--];
		if (c[t] == 1) --t, add(p[t+1] + 1, 1);
		else --c[t], --s[t], add(p[t] + 1, 1);
		add(1, k);
	}
	return 1;
}

inline bool pd(int m) {
	t = 0, add(1, a[1]);
	for (int i = 2; i <= n; i++)
		if (a[i] > a[i-1]) add(1, a[i] - a[i-1]);
		else {
			while (s[t] > a[i]) --t;
			if (s[t] < a[i]) add(p[t+1], a[i] - s[t]);
			if (!add1(m)) return 0;
		}
	return 1;
}

int main() {
	rd(n), rda(a, n);
	int l = 1, r = n;
	while (l < r) {
		int d = (l + r) >> 1;
		if (pd(d)) r = d;
		else l = d + 1;
	}
	print(l);
	return 0;
}

Grid game

显然先手一直会往下走，后手需要找到一个格子让先手无法走。

求出到每一行时后手可以让棋子在哪些列，如果这些列中存在某个位置有障碍，则让棋子走到这个障碍上方即可。

const int N = 2e5 + 7;
int n, m, k, p[N];

int main() {
	rd(n, m, k);
	for (int i = 1; i <= n; i++) p[i] = m + 1;
	for (int i = 1, x, y; i <= k; i++)
		rd(x, y), p[x] = min(p[x], y);
	for (int i = 2, r = 1; i <= n; i++)
		if (r >= p[i]) return print(i - 1), 0;
		else if (r + 1 < p[i]) ++r;
	print(n);
	return 0;
}

Wandering TKHS

题意

• 给定一棵 $n$ 个点的树。
• 你现在在某个点 $r$，你要到 $1$ 去。
• 每次你会移动到未去过的，且与去过的点相邻的编号最小的点。
• 你要求出对于 $r \in [2,n]$，从 $r$ 到 $1$ 的移动次数。
• $n \le 2 \times 10^5$。

题解

把 $1$ 当做根，设 $f_x$ 表示 $x$ 的父亲，$m_x$ 表示 $1 \to f_X$ 的路径上编号最大的点，$h_{x,y}$ 表示从 $x$ 开始不经过 $f_x$ 和其它编号 $>y$ 的点的情况下能到达多少个点，$c_x$ 表示 $x$ 的答案。

考虑对于每个 $x$，讨论一下可知 $c_x - c_{f_x}$ 为 $h_{x,m_x} - [x < m_x][x < m_{f_x}]h_{x,m_{f_x}}$。

而对于 $h$ 有 $h_{x,y} = 1 + \sum_{z \in \text{son}(x)} [z \le y]h_{z,y}$。

注意到对于 $h_{x,y}$，有用的 $y$ 值只有 $m_x$ 和 $m_{f_X}$，因此总状态数为 $\mathcal O(n)$，时间复杂度也为 $\mathcal O(n)$。

代码

const int N = 2e5 + 7;
int n, m[N], c[N];
vi e[N];
unordered_map<int, int> h[N];

void dfs1(int x, int f) {
	if (x == 1) m[x] = -1;
	else {
		m[x] = max(m[f], f), h[x][m[x]] = 0;
		if (x < m[x] && m[f] > x) h[x][m[f]] = 0;
	}
	for (pi o : h[x])
		for (int y : e[x])
			if (y < o.fi) h[y][o.fi] = 0;
	for (int y : e[x])
		if (y != f) dfs1(y, x);
	for (auto &o : h[x]) {
		++o.se;
		for (int y : e[x])
			if (y < o.fi) o.se += h[y][o.fi];
	}
	if (x == 1) return;
	if (x > m[x]) c[x] += h[x][m[x]];
	else {
		c[x] += h[x][m[x]];
		if (m[f] > x) c[x] -= h[x][m[f]];
	}
}

void dfs2(int x, int f) {
	c[x] += c[f];
	for (int y : e[x])
		if (y != f) dfs2(y, x);
}
 
int main() {
	rd(n);
	for (int i = 1, x, y; i < n; i++)
		rd(x, y), e[x].pb(y), e[y].pb(x);
	dfs1(1, 0), dfs2(1, 0);
	for (int i = 2; i <= n; i++)
		print(c[i], " \n"[i==n]);
	return 0;
}

Construction of a tree

题意

• 给定 $[1,n]$ 的 $n-1$ 个子集 $E_{1\dots n-1}$。
• 问是否能从每个子集中选择两个元素，使得将这两个元素相连后形成一棵树，如果可以请构造一组方案。
• $n \le 10^5$，$\sum_{i=1}^{n-1} |E_i| \le 2 \times 10^5$。

题解

考虑将 $1$ 作为根，那么之后每条边都可以看成是一个点和其父亲的连边。

建立二分图，左边是点 $2 \sim n$，右边是子集 $1 \sim n - 1$，若点 $i$ 在子集 $j$ 中则连边，那么如果有解就必须存在完备匹配。

任取一组完备匹配，从 $1$ 开始构造树。一开始将 $1$ 所在的所有点集的匹配点的父亲设为 $1$，然后从这些点递归下去。

如果递归到了所有点，则构造出了一组解，否则说明二分图不连通，从而一定无解。

Dinic 求二分图匹配，时间复杂度 $\mathcal O(m \sqrt n)$。

代码

namespace Dinic {
	const int N = 2e5 + 7, M = 2e6 + 7;
	const ll inf = 1e18;
	int n, S, T, d[N];
	int h[N], hi[N], e[M], t[M], tot;
	ll f[M], mxf;

	inline void add(int x, int y, ll z, bool o = 1) {
		e[++tot] = y, f[tot] = z, t[tot] = h[x], h[x] = tot;
		if (o) add(y, x, 0, 0);
	}

	inline bool bfs() {
		for (int i = 1; i <= n; i++) d[i] = 0;
		queue<int> q;
		q.push(S), d[S] = 1;
		while (q.size()) {
			int x = q.front();
			q.pop();
			for (int i = h[x]; i; i = t[i]) {
				int y = e[i];
				ll z = f[i];
				if (d[y] || !z) continue;
				q.push(y), d[y] = d[x] + 1;
				if (y == T) return 1;
			}
		}
		return 0;
	}

	ll dfs(int x, ll now = inf) {
		if (x == T) return now;
		ll rst = now;
		for (int &i = hi[x]; i; i = t[i]) {
			int y = e[i];
			ll z = f[i];
			if (d[y] != d[x] + 1 || !z) continue;
			ll k = dfs(y, min(z, rst));
			if (!k) d[y] = 0;
			else f[i] -= k, f[i^1] += k, rst -= k;
			if (!rst) break;
		}
		return now - rst;
	}

	inline void main() {
		while (bfs()) {
			for (int i = 1; i <= n; i++) hi[i] = h[i];
			ll now;
			while ((now = dfs(S))) mxf += now;
		}
	}

	inline void init(int _n, int _S, int _T) {
		n = _n, S = _S, T = _T, tot = 1, mxf = 0;
		for (int i = 1; i <= n; i++) h[i] = 0; 
	}
}
using Dinic::add;

const int N = 1e5 + 7;
int n, f[N], fa[N], id[N];
set<int> e[N], g[N];
bool v[N];
pi ans[N];

int main() {
	rd(n), Dinic::init(2 * n, 1, 2 * n);
	for (int i = 1, c, x; i < n; i++) {
		add(1, i + 1, 1), add(i + n, 2 * n, 1);
		rd(c);
		while (c--) {
			rd(x), e[i].insert(x), g[x].insert(i);
			if (x == 1) continue;
			add(x, i + n, 1);
		}
	}
	Dinic::main();
	if (Dinic::mxf != n - 1) return print(-1), 0;
	for (int x = 1; x < n; x++)
		for (int i = Dinic::h[x+n]; i; i = Dinic::t[i])
			if (Dinic::e[i] <= n && Dinic::f[i]) f[x] = Dinic::e[i];
	queue<int> q;
	q.push(1);
	while (q.size()) {
		int x = q.front();
		q.pop();
		for (int y : g[x])
			if (!v[y]) v[y] = 1, fa[f[y]] = x, id[f[y]] = y, q.push(f[y]);
	}
	for (int i = 1; i < n; i++)
		if (!v[i]) return print(-1), 0;
	for (int i = 2; i <= n; i++) ans[id[i]] = mp(fa[i], i);
	for (int i = 1; i < n; i++) print(ans[i].fi, ans[i].se);
	return 0;
}