JOI Final 2019 题解

JOI Final 2019

勇者ビ太郎 (Bitaro the Brave)

前缀和计数一下，时间复杂度 $\mathcal O(nm)$。

const int N = 3e3 + 7;
int n, m, c[2][N][N];
char s[N][N];
ll ans;

int main() {
	rd(n, m);
	for (int i = 1; i <= n; i++) rds(s[i], m);
	for (int i = 1; i <= n; i++)
		for (int j = m; j; j--)
			c[0][i][j] = c[0][i][j+1] + (s[i][j] == 'O');
	for (int j = 1; j <= m; j++)
		for (int i = n; i; i--)
			c[1][i][j] = c[1][i+1][j] + (s[i][j] == 'I');
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			ans += (s[i][j] == 'J') * c[0][i][j] * c[1][i][j];
	print(ans);
	return 0;
}

展覧会 (Exhibition)

sort + 贪心，时间复杂度 $\mathcal O(n \log n)$。

const int N = 1e5 + 7;
int n, m, c[N], ans;
pi a[N];

int main() {
	rd(n, m);
	for (int i = 1; i <= n; i++) rd(a[i].se, a[i].fi);
	sort(a + 1, a + n + 1);
	rda(c, m);
	sort(c + 1, c + m + 1);
	for (int i = m, j = n; i && j; i--) {
		while (j && a[j].se > c[i]) --j;
		if (j) ++ans, --j;
	}
	print(ans);
	return 0;
}

たのしいたのしいたのしい家庭菜園 (Growing Vegetables is Fun 3)

考虑确定了最终的字符串后如何计算最少交换次数。

首先同一个字符的相对顺序不变，于是可以一一对应起来。

考虑计算逆序对的个数，由于每次交换可以使逆序对个数减 $2$，因此答案就是逆序对个数除以 $2$。

把这个玩意儿套到一个 $\mathcal O(n^3)$ 的 DP 上去即可。

const int N = 407, inf = 1e9;
int n, p[3][N], f[3][N][N][N], a[N], b[N], c[N];
char s[N];

inline void upd(int &x, int y) {
	x = min(x, y);
}

int main() {
	rd(n), rds(s, n);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++) p[j][i] = p[j][i-1];
		switch (s[i]) {
			case 'R' : a[++a[0]] = i, ++p[0][i]; break;
			case 'G' : b[++b[0]] = i, ++p[1][i]; break;
			case 'Y' : c[++c[0]] = i, ++p[2][i]; break;
		}
	}
	for (int i = 0; i < 3; i++)
		for (int x = 0; x <= a[0]; x++)
			for (int y = 0; y <= b[0]; y++)
				for (int z = 0; z <= c[0]; z++)
					f[i][x][y][z] = inf;
	if (a[0]) f[0][a[0]-1][b[0]][c[0]] = abs(n - a[a[0]]);
	if (b[0]) f[1][a[0]][b[0]-1][c[0]] = abs(n - b[b[0]]);
	if (c[0]) f[2][a[0]][b[0]][c[0]-1] = abs(n - c[c[0]]);
	for (int i = n - 1; i; i--)
		for (int x = 0; x <= a[0] && x <= i; x++)
			for (int y = 0; y <= b[0] && x + y <= i; y++) {
				int z = i - x - y;
				if (z > c[0]) continue;
				if (x) upd(f[0][x-1][y][z], min(f[1][x][y][z], f[2][x][y][z]) + abs(p[1][a[x]] - y) + abs(p[2][a[x]] - z));
				if (y) upd(f[1][x][y-1][z], min(f[0][x][y][z], f[2][x][y][z]) + abs(p[0][b[y]] - x) + abs(p[2][b[y]] - z));
				if (z) upd(f[2][x][y][z-1], min(f[0][x][y][z], f[1][x][y][z]) + abs(p[0][c[z]] - x) + abs(p[1][c[z]] - y));
			}
	int ans = min(min(f[0][0][0][0], f[1][0][0][0]), f[2][0][0][0]);
	print(ans == inf ? -1 : (ans >> 1));
	return 0;
}

コイン集め (Coin Collecting)

依然是贪心，先把每个方块移到离它最近的范围内的位置，然后调整一下即可，时间复杂度 $\mathcal O(n)$。

const int N = 1e5 + 7;
int n, c[N][3];
ll ans;

int main() {
	rd(n);
	for (int i = 1, x, y; i <= (n << 1); i++) {
		rd(x, y);
		if (x < 1) ans += 1 - x, x = 1;
		if (x > n) ans += x - n, x = n;
		if (y < 1) ans += 1 - y, y = 1;
		if (y > 2) ans += y - 2, y = 2;
		++c[x][y];
	}
	for (int i = 1, c1 = 0, c2 = 0; i <= n; i++) {
		c1 += c[i][1] - 1, c2 += c[i][2] - 1;
		while (c1 < 0 && c2 > 0) ++c1, --c2, ++ans;
		while (c1 > 0 && c2 < 0) --c1, ++c2, ++ans;
		if (i < n) ans += abs(c1) + abs(c2);
	}
	print(ans);
	return 0;
}

珍しい都市 (Unique Cities)

关于 $x$ 合法的城市一定在以 $x$ 为根的最长链上，这条最长链的另一端一定是直径的某一端。

因此我们对于直径的两端各算一次答案，取 $\max$ 即为最终的答案。

考虑对于直径的一端如何计算答案，将这个点设为根，然后长链剖分。

全局上用一个栈记录从根到每个点的路径上合法的点，用一个桶维护答案。

处理到一个点时，优先递归重儿子，因此要先把栈中和他距离不大于深度最大的轻儿子的点退栈。接着再递归所有轻儿子，把栈中和他距离不大于重儿子的点退栈。

这样可以保证每个点的贡献被删掉后不可能还需要加回来。

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

const int N = 2e5 + 7;
int n, m, a[N], ans[N];
vi e[N];

int rt, d[N];

void dfs1(int x, int fa) {
	d[x] = d[fa] + 1;
	if (d[x] > d[rt]) rt = x;
	for (int y : e[x])
		if (y != fa) dfs1(y, x);
}

int f[N], son[N][2];
#define s0 son[x][0]
#define s1 son[x][1]

void dfs2(int x, int fa) {
	d[x] = d[fa] + 1;
	s0 = s1 = 0;
	for (int y : e[x])
		if (y != fa) {
			dfs2(y, x);
			if (f[y] > f[s1]) s1 = y;
			if (f[s1] > f[s0]) swap(s0, s1);
		}
	f[x] = f[s0] + 1;
}

int st[N], tp;
int c[N], cnt;

inline void ins(int x) {
	cnt += !c[x]++;
}

inline void del(int x) {
	cnt -= !--c[x];
}

void dfs3(int x, int fa) {
	if (fa) ins(a[fa]), st[++tp] = fa;
	if (s0) {
		while (tp && d[st[tp]] >= d[x] - f[s1]) del(a[st[tp--]]);
		dfs3(s0, x);
	}
	while (tp && d[st[tp]] >= d[x] - f[s0]) del(a[st[tp--]]);
	for (int y : e[x])
		if (y != fa && y != s0)
			dfs3(y, x);
	ans[x] = max(ans[x], cnt);
	if (st[tp] == fa) del(a[st[tp--]]);
}

inline void work(int x) {
	rt = x;
	dfs1(x, 0);
	dfs2(rt, 0);
	for (int i = 1; i <= m; i++) c[i] = 0;
	cnt = tp = 0;
	dfs3(rt, 0);
}

int main() {
	rd(n, m);
	for (int i = 1, x, y; i < n; i++)
		rd(x, y), e[x].pb(y), e[y].pb(x);
	rda(a, n);
	work(1), work(rt);
	for (int i = 1; i <= n; i++) print(ans[i]);
	return 0;
}