AtCoder Grand Contest 026 题解

AtCoder Grand Contest 026

Colorful Slimes 2

对于每个同色连续段，设长度为 $c$ ，则对答案有贡献 $\lfloor \frac c2 \rfloor$ 。

const int N = 107;
int n, a[N], ans;

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

rng_10s

细节题，各种情况想清楚就行了。

最后大概是发现会在一个相邻点长为 $\gcd(d - b, b)$ 的若干个点上走成一个环，考虑这个环上 $> c$ 的最小位置是否 $\ge b$ 即可。

inline bool pd() {
	ll a, b, c, d;
	rd(a, b), rd(c, d);
	if (d < b) return 0;
	a -= b;
	if (a > c) {
		a -= (a - c) / b * b;
		if (a > c) a -= b;
	}
	while (a < 0) return 0;
	if (d == b) return 1;
	a += (c + 1 - a) / (d - b) * (d - b);
	while (a <= c) a += d - b;
	ll g = __gcd(d - b, b);
	a -= (a - c - 1) / g * g;
	while (a - g > c) a -= g;
	return a >= b;
}

int main() {
	int T;
	rd(T);
	while (T--) prints(pd() ? "Yes" : "No");
	return 0;
}

String Coloring

前 $n$ 个字符状态确定了整个字符串就确定了，因此前 $n$ 个字符状压，后 $n$ 个字符 $\mathcal O(n^2)$ DP 即可，时间复杂度 $\mathcal O(2^nn^2)$ 。

const int N = 19;
int n, p, q;
char s[N], t[N], a[N], b[N];
ll f[N][N], ans;

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rdc(s[i]);
	for (int i = 1; i <= n; i++) rdc(t[i]);
	for (int i = 0; i < 1 << n; i++) {
		p = q = 0;
		for (int j = 0; j < n; j++)
			if (i >> j & 1) a[++p] = s[j+1];
			else b[++q] = s[j+1];
		reverse(a + 1, a + p + 1);
		reverse(b + 1, b + q + 1);
		for (int j = 0; j <= n; j++)
			for (int k = 0; k <= p; k++)
				f[j][k] = 0;
		f[0][0] = 1;
		for (int j = 0; j < n; j++)
			for (int k = 0; k <= j; k++)
				if (f[j][k]) {
					if (k < p && t[j+1] == a[k+1])
						f[j+1][k+1] += f[j][k];
					if (j - k < q && t[j+1] == b[j-k+1])
						f[j+1][k] += f[j][k];
				}
		ans += f[n][p];
	}
	print(ans);
	return 0;
}

Histogram Coloring

题意

有 $n$ 列格子排成一排，第 $i$ 列的高度为 $h_i$ 。
每个格子都可以被染成红色或蓝色，但要求所有 $2 \times 2$ 的四个格子中恰好两红两蓝。
求方案数。
$n \le 100$ ， $h_i \le 10^9$ ，答案对 $10^9+7$ 取模。

题解

定义第 $i$ 列第 $j$ 行的颜色为 $a_{i,j}$ 。

对于 $i,i+1$ 两列中 $j \le \min(h_i,h_{i+1})$ 的部分，染色情况有两种：

$a_{i,j} \ne a_{i+1,j}$ ，即两列颜色相反。
$a_{i,j} \ne a_{i,j-1}$ ，即同列两色交替。

设 $f_{i,j}$ 表示考虑前 $i$ 列，第 $i$ 列从下往上有 $j$ 个位置满足两色交替且第 $j+1$ 个位置不满足。

第二维可以只保留所有 $h$ 值的位置，时间复杂度可以做到 $\mathcal O(n^2)$ 。

然而还可以更优。

建出根为最小值的笛卡尔树，设 $f_{l,r,i,j,0/1}$ 表示笛卡尔树上的节点 $[l,r]$ 在高度 $\ge h = \min h_{l\dots r}$ 的部分，其中 $a_{l,h} = i$ ， $a_{r,h} = j$ ，是否在同一列为两色交替的方案数。

实现时可以将 $h$ 从大到小排序之后，每次相当于对于一列 $t$ 合并 $[l,t-1]$ 和 $[t+1,r]$ 两个状态，时间复杂度 $\mathcal O(n \log n)$ 。

代码

const int N = 1e5 + 7;
int n, h[N], p[N], pl[N], pr[N], w[N];

struct DP {
	modint a[2][2][2];
	inline DP() {
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				for (int k = 0; k < 2; k++)
					a[i][j][k] = 0;
	}
	inline modint (* operator [] (int i)) [2] {
		return a[i];
	}
	inline friend DP operator + (DP a, DP b) {
		DP c;
		for (int li = 0; li < 2; ++li)
			for (int ri = 0; ri < 2; ++ri)
				for (int lj = 0; lj < 2; ++lj)
					for (int rj = 0; rj < 2; ++rj)
						for (int lk = 0; lk < 2; ++lk)
							for (int rk = 0; rk < 2; ++rk)
								c[li][rj][lk|rk|(lj==ri)] += a[li][lj][lk] * b[ri][rj][rk];
		return c;
	}
} f[N];

void work(int o, int x) {
	if (w[o] == x) return;
	DP now;
	int t = (w[o] ^ x) & 1;
	modint k = (modint)2 ^ (w[o] - x - 1);
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			now[i][j][0] = (f[o][i][j][0] + f[o][i^1][j^1][0]) * k,
			now[i][j][1] = f[o][i^t][j^t][1];
	f[o] = now;
}

int main() {
	rd(n), rda(h, n), iota(p + 1, p + n + 1, 1);
	sort(p + 1, p + n + 1, [&](int i, int j) { return h[i] > h[j]; });
	for (int o = 1; o <= n; o++) {
		int i = p[o], L = i, R = i;
		DP now;
		now[0][0][0] = now[1][1][0] = 1;
		if (pl[i-1]) L = pl[i-1], pr[L] = pl[i-1] = 0, work(L, h[i]), now = f[L] + now;
		if (pr[i+1]) R = pr[i+1], pr[i+1] = pl[R] = 0, work(i + 1, h[i]), now = f[i+1] + now;
		f[L] = now, pr[L] = R, pl[R] = L, w[L] = h[i];
	}
	work(1, 1);
	modint ans;
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				ans += f[1][i][j][k];
	print(ans);
	return 0;
}

Synchronized Subsequence

题意

给定一个包含 $n$ 个 a 和 $n$ 个 b 的字符串。
你要从中选出一个子序列，要求对于每个 $i \in [1,n]$ ，该子序列要么同时包含第 $i$ 个 a 和第 $i$ 个 b，要么同时不含第 $i$ 个 a 和第 $i$ 个 b。
你还要最大化这个子序列的字典序。
$n \le 3 \times 10^3$ 。

题解

令 $a_i$ 表示第 $i$ 个 a 的位置， $b_i$ 表示第 $i$ 个 b 的位置。

考虑从后往前 DP，设 $f_i$ 表示只考虑所有的 $a_{i \dots n}$ 和 $b_{i \dots n}$ 的情况下的字典序最大的串，那么答案就为 $f_1$ 。

考虑转移， $f_i$ 会从 $a_i$ 和 $b_i$ 都保留或者都删掉两个方向转移来。

如果都删掉，就直接从 $f_{i+1}$ 转移来；如果都保留，分类讨论：

$a_i < b_i$ ：
由于要让字典序尽量大，所以 $a_i$ 到 $b_i$ 之间所有的 a 都应该被删掉，而所有的 b 因为都在第 $i$ 个 b 之前所以不用考虑。
即 $f_i = \mathtt{ab} + f_k$ ，其中 $k$ 为完全在 $b_i$ 之后的第一对 $a_k, b_k$ 的 $k$ ，可以预处理出来。
$a_i > b_i$ ：
由于要让字典序尽量大，所以 $a_i$ 到 $b_i$ 之间所有的 b 都应该被保留，而所有的 a 都不用考虑。
而要保留这些 b，又会导致往后包含了更多的 b，同理被包含的 b 也应该被保留，连锁反应会一直进行下去，直到某一次不包含了更多的 b 为止。
即 $f_i = s + f_k$ ，其中 $s$ 为上述连锁反应所涉及到的所有字符，而 $k$ 为这之后的第一对 $a_k,b_k$ 的 $k$ ，可以暴力找。

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

代码

const int N = 6e3 + 7;
int n, a[N], b[N], d[N], p[N];
char s[N];
string f[N];

int main() {
	rd(n), rds(s, n);
	for (int i = 1, j = 0, k = 0; i <= n; i++)
		if (s[i] == 'a') a[d[i]=++j] = i;
		else b[d[i]=++k] = i;
	a[n+1] = b[n+1] = n + 1, d[n+1] = (n >> 1) + 1, n >>= 1;
	for (int i = 1, j = 0; i <= n + 1; i++)
		while (j < min(a[i], b[i])) p[++j] = i;
	for (int i = n; i; i--) {
		if (a[i] > b[i]) {
			int j = b[i];
			while (b[d[j]] < a[d[j]] && (d[j] <= i || b[d[j]] < a[d[j]-1])) {
				if (d[j] >= i) f[i] += s[j];
				++j;
			}
			f[i] += f[d[j]];
		} else f[i] = "ab" + f[p[b[i]+1]];
		f[i] = max(f[i], f[i + 1]);
	}
	prints(f[1]);
	return 0;
}

Manju Game

题意

有 $n$ 个盒子，第 $i$ 个盒子里装有 $a_i$ 个金币。
两个人轮流选择盒子并拿走其中的金币，共选择 $n$ 轮，规则如下：
- 如果与上一轮对方选择的盒子相邻的盒子中存在没有被选过的盒子，则必须选择这些盒子中的某一个。
- 如果这是第一轮，或者与上一轮对方选择的盒子相邻的盒子中不存在没有被选过的盒子，则可以随便选择一个没有被选过的盒子。
双方都希望自己得到的金币尽量多，问最优策略下双方最终获得的金币数量。
$n \le 3 \times 10^5$ ， $a_i \le 10^3$ 。

题解

首先把序列交替染色，奇数位上染黑，偶数位上染白，设黑色位上的数之和为 $B$ ，白色位上的数之和为 $W$ 。

如果 $n$ 为偶数，那么：

先手能保证至少获得 $\max(W, B)$ 分，他只需要第一步选择 $a_1$ 就能获得 $B$ 分，第一步选择 $a_n$ 就能获得 $W$ 分。
后手能保证至少获得 $\min(W, B)$ 分，若先手第一步选择黑色位，那么后手往左走就可以保证走到 $1$ 后变成先手，于是可以拿到 $W$ 分；反之亦然。

由于 $\max(W, B) + \min(W, B) = W + B$ ，因此最优策略下一定是先手获得 $\max(W, B)$ 分后手获得 $\min(W, B)$ 分。

接下来考虑 $n$ 为奇数的情况，首先可以发现的是先手可以保证至少获得 $B$ 分。

考虑先手第一步的选择：

如果选择黑色位，则类似 $n$ 为偶数的情况可以发现后手可以保证至少获得 $W$ 分。
如果选择白色位，则后手可以选择往左或往右获得那一边的所有黑色位，到了另一边先手仍然是先手，于是递归下去。

因此将每次先手需要决策（即可以选择黑白）时的策略记下来，一定是若干个白最后一个黑。

我们发现这些白色位的具体位置是先手可以决定的，然而黑色位所在的被白色位隔开的区间是后手决定的。

同时这种情况下先手的得分为这个区间内所有的黑色位，以及这个区间外所有的白色位，即 $B_{in} + W_{out} = W+B_{in}-W_{in}$ ；后手相反。因此后手一定会选择所有区间中 $B_{in}-W_{in}$ 最小的一个。

于是问题变成选择若干的白色位，使得被这些白色位隔开的区间的 $B_{in}-W_{in}$ 的最小值最大。

于是可以二分答案，二分一个 $X$ ，判断是否存在一种选择白色位的方案使得所有区间的 $B_{in} - W_{in} \ge X$ ，类似最大字段和贪心（或 DP）即可。

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

代码

const int N = 3e5 + 7;
int n, a[N], B, W;

inline bool pd(int X) {
	int t = 0;
	for (int i = 1; i <= n; i++)
		if (i & 1) t += a[i];
		else if (t >= X) t = max(t - a[i], 0);
		else t -= a[i];
	return t >= X;
}

int main() {
	rd(n), rda(a, n);
	for (int i = 1; i <= n; i++)
		if (i & 1) B += a[i];
		else W += a[i];
	if (!(n & 1)) return print(max(B, W), min(B, W)), 0;
	int l = 0, r = B;
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (pd(mid)) l = mid;
		else r = mid - 1;
	}
	print(W + l, B - l);
	return 0;
}