AtCoder Grand Contest 039 题解

作者: xht37 分类: 题解 发布时间: 2020-05-10 18:45

点击数:63

AtCoder Grand Contest 039

Connection and Disconnection

分类讨论贪心。

const int N = 107;
int n, c, k, t, a, b;
char s[N];

int main() {
    rds(s, n), rd(k);
    for (int l = 1, r = 1; l <= n; l = ++r) {
        while (s[r+1] == s[l]) ++r;
        t += (r - l + 1) >> 1, ++c;
        if (!a) a = r - l + 1;
        b = r - l + 1;
    }
    if (s[1] != s[n]) print(1ll * k * t);
    else if (c == 1) print((1ll * n * k) >> 1);
    else {
        t -= (a >> 1) + (b >> 1);
        t += (a + b) >> 1;
        print(1ll * k * t - ((a & 1) && (b & 1)));
    }
    return 0;
}

Graph Partition

首先图要是一张二分图。

是二分图的情况下,从某一个点开始 bfs,如果合法,用最大深度更新答案即可。

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

const int N = 207;
int n, c[N], d[N], ans;
vi e[N];

void dfs(int x, int o) {
    c[x] = o;
    for (int y : e[x])
        if (!c[y]) dfs(y, 3 - o);
        else if (c[x] == c[y]) print(-1), exit(0);
}

inline int calc(int s) {
    for (int i = 1; i <= n; i++) d[i] = 0;
    d[s] = 1;
    queue<int> q;
    q.push(s);
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int y : e[x])
            if (!d[y]) d[y] = d[x] + 1, q.push(y);
            else if (d[y] != d[x] - 1 && d[y] != d[x] + 1) return 0;
    }
    return *max_element(d + 1, d + n + 1);
}

int main() {
    rd(n);
    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= n; y++) {
            char c;
            rdc(c);
            if (c == '1') e[x].pb(y);
        }
    dfs(1, 1);
    for (int i = 1; i <= n; i++) ans = max(ans, calc(i));
    print(ans);
    return 0;
}

Division by Two with Something

有趣的计数题。

不当成一个 $n$ 位二进制数而看作一个 $0/1$ 串的话,每次操作相当于把最右边的字符取反放到最左边。

考虑一个 $0/1$ 串如何计算需要多少次操作能回到本身。

首先注意到串 $s$ 一定会至多经过 $n$ 次操作完全取反,然后再经过同等次数的操作回到本身。

因此任何一个串一定能够回到本身,且次数不超过 $2n$ 次,且次数为偶数次。

假设次数为 $2t$ 次,则意味着 $t$ 次之后能取反。

于是有 $s[n-t+1:n]$ 和 $s[n-2t+1:n-t]$ 互反,$s[n-2t+1:n-t]$ 和 $s[n-3t+1:n-2t]$ 互反,$\cdots$,$s[t+1:2t]$ 与 $s[1:t]$ 互反,$s[1:t]$ 与 $s[n-t+1:n]$ 互反。

因此 $t$ 为满足:

  1. $n$ 的约数;
  2. $\frac nt$ 为奇数;
  3. $s[i]$ 与 $s[i+t]$ 互反;

的最小值。

于是就简单了,枚举 $t$,求出恰好经过 $t$ 次操作回到本身且 $\le X$ 的个数,即:

  • $S[1:t]$ 所构成的数;
  • 减去 $t$ 的约数对应的个数(这意味着更小的循环节);
  • 如果 $S[1:t]$ 根据 $s[i]$ 与 $s[i+t]$ 互反,扩展成长度为 $n$ 的数之后 $\le X$,则还要加上 $1$。

然后将个数乘上 $2t$ 就是 $t$ 的贡献。

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

const int N = 2e5 + 7;
int n;
char s[N];
bool a[N], b[N];
modint c[N], ans;

inline bool pd(int i) {
    for (int j = 1; j <= i; j++) b[j] = a[j];
    for (int j = i + 1; j <= n; j++) {
        b[j] = b[j-i] ^ 1;
        if (b[j] < a[j]) return 1;
        if (b[j] > a[j]) return 0;
    }
    return 1;
}

int main() {
    rd(n), rds(s, n);
    for (int i = 1; i <= n; i++) a[i] = s[i] & 15;
    for (int i = 1; i <= n; i++)
        if (!(n % i) && ((n / i) & 1)) {
            for (int j = 1; j <= i; j++)
                c[i] = c[i] * 2 + a[j];
            for (int j = 1; j < i; j++)
                if (!(i % j)) c[i] -= c[j];
            c[i] += pd(i);
            ans += c[i] * i * 2;
        }
    print(ans);
    return 0;
}

Incenters

题意

  • 平面直角坐标系上有 $n$ 个点,第 $i$ 个点为 $(\cos(\frac {2\pi T_i}{L}), \sin(\frac {2\pi T_i}{L}))$。
  • 求出在 $n$ 个点中随机选择三个点,以这三个点为顶点的三角形的内心的期望坐标。
  • $n \le 3 \times 10^3$,$0 \le T_i < L \le 10^9$。

题解

对于 $\triangle ABC$,取 $AB,BC,CA$ 弧的中点 $D,E,F$,可以发现 $\triangle DEF$ 的垂心就是 $\triangle ABC$ 的内心。

考虑如何求 $\triangle DEF$ 的垂心,根据欧拉线,由于 $\triangle DEF$ 的外心为 $O(0,0)$,重心为 $\frac{D+E+F}{3}$,所以垂心为 $D+E+F$。

于是显然可以 $\mathcal O(n^2)$ 枚举求答案。

代码

const int N = 3e3 + 7;
const ld PI = acos(-1);
int n, L, a[N];
ld x, y;

int main() {
    rd(n, L), rda(a, n);
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            x += (n - 2 * (j - i)) * cos(PI * (a[i] + a[j]) / L),
            y += (n - 2 * (j - i)) * sin(PI * (a[i] + a[j]) / L);
    ll k = 1ll * n * (n - 1) * (n - 2) / 6;
    printf("%.20Lf %.20Lf\n", x / k, y / k);
    return 0;
}

Pairing Points

题意

  • 圆上有 $2n$ 个点,对于任意六个点 $a,b,c,d,e,f$ 满足 $ab,cd,ef$ 三线不共点。
  • 给定一个 $2n \times 2n$ 的 $0/1$ 矩阵 $a$,你需要计算将 $2n$ 个点分成 $n$ 个点对的方案数,满足:
    • 对于所有点对 $(p,q)$,$a_{p,q} = a_{q,p} = 1$。
    • 将所有点对用线段连接起来,恰好形成一棵树。
  • $n \le 20$。

题解

考虑先将 $n$ 设为原本的 $2n$。

考虑用 $f(l,m,r)$ 表示在 $[l,m-1] \cup [m+1,r]$ 中连一些点对,使得至少有一组点对跨过 $m$,且所有跨过 $m$ 的点对两两不交的方案数。

枚举 $1$ 号点的对应点 $i$,于是问题求 $f(2,i,n)$ 的答案。

考虑如何求 $f(l,m,r)$,枚举跨过 $m$ 的所有点对中最靠近 $l,r$ 的点对 $(p,q)$。

可以发现,此时 $[p+1,m-1]$ 中,有靠近 $p$ 的一部分会和 $p$ 连通,剩下的部分与 $m$ 连通,分界点为 $x$。

同理,此时 $[m+1,q-1]$ 中,有靠近 $q$ 的一部分会和 $q$ 连通,剩下的部分与 $m$ 连通,分界点为 $y$。

而 $[l,p-1]$ 一定和 $p$ 连通,$[q+1,r]$ 一定和 $q$ 连通。

因此问题被分为了 $f(l,p,x),f(y,q,r),f(x+1,m,y-1)$ 三个子问题。

记忆化搜索即可,状态数为 $\mathcal O(n^3)$,转移为 $\mathcal O(n^4)$,总时间复杂度为 $\mathcal O(n^7)$,常数非常小,可以通过本题。

这个 DP 可以优化到 $\mathcal O(n^5)$,不过没必要。

代码

const int N = 47;
int n, a[N][N];
char s[N][N];
ll f[N][N][N], ans;
bool v[N][N][N];

ll DP(int l, int m, int r) {
    if ((l ^ r) & 1) return 0;
    if (l == m && m == r) return 1;
    if (l == m || m == r) return 0;
    if (v[l][m][r]) return f[l][m][r];
    v[l][m][r] = 1;
    for (int p = l; p < m; p++)
        for (int q = r; q > m; q--)
            if (a[p][q])
                for (int x = p; x < m; x++)
                    for (int y = q; y > m; y--)
                        f[l][m][r] += DP(l, p, x) * DP(y, q, r) * DP(x + 1, m, y - 1);
    return f[l][m][r];
}

int main() {
    rd(n), n <<= 1;
    for (int i = 1; i <= n; i++) rds(s[i], n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = s[i][j] & 1;
    for (int i = 2; i <= n; i++)
        if (a[1][i]) ans += DP(2, i, n);
    print(ans);
    return 0;
}

Min Product Sum

题意

  • 有一个 $n \times m$ 的矩阵 $a$,每个位置上有一个 $[1,k]$ 的整数。
  • 对于一种填数方案,设 $f(x,y) = \min(\min_{i=1}^n a_{i,y}, \min_{j=1}^m a_{x,j})$,则这种方案的权值为 $\prod_{x=1}^n \prod_{y=1}^m f(x,y)$。
  • 求一共 $k^{nm}$ 种方案的权值和。
  • $n,m,k \le 100$,答案对 $P$ 取模。

题解

首先转化题意:

  • 有两个 $n \times m$ 的矩阵 $a,b$,每个位置上有一个 $[1,k]$ 的整数。
  • 另外要求 $b_{x,y} \le \min(\min_{i=1}^n a_{i,y}, \min_{j=1}^m a_{x,j})$。
  • 求方案数。

显然这两者是等价的。

设 $x_i = \min_{j=1}^m a_{i,j}$,$y_j = \min_{i=1}^n a_{i,j}$,假设我们已经设定了所有 $x_i,y_j$,考虑如何求方案数。

对于 $a$,$a_{i,j}$ 可以填 $[\max(x_i, y_j), k]$;对于 $b$,$b_{i,j}$ 可以填 $[1,\min(x_i,y_i)]$。

然而这样填是有问题的,并不能保证最小值恰好 $x_i,y_j$,于是需要容斥一下,即枚举有多少行多少列的最小值大于设定值,乘上 $-1$ 的那么多次方。

考虑 DP,从小到大填 $x_i,y_i$,设 $f_{t,i,j}$ 表示已经填了 $1 \sim t$,用了 $i$ 行 $j$ 列,$a$ 已经填了这 $i$ 行 $j$ 列的交的位置,$b$ 已经填了这 $i$ 行 $j$ 列的并的位置,的方案数。

转移时枚举填 $t$ 的不被容斥的行列数 $p,q$,被容斥的行列数 $u,v$,则有:
$$
f_{t,i+p+u,j+q+v} \leftarrow (-1)^{u+v} \binom {n-i}{p,u} \binom {m-j}{q,v} \cdot (k-t+1)^{iq+pj+pq}(k-t)^{iv+pv+uj+uq+uv}t^{(p+u)(m-j)+(n-i)(q+v)-(p+u)(q+v)} \cdot f_{t-1,i,j}
$$
然而设 $n,m,k$ 同阶,这个 DP 复杂度是 $\mathcal O(n^7)$,显然要优化。

依然从小到大枚举 $t$,在这一层转移时,可以发现我们不必同时枚举 $p,q,u,v$,而只需要依次枚举,每次把贡献计算清楚即可。

具体而言,先让 $f_t$ 继承 $f_{t-1}$。

再枚举 $p$,转移为:
$$
f_{t,i+p,j} \leftarrow \binom {n-i}{p} \cdot (k-t+1)^{pj}t^{p(m-j)} \cdot f_{t,i,j}
$$
再枚举 $q$,转移为:
$$
f_{t,i,j+q} \leftarrow \binom {m-j}{q} \cdot (k-t+1)^{iq}t^{q(n-i)} \cdot f_{t,i,j}
$$
再枚举 $u$,转移为:
$$
f_{t,i+u,j} \leftarrow (-1)^u\binom {n-i}{u} \cdot (k-t)^{uj}t^{u(m-j)} \cdot f_{t,i,j}
$$
再枚举 $v$,转移为:
$$
f_{t,i,j+v} \leftarrow (-1)^v\binom {m-j}{v} \cdot (k-t)^{iv}t^{v(n-i)} \cdot f_{t,i,j}
$$
时间复杂度 $\mathcal O(n^4)$,很卡常,要进行一定程度的预处理,尽可能减少取模次数。

代码

const int N = 107;
int n, m, k;
int f[N<<2][N][N], g[N][N*N], c[N][N];

inline void upd(int &x, int y, int z) {
    x = (x + 1ll * y * z) % P;
}

int main() {
    rd(n, m, k), rd(P);
    init(max(n, m));
    for (int i = 0; i <= k; i++) {
        g[i][0] = 1;
        for (int j = 1; j <= n * m; j++) g[i][j] = 1ll * g[i][j-1] * i % P;
    }
    for (int i = 0; i <= max(n, m); i++)
        for (int j = 0; j <= i; j++) c[i][j] = binom(i, j).x;
    f[0][0][0] = 1;
    for (int t = 1, o = 0; t <= k; t++) {
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                if (!!f[o][i][j]) {
                    ll x = f[o][i][j], y = 1ll * g[k-t+1][j] * g[t][m-j] % P;
                    for (int p = 0; i + p <= n; p++, (x *= y) %= P) upd(f[o+1][i+p][j], c[n-i][p], x);
                }
        ++o;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                if (!!f[o][i][j]) {
                    ll x = f[o][i][j], y = 1ll * g[k-t+1][i] * g[t][n-i] % P;
                    for (int q = 0; j + q <= m; q++, (x *= y) %= P) upd(f[o+1][i][j+q], c[m-j][q], x);
                }
        ++o;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                if (!!f[o][i][j]) {
                    ll x = f[o][i][j], y = P - 1ll * g[k-t][j] * g[t][m-j] % P;
                    for (int u = 0; i + u <= n; u++, (x *= y) %= P) upd(f[o+1][i+u][j], c[n-i][u], x);
                }
        ++o;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                if (!!f[o][i][j]) {
                    ll x = f[o][i][j], y = P - 1ll * g[k-t][i] * g[t][n-i] % P;
                    for (int v = 0; j + v <= m; v++, (x *= y) %= P) upd(f[o+1][i][j+v], c[m-j][v], x);
                }
        ++o;
    }
    print(f[k<<2][n][m]);
    return 0;
}

发表评论

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