Visits: 380

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;
}