AtCoder Grand Contest 037 题解

AtCoder Grand Contest 037

Dividing a String

可以证明划分出来的段长度不超过 $2$ ，于是 $\mathcal O(n)$ DP 即可。

const int N = 2e5 + 7, inf = 1e9;
int n, f[N][2];
char s[N];

int main() {
	rds(s, n), f[0][1] = -inf;
	for (int i = 1; i <= n; i++) {
		f[i][0] = f[i][1] = -inf;
		if (i == 1 || s[i] != s[i-1])
			f[i][0] = max(f[i][0], f[i-1][0] + 1);
		f[i][0] = max(f[i][0], f[i-1][1] + 1);
		if (i > 1) f[i][1] = max(f[i][1], f[i-2][0] + 1);
		if (i > 3 && s[i] != s[i-2] && s[i-1] != s[i-3])
			f[i][1] = max(f[i][1], f[i-2][1] + 1);
	}
	print(max(f[n][0], f[n][1]));
	return 0;
}

RGB Balls

最小值直接贪心，方案数把每次的选择数量乘起来，最后乘上 $n!$ 。

const int N = 3e5 + 7;
int n, r, g, b, rg, gb, br;
char c;
modint ans = 1;

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) ans *= i;
	for (int i = 0; i < 3 * n; i++) {
		rdc(c);
		switch (c) {
			case 'R' : {
				if (gb) ans *= gb--;
				else if (g) ans *= g--, ++rg;
				else if (b) ans *= b--, ++br;
				else ++r;
				break;
			}
			case 'G' : {
				if (br) ans *= br--;
				else if (b) ans *= b--, ++gb;
				else if (r) ans *= r--, ++rg;
				else ++g;
				break;
			}
			case 'B' : {
				if (rg) ans *= rg--;
				else if (r) ans *= r--, ++br;
				else if (g) ans *= g--, ++gb;
				else ++b;
				break;
			}
		}
	}
	print(ans);
	return 0;
}

Numbers on a Circle

倒着考虑，如果一个位置比左右两边都大，那么这个位置上的数必然是通过一次对这个位置的操作得到的。

于是可以每次从最大值开始不断往下减（除），中途判一下无解的情况，时间复杂度大概是 $\mathcal O(n \log n \log w)$ 。

#define Fail return print(-1), 0
const int N = 2e5 + 7;
int n, a[N], b[N];
ll ans;

int main() {
	rd(n), rda(a, n), rda(b, n);
	pq<pi> q;
	for (int i = 1; i <= n; i++)
		if (a[i] != b[i]) q.push(mp(b[i], i));
	while (q.size()) {
		int x = q.top().se, l = x == 1 ? n : x - 1, r = x == n ? 1 : x + 1;
		q.pop();
		int t = (b[x] - max(max(b[l], b[r]), a[x])) / (b[l] + b[r]);
		ans += t, b[x] -= t * (b[l] + b[r]);
		while (b[x] > max(max(b[l], b[r]), a[x])) ++ans, b[x] -= b[l] + b[r];
		if (b[x] < a[x]) Fail;
		if (b[x] != a[x]) q.push(mp(b[x], x));
	}
	print(ans);
	return 0;
}

Sorting a Grid

题意

给定一个 $n \times m$ 的矩阵，每个位置上的数 $\in[1,nm]$ ，且每个数恰好出现一次。
你可以进行三次操作：
1. 将每一行重排。
2. 将每一列重排。
3. 再将每一行重排。
要求最终矩阵被还原为有序矩阵。
$n,m \le 100$ 。

题解

倒着考虑，第三步会将同一行的打乱，因此同一行的顺序不重要，于是可以将每个数的行数看成它们的颜色。

第二步会将同一列的打乱，因此第二步之前每一列应该恰好每种颜色各有一个。

于是问题变成了，在一个矩阵中有 $n$ 种颜色，每种颜色恰好 $m$ 个，要通过重排每一行，实现每一列恰好每种颜色各一个。

考虑二分图匹配模型，左边为 $n$ 行，右边为 $n$ 种颜色，对于每一行的每种颜色连边，

然后找 $m$ 次最大匹配，将第 $i$ 的匹配作为第 $i$ 列。根据 Hall 定理，每次匹配必然是完美匹配。

使用匈牙利算法时间复杂度为 $\mathcal O(n^2m^2)$ 。

代码

const int N = 107;
int n, m, a[N][N], b[N][N], f[N], g[N], v[N], p[N];

bool dfs(int i, int k) {
	for (int j = 1; j <= m; j++)
		if (a[i][j]) {
			int x = (a[i][j] - 1) / m + 1;
			if (v[x] != k) {
				v[x] = k;
				if (!f[x] || dfs(f[x], k))
					return f[x] = i, g[i] = j, 1;
			}
		}
	return 0;
}

int main() {
	rd(n, m);
	for (int i = 1; i <= n; i++)
		rda(a[i], m);
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= n; i++)
			dfs(i, (i - 1) * m + (j - 1) + 1);
		for (int i = 1; i <= n; i++)
			b[i][j] = a[i][g[i]], a[i][g[i]] = f[i] = 0;
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			print(b[i][j], " \n"[j==m]);
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= n; i++)
			p[(b[i][j]-1)/m+1] = b[i][j];
		for (int i = 1; i <= n; i++)
			b[i][j] = p[i];
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			print(b[i][j], " \n"[j==m]);
	return 0;
}

Reversing and Concatenating

题意

给定一个长度为 $n$ 的字符串 $s$ 。
你可以进行如下操作 $k$ 次：
- 将 $s$ 变成 $ss^r$ 的一个长度为 $n$ 的子串。
要求最终 $s$ 的字典序最小。
$n \le 5 \times 10^3$ ， $k \le 10^9$ 。

题解

另 $s$ 中最小的字符为 $c$ ，设 $s$ 中最长连续的 $c$ 的长度为 $l$ ，则最终的 $s$ 内我们至少可以构造出开头连续 $\min(n, 2^{k-1}l)$ 个 $c$ 的串。

若 $\min$ 是取到 $2^{k-1}l$ ，则意味着后面还有一些字符要确定，可以发现后面的字符一定是 $ss^r$ 的一个后缀，由于数据范围很小，直接暴力找最小后缀即可，时间复杂度 $\mathcal O(n^2)$ 。

代码

const int N = 1e4 + 7;
int n, k, a[N], l, w;
char s[N], c, ans[N];

inline void upd(int p) {
	bool ok = 1;
	for (int i = 1; i <= w; i++) {
		if (ans[i] > s[p - i + 1]) break;
		if (ans[i] < s[p - i + 1]) {
			ok = 0;
			break;
		}
	}
	if (!ok) return;
	for (int i = 1; i <= w; i++)
		ans[i] = s[p - i + 1];
}

int main() {
	rd(n, k), rds(s, n);
	for (int i = 1; i <= n; i++)
		s[n + n + 1 - i] = s[i];
	c = *min_element(s + 1, s + n + n + 1);
	for (int i = 1; i <= n + n; i++)
		a[i] = s[i] == c ? a[i - 1] + 1 : 0;
	l = *max_element(a + 1, a + n + n + 1);
	if (k >= 14 || ((n - 1) >> (k - 1)) + 1 <= l) {
		for (int i = 1; i <= n; i++) printc(c);
		return 0;
	}
	w = n - (l << (k - 1));
	ans[1] = 'z' + 1;
	for (int i = 1; i <= n; i++)
		if (a[n + i] == l) upd(n + i - l);
	for (int i = 1; i <= (l << (k - 1)); i++) printc(c);
	prints(ans, w);
	return 0;
}

Counting of Subarrays

题意

给定一个正整数序列 $a_{1\dots n}$ 和一个正整数 $l$ ，求 $a$ 有多少个非空子段 $a_{i\dots j}$ ，满足存在正整数 $k$ 使得 $a_{i \dots j}$ 属于等级 $k$ 。
对于一个正整数序列 $a$ 和正整数 $k,l$ ，称 $a$ 属于等级 $k$ 当且仅当满足以下两个条件至少一个：
- $a$ 的长度为 $1$ 且唯一的元素为 $k$ 。
- 当 $k \ne 1$ 时，可以将 $a$ 分成不少于 $l$ 个非空子段，使得每一段都属于等级 $k-1$ 。
$n \le 2 \times 10^5$ ， $2 \le l \le n$ ， $a_{i} \le 10^9$ 。

题解

首先考虑如何判断一个序列 $s$ 是否合法（即存在正整数 $k$ 使得 $s$ 属于等级 $k$ ）。

考虑将定义的过程反着推，相当于每次对于 $s$ 中最小的元素 $x$ ，找到所有 $x$ 的连续段。设一个连续段的长度为 $t$ ，若 $t < l$ 则判定为不合法，否则将这一段合并为 $\lfloor \frac tl \rfloor$ 个 $x + 1$ ，直到 $s$ 中只剩下一种元素。注意这个元素一定是一开始 $s$ 中的最大值，同时我们不再合并这个元素。

设 $s$ 的最大值为 $w$ ，此时分三种情况：

若 $w$ 的数量为 $1$ ，这种情况当且仅当原序列的长度为 $1$ ， $s$ 属于等级 $w$ ，合法。
若 $w$ 的数量不少于 $l$ ， $s$ 属于等级 $w + 1$ ，合法。
不合法。

考虑将这个过程搬到整个序列 $a$ 中。

首先对于第一种情况直接特判。

然后从小到大考虑 $a$ 中出现过的值 $w$ ，当考虑到 $w$ 时，我们需要计算 $a$ 中所有最大值为 $w$ 的子段的中合法的数量，这个过程可以用一个单调栈维护。

即我们现在有一个序列 $s = s_0ws_1w \cdots ws_m$ ，其中 $s_i$ 为一个所有元素都 $<w$ 的序列，我们要求出这个序列中有多少个子段满足其属于等级 $w+1$ 。

考虑对于一个序列 $s$ 维护以下几个信息（其中 $w$ 为 $s$ 中的最大值）：

$f_{s,i}$ 表示 $s$ 中至多能合并出 $i$ 个 $w$ 的前缀个数。
$g_{s,i}$ 表示 $s$ 中至多能合并出 $i$ 个 $w$ 的后缀个数。
$h_{s}$ 表示 $s$ 至多能合并出的 $w$ 的个数，这个可以根据 $f,g$ 求出。

根据 $f_s,g_s,h_s$ ，我们可以简单地求出对于任意一个 $w^\prime > w$ ， $s$ 中至多能合并出 $i$ 个 $w^\prime$ 的前/后缀个数，以及 $s$ 至多能合并出的 $w^\prime$ 的个数。

假设我们现在对于 $s = s_0ws_1w \cdots ws_m$ 中的所有 $s_i$ 都求出了 $f_{s_i},g_{s_i},h_{s_i}$ ，则我们首先可以求出 $s_i$ 中至多能合并出 $i$ 个 $w$ 的前/后缀个数，以及 $s$ 至多能合并出的 $w$ 的个数。然后使用 Two pointers 在 $\mathcal O(m + \sum_{i=0}^m h_{s_i})$ 的时间复杂度下求出 $s$ 的答案，以及 $f_s,g_s,h_s$ 。

接下来考虑一下时间复杂度，乍看下去可能时间复杂度非常高，但如果我们只记录不为 $0$ 的 $f_s,g_s$ ，状态总数是 $\mathcal O(n \log n)$ 的。

这是因为对于 $a$ 中的一个元素 $w$ ，它至多为最大值为 $w$ 的极长子段提供 $1$ 的状态数，为最大值为 $w+1$ 的极长子段提供 $\frac1l$ 的状态数，为最大值为 $w+2$ 的极长子段提供 $\frac1{l^2}$ 的状态数，因此总状态数实际上是 $\mathcal O(n \log n)$ 的。

精细实现的话，总时间复杂度为 $\mathcal O(n \log n)$ 。

代码

const int N = 2e5 + 7;
int n, l, s[N], t, f[N], g[N], sf[N], sg[N];
ll ans;

inline void pop() {
	int k = 1, x = s[t];
	while (s[t-1] == x) --t, ++k;
	--t;
	if (k < l) {
		while (t) pop();
		return;
	}
	int w = k / l;
	for (int i = 1; i <= k; i++)
		sf[i] = sf[i-1] + f[i+t], sg[i] = sg[i-1] + g[i+t];
	for (int i = l; i <= k; i++)
		ans += 1ll * sf[i-l+1] * g[i+t];
	for (int i = 1; i <= w; i++)
		f[t+i] = sf[k-l*(w-i+1)+1] - sf[max(k-l*(w-i+2)+1,0)],
		g[t+i] = sg[min(l*(i+1)-1,k)] - sg[l*i-1];
	for (int i = l, s = 0; i <= w; i++)
		ans -= 1ll * (s += f[t+i-l+1]) * g[t+i];
	for (int i = 1; i <= w; i++)
		s[++t] = x + 1;
}

int main() {
	rd(n, l), ans = n;
	for (int i = 1, x; i <= n; i++) {
		rd(x);
		while (t && s[t] < x) pop();
		s[++t] = x, f[t] = g[t] = 1;
	}
	while (t) pop();
	print(ans);
	return 0;
}