AtCoder Grand Contest 037 题解
Visits: 409
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]$,且每个数恰好出现一次。
- 你可以进行三次操作:
- 将每一行重排。
- 将每一列重排。
- 再将每一行重排。
- 要求最终矩阵被还原为有序矩阵。
- $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;
}