AtCoder Grand Contest 030 题解

作者: xht37 分类: 题解 发布时间: 2020-07-09 08:17

点击数:126

AtCoder Grand Contest 030

Poisonous Cookies

$ans = \min(a+b+1,c) + b$。

int main() {
    ll a, b, c;
    rd(a, b, c);
    print(min(a + b + 1, c) + b);
    return 0;
}

Tree Burning

贪心,最终的方案一定是先走到某个点,然后后面每碰到一个点就调头。

前缀和一下就可以 $\mathcal O(n)$ 了。

const int N = 2e5 + 7;
int n, l, a[N], b[N];
ll sa[N], sb[N], ans;
#define Sa(l, r) (sa[r] - sa[l-1])
#define Sb(l, r) (sb[r] - sb[l-1])

inline ll calc() {
    ll ret = 0; 
    for (int i = n; i; i--) {
        int y = (n - i) >> 1, x = n - i - y;
        ret = max(ret, ((n - i) & 1 ? b[n-y] : a[n-x]) + (Sb(n - y + 1, n) + Sa(i, i + x - 1)) * 2);
    }
    return ret;
}

int main() {
    rd(l, n), rda(a, n);
    for (int i = 1; i <= n; i++)
        b[i] = l - a[i], sa[i] = sa[i-1] + a[i], sb[i] = sb[i-1] + b[i];
    ll now = calc();
    for (int i = 1; i <= n; i++) a[i] = b[n+1-i];
    for (int i = 1; i <= n; i++)
        b[i] = l - a[i], sa[i] = sa[i-1] + a[i], sb[i] = sb[i-1] + b[i];
    print(max(now, calc()));
    return 0;
}

Coloring Torus

题意

  • 对于一个 $n \times n$ 的网格,下标从 $0$ 开始,且第 $0$ 行在第 $n-1$ 行下面,列同理。
  • 你要用 $k$ 种颜色对这个矩阵染色,需要满足以下条件:
    • 每个格子被染成 $k$ 种颜色之一。
    • $k$ 种颜色都染了至少一个格子。
    • 对于任意两种颜色 $i,j$,满足所有颜色为 $i$ 的格子,其上下左右相邻的颜色 $j$ 的格子数相同(如果一个格子出现多次也会被计算多次)。
  • 给定 $k$,要求构造一种网格染色方案。
  • $k \le 10^3$,$n \le 500$。

题解

设颜色为 $[0,k-1]$,考虑 $n$ 为偶数的情况,构造 $c_{i,j} = ((i + j) \bmod n)$。

注意到如果将某一种颜色加入一个新颜色与之交替,同样是合法的。

因此特判 $k = 1$ 的情况,令 $n = 2\lceil \frac k4 \rceil$ 即可。

代码

int main() {
    int k;
    rd(k);
    if (k == 1) return prints("1\n1"), 0;
    int n = (k + 3) / 4 * 2;
    print(n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            int c = (i + j) % n;
            if ((i & 1) && c + n < k) c += n;
            print(c + 1, " \n"[j==n-1]);
        }
    return 0;
}

Inversion Sum

题意

  • 给定一个序列 $a_{1\dots n}$。
  • 有 $q$ 次操作,每次操作会交换两个位置上的数,你都可以选择是否执行。
  • 求所有情况下最终序列的逆序对数之和。
  • $n,q \le 3 \times 10^3$,答案对 $10^9+7$ 取模。

题解

令 $f_{i,j}$ 表示 $a_i > a_j$ 的概率,这样每次转移只会修改 $\mathcal O(n)$ 对 $(i,j)$,时间复杂度 $\mathcal O(n(n+q))$。

代码

const int N = 3e3 + 7;
const modint v2 = (modint)1 / 2;
int n, q, a[N];
modint f[N][N], ans;

inline void work(modint &x, modint &y) {
    x = y = (x + y) * v2;
}

int main() {
    rd(n, q), rda(a, n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            f[i][j] = a[i] > a[j];
    for (int i = 1, x, y; i <= q; i++) {
        rd(x, y), work(f[x][y], f[y][x]);
        for (int j = 1; j <= n; j++)
            if (j != x && j != y)
                work(f[j][x], f[j][y]), work(f[x][j], f[y][j]);
    }
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            ans += f[i][j];
    print(ans * ((modint)2 ^ q));
    return 0;
}

Less than 3

题意

  • 给定两个长度为 $n$ 的 $0/1$ 串 $s,t$,其中相同字符构成的连续段长度 $<3$。
  • 你可以对 $s$ 进行单点取反操作,要求每次操作后仍然满足相同字符构成的连续段长度 $<3$。
  • 求将 $s$ 变成 $t$ 的最小操作次数。
  • $n \le 5 \times 10^3$。

题解

注意到一段相同字符不会消失,否则一定会出现一个长度至少为 $3$ 的相同字符连续段。

考虑所有的 $01$ 分界线和 $10$ 分界线,则一次合法的操作只有下面三种情况:

  • 将某个分界线朝某个方向移动一个字符。
  • 将两端的分界线移出。
  • 在某一端加入一条分界线。

在过程中要求相邻两个分界线的距离为 $1$ 或 $2$。

考虑 $s$ 和 $t$ 分界线的对应关系,一共只有 $\mathcal O(n)$ 种,每种的答案就是对应分界线的距离之和。

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

代码

const int N = 5e3 + 7;
int n, a[N], b[N], c, d;
char s[N], t[N];

int main() {
    rd(n), rds(s, n), rds(t, n);
    for (int i = 1; i < n; i++)
        if (s[i] != s[i+1]) a[++c] = i;
    for (int i = 1; i < n; i++)
        if (t[i] != t[i+1]) b[++d] = i;
    int ans = 1e9;
    for (int i = -c - 1; i <= d + 1; i++)
        if ((i & 1) ^ (s[1] == t[1])) {
            int now = 0;
            for (int j = min(1, 1 - i); j <= max(c, d - i); j++)
                now += abs(((j < 0) ? 0 : ((j > c) ? n : a[j])) - ((i + j < 0) ? 0 : ((i + j > d) ? n : b[i+j])));
            ans = min(ans, now);
        }
    print(ans);
    return 0;
}

Permutation and Minimum

题意

  • 有一个 $1 \sim 2n$ 的排列 $a$,有些位置上的数不确定。
  • 根据排列 $a$ 可以生成序列 $b_{1\dots n}$,其中 $b_i = \min(a_{2i-1}, a_{2i})$。
  • 求 $b$ 的方案数。
  • $n \le 300$,答案对 $10^9+7$ 取模。

题解

先把 $(x,x)$ 的去掉,剩下的就是 $(x,-1)$ 和 $(-1,-1)$ 两种。

对于 $(-1,-1)$,先忽略其位置关系,最后再乘上个数的阶乘即可。

考虑从大到小 DP,设 $f_{i,j,k}$ 表示当前考虑到 $i$,有 $j$ 个 $-1$ 没有匹配,有 $k$ 个 $x$ 没有匹配。

转移分是否确定讨论一下即可,时间复杂度 $\mathcal O(n^3)$。

代码

const int N = 607;
int n, m, k, a[N], v[N];
bool w[N];
modint f[N][N][N], ans;

int main() {
    rd(n), m = 2 * n, rda(a, m);
    for (int i = 1; i <= n; i++)
        if (a[2*i-1] > 0 && a[2*i] > 0)
            v[a[2*i-1]] = v[a[2*i]] = 1, m -= 2;
    for (int i = 1; i <= 2 * n; i++) v[i] += v[i-1];
    for (int i = 1; i <= n; i++)
        if (a[2*i-1] > 0 && a[2*i] < 0) w[a[2*i-1]-v[a[2*i-1]]] = 1;
        else if (a[2*i-1] < 0 && a[2*i] > 0) w[a[2*i]-v[a[2*i]]] = 1;
        else if (a[2*i-1] < 0 && a[2*i] < 0) ++k;
    f[m+1][0][0] = 1;
    for (int i = m; i; i--)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < m; k++)
                if (!!f[i+1][j][k]) {
                    if (w[i]) {
                        f[i][j+1][k] += f[i+1][j][k];
                        if (k) f[i][j][k-1] += f[i+1][j][k];
                    } else {
                        f[i][j][k+1] += f[i+1][j][k];
                        if (j) f[i][j-1][k] += f[i+1][j][k] * j;
                        if (k) f[i][j][k-1] += f[i+1][j][k];
                    }
                }
    ans = f[1][0][0];
    for (int i = 1; i <= k; i++) ans *= i;
    print(ans); 
    return 0;
}

发表评论

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