AtCoder Grand Contest 046 题解

作者: xht37 分类: 题解 发布时间: 2020-06-26 20:28

点击数:184

AtCoder Grand Contest 046

Takahashikun, The Strider

相当于要找到最小的正整数 $t$ 满足 $tx \equiv 0 \pmod {360}$,暴力即可。

int main() {
    int x;
    rd(x);
    int t = 1;
    while (1) {
        if (t * x % 360 == 0) {
            return print(t), 0;
        }
        ++t;
    }
    return 0;
}

Extension

$\mathcal O(n^2)$ DP,转移时容斥一下。

const int N = 3e3 + 7;
int a, b, c, d;
modint f[N][N];

int main() {
    rd(a, b), rd(c, d);
    f[a][b] = 1;
    for (int i = a; i <= c; i++)
        for (int j = b; j <= d; j++) {
            if (i == a && j == b) continue;
            f[i][j] = f[i-1][j] * j + f[i][j-1] * i - f[i-1][j-1] * (i - 1) * (j - 1);
        }
    print(f[c][d]);
    return 0;
}

Shift

设有 $t$ 个 $0$,相当于用这 $t$ 个 $0$ 将 $1$ 分成 $t+1$ 堆,然后可以进行 $k$ 次操作,每次操作把一个 $1$ 移到左边某一堆中,求最终的方案数。

考虑 DP,设 $f_{i,j,l}$ 考虑前 $i$ 堆,已经使用了 $k$ 次中的 $j$ 次,前 $i$ 堆中多了 $l$ 个 $1$ 的方案数。

转移时枚举第 $i+1$ 堆的变化量,时间复杂度 $\mathcal O(n^4)$,常数很小,注意特判 $t=0$ 的情况。

const int N = 307;
int n, k, c, t, x, p[N];
char s[N];
modint f[N][N][N], ans;

int main() {
    rds(s, n), rd(k);
    for (int i = 1; i <= n; i++) c += s[i] == '1';
    if (c == n) return print(1), 0;
    for (int i = 1; i <= n; i++)
        if (s[i] == '0') {
            ++t;
            int j = i;
            while (s[j-1] == '1') --j, ++p[t];
            x = i;
        }
    p[++t] = n - x;
    k = min(k, c - p[1]);
    for (int j = p[1]; j <= min(c, k + p[1]); j++)
        f[1][j-p[1]][j-p[1]] = 1;
    for (int i = 1; i < t - 1; i++)
        for (int j = 0; j <= k; j++)
            for (int l = 0; l <= j; l++)
                if (f[i][j][l].x)
                    for (int w = -min(p[i+1], l); w <= k - j; w++)
                        f[i+1][j+max(0,w)][l+w] += f[i][j][l];
    for (int j = 0; j <= k; j++)
        for (int l = 0; l <= min(j, p[t]); l++)
            ans += f[t-1][j][l];
    print(ans);
    return 0;
}

Secret Passage

设 $f_{i,j,k}$ 表示从 $s_{1\dots i}$ 中抽出 $j$ 个 $0$ 和 $k$ 个 $1$ 插入到 $s_{i+1\dots n}$ 中的方案数。

注意我们暂时先不考虑 $s_{1\dots i}$ 中能否抽出 $j$ 个 $0$ 和 $k$ 个 $1$,只进行计数。

这个 DP 可以 $\mathcal O(1)$ 转移,时间复杂度 $\mathcal O(n^3)$。

接下来的问题就是判断 $s_{1\dots i}$ 中能否抽出 $j$ 个 $0$ 和 $k$ 个 $1$,如果可以抽出,则将答案加上 $f_{i,j,k}$。

注意我们每次操作可以将一个字符插入到 $s_{i+1\dots n}$ 中,也可以将其依旧放在前面。

如果依旧放在前面,若后面依然需要把这个字符插入到 $s_{i+1 \dots n}$,那一定比不放在前面直接插入要劣,因此我们不妨要求依旧放在前面的字符唯一的用处是,删除这个字符,以让其他字符能够插入到后面。

于是设 $g_{i,j,k}$ 表示考虑 $s_{1\dots i}$ 已经抽出了 $j$ 和 $0$ 和 $k$ 个 $1$ 时,最多还剩下多少个可以被删除的字符。

这个 DP 同样可以 $\mathcal O(1)$ 转移,时间复杂度 $\mathcal O(n^3)$。

最终 $g_{i,j,k} \ge 0$ 的位置,以及其衍生出更劣的位置都是合法的位置。

总时间复杂度 $\mathcal O(n^3)$,注意最后需要减去空串。

const int N = 307;
int n;
char s[N];
modint f[N][N][N], ans;
int g[N][N][N];
bool v[N][N][N];

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

int main() {
    rds(s, n);
    f[n][0][0] = 1;
    for (int i = n; i; i--)
        for (int j = 0; j < i; j++)
            for (int k = 0; j + k < i; k++) {
                f[i-1][j][k] += f[i][j][k];
                if (s[i] == '0') f[i][j][k+1] += f[i][j][k];
                else f[i][j+1][k] += f[i][j][k];
            }
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            for (int k = 0; k <= n; k++)
                g[i][j][k] = -1;
    g[0][0][0] = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= (i >> 1); j++)
            for (int k = 0; j + k <= (i >> 1); k++)
                if (~g[i][j][k]) {
                    if (s[i+1] == '0') upd(g[i+1][j+1][k], g[i][j][k] - 1);
                    else upd(g[i+1][j][k+1], g[i][j][k] - 1);
                    if (i + 2 <= n) {
                        upd(g[i+2][j][k], g[i][j][k] + 1);
                        if (s[i+1] == '0' || s[i+2] == '0')
                            upd(g[i+2][j+1][k], g[i][j][k]);
                        if (s[i+1] == '1' || s[i+2] == '1')
                            upd(g[i+2][j][k+1], g[i][j][k]);
                    }
                }
    for (int i = 0; i <= n; i++)
        for (int j = n; ~j; j--)
            for (int k = n; ~k; k--) {
                v[i][j][k] = ~g[i][j][k];
                if (i) v[i][j][k] |= v[i-1][j][k];
                v[i][j][k] |= v[i][j+1][k];
                v[i][j][k] |= v[i][j][k+1];
            }
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= i; j++)
            for (int k = 0; j + k <= i; k++)
                if (v[i][j][k]) ans += f[i][j][k];
    print(ans - 1);
    return 0;
}

Permutation Cover

显然有解的充要条件为 $\max a_i \le 2 \cdot \min a_i$。

看见字典序最小,显然贪心枚举,不同之处在考虑每次加入一段排列(可能与之前的重合),问题转化成一个前缀是否合法。

设此时的前缀为 $S$,显然最后 $k$ 个为一个排列,设为 $p$,再设 $i$ 还要加入 $b_i$ 个。

此时跟一开始判定唯一的区别为 $\max b_i = 2 \cdot \min b_i + 1$ 时仍然可能有解,此时附加的充要条件为,设 $j$ 满足 $b_j = \max b_i$,$k$ 满足 $b_k = \min b_i$,则 $j$ 要在 $k$ 之前。

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

const int N = 1e3 + 7;
int n, m, s, a[N], p[N], q[N], ans[N];

void work(int k) {
    bool ok1 = 1, ok2 = 0;
    for (int i = 1; i <= k; i++) --a[p[i]];
    int mn = *min_element(a + 1, a + n + 1);
    int mx = *max_element(a + 1, a + n + 1);
    if (mn * 2 >= mx) {
        ok2 = 1;
        copy(p + 1, p + k + 1, q + 1);
        sort(q + 1, q + k + 1);
    } else if (mn * 2 + 1 == mx) {
        int k1 = 0, k2 = 0;
        static int f1[N], f2[N];
        for (int i = 1; i <= k; i++)
            ((a[p[i]] == mn || a[p[i]] == mx) ? f1[++k1] : f2[++k2]) = p[i];
        sort(f1 + 1, f1 + k1 + 1, [&](int i, int j) {
            if ((a[i] == mn) == (a[j] == mn)) return i < j;
            return (a[i] == mn) < (a[j] == mn);
        });
        sort(f2 + 1, f2 + k2 + 1);
        int x1 = 1, x2 = 1;
        for (int i = 1; i <= k; i++)
            if (x1 <= k1 && x2 <= k2)
                q[i] = f1[x1] < f2[x2] ? f1[x1++] : f2[x2++];
            else q[i] = x1 <= k1 ? f1[x1++] : f2[x2++];
        ok2 = 1;
        for (int i = k + 1; i <= n; i++)
            if (a[p[i]] == mn) ok2 = 0;
        ok2 |= !x1 || (a[f1[1]] == mx);
    }
    for (int i = 1; i <= k; i++) ++a[p[i]];
    if (!ok1 || !ok2) q[1] = 0;
}

inline bool pd(int *a, int *b) {
    int p = 1;
    while (a[p] == b[p]) ++p;
    return a[p] < b[p];
}

int main() {
    rd(n), rda(a, n);
    for (int i = 1; i <= n; i++) s += a[i];
    int mn = *min_element(a + 1, a + n + 1);
    int mx = *max_element(a + 1, a + n + 1);
    if (mn * 2 < mx) return print(-1), 0;
    iota(p + 1, p + n + 1, 1), work(n);
    for (int i = 1; i <= n; i++) --a[q[i]], ans[++m] = p[i] = q[i];
    while (m != s) {
        static int t[N];
        memset(t, 0, sizeof(t)), t[1] = n + 1;
        int k = 0;
        for (int i = 1; i <= n; i++) {
            work(i);
            if (q[1] && pd(q, t))
                k = i, copy(q + 1, q + i + 1, t + 1);
        }
        for (int i = 1; i + k <= n; i++) p[i] = p[i+k];
        for (int i = 1; i <= k; i++)
            ans[++m] = p[n-k+i] = t[i], --a[t[i]];
    }
    printa(ans, m);
    return 0;
}

Forbidden Tournament

咕.

发表评论

电子邮件地址不会被公开。 必填项已用*标注