AtCoder Grand Contest 027 题解

作者: xht37 分类: 题解 发布时间: 2020-07-12 20:03

点击数:40

AtCoder Grand Contest 027

Candy Distribution Again

排序后从小到大贪心的选。

const int N = 107;
int n, x, a[N], s;

int main() {
    rd(n, x), rda(a, n);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; s += a[i++])
        if (s + a[i] > x) return print(i - 1), 0;
    print(n - (s != x));
    return 0;
}

Garbage Collector

枚举次数 $k$,注意到从后往前的贡献为 $5,5,7,9,\cdots$,因此贪心地将最后 $k$ 个作为第一个,次后 $k$ 个作为第二个,以此类推。

复杂度是调和级数 $\mathcal O(n \log n)$,另外计算中会爆 long long 但答案不会爆,用 __int128 或者剪枝都可以。

const int N = 2e5 + 7;
int n;
__int128 x, p[N], s[N], d[N], ans = 1e36;

int main() {
    rd(n), rd(x), rda(p, n);
    for (int i = 1; i <= n; i++) s[i] = s[i-1] + p[i];
    d[1] = d[2] = 5;
    for (int i = 3; i <= n; i++) d[i] = d[i-1] + 2;
    for (int k = 1; k <= n; k++) {
        __int128 now = (k + n) * x;
        for (int i = n, t = 1; i > 0; i -= k, t++)
            now += d[t] * (s[i] - (i - k > 0 ? s[i-k] : 0));
        ans = min(ans, now);
    }
    print(ans);
    return 0;
}

ABland Yard

若一条边连接的两个点字符相同,则标为 0,否则标为 1

那么合法当且仅当存在一个 01 环。

类似拓扑排序,每次删掉一个连边都是同一个字符的点。

如果最后剩下点没被删掉说明存在,否则不存在。

const int N = 2e5 + 7;
int n, m, d[N][2];
char s[N];
vi e[N];
queue<int> q;
bool v[N];

int main() {
    rd(n, m), rds(s, n);
    for (int i = 1, x, y; i <= m; i++)
        rd(x, y), e[x].pb(y), e[y].pb(x), ++d[x][s[y]&1], ++d[y][s[x]&1];
    for (int i = 1; i <= n; i++)
        if (!d[i][0] || !d[i][1]) q.push(i), v[i] = 1;
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int y : e[x])
            if (!v[y] && !--d[y][s[x]&1]) q.push(y), v[y] = 1;
    }
    for (int i = 1; i <= n; i++)
        if (!v[i]) return prints("Yes"), 0;
    prints("No");
    return 0;
}

Modulo Matrix

题意

  • 你要构造一个 $n \times n$ 的矩阵 $a$,满足:
    • $a_{i,j} \in [1,10^{15}]$。
    • 所有 $a_{i,j}$ 互不相同。
    • 对于任意两个相邻的数 $x,y$,$\max(x,y) \bmod \min(x,y)$ 为定值。
  • $n \le 500$。

题解

如下图构造:

其中黄格子是两个质数的乘积,白格子为周围黄格子的 $\text{lcm} + 1$。

代码

namespace shai {
    const int n = 1e6 + 7;
    int p[n], v[n], phi[n], miu[n];

    inline void init(int n) {
        v[1] = phi[1] = miu[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (!v[i]) p[++p[0]] = v[i] = i, phi[i] = i - 1, miu[i] = -1;
            for (int j = 1; j <= p[0] && i * p[j] <= n && p[j] <= v[i]; j++)
                v[i*p[j]] = p[j],
                phi[i*p[j]] = phi[i] * (p[j] - 1 + (p[j] == v[i])),
                miu[i*p[j]] = p[j] == v[i] ? 0 : -miu[i];
        }
    }
}
using shai::p;

const int N = 507;
int n, a[N], b[N];

int main() {
    shai::init(1e4);
    rd(n);
    for (int i = 1; i <= n; i++) a[i] = p[i&1?i/2+1:n*2-i/2+1];
    for (int i = 1; i <= n; i++) b[i] = p[(i&1?n-i/2:n+i/2)+(n&1)];
    a[0] = a[n+1] = b[0] = b[n+1] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            print((i ^ j) & 1 ? 1ll * a[(i+j)/2] * a[(i+j)/2+1] * b[(n+i-j+(n&1))/2] * b[(n+i-j+(n&1))/2+1] + 1 : 1ll * a[(i+j)/2] * b[(n+i-j+(n&1))/2], " \n"[j==n]);
    return 0;
}

ABBreviate

题意

  • 给定一个仅包含 ab 的字符串 $s$。
  • 你会进行若干次操作,每次操作可以将 $s$ 中的一个 aa 替换成 b,或将一个 bb 替换成 a
  • 求能够生成的字符串数量。
  • $|s| \le 10^5$,答案对 $10^9+7$ 取模。

题解

首先如果没有 aabb,答案为 $1$。

否则,令 a 为 $2$,b 为 $1$,可以发现每次操作都不影响和 $\bmod 3$ 的值。

考虑到如果一个 $t$ 能被 $s$ 生成,那么必然是 $t$ 中的每个字符对应 $s$ 中的某一段,且这两段的和 $\bmod 3$ 的值相同。

可以证明从前往后贪心匹配 $t$ 中的每个字符,如果最后 $s$ 剩下的部分之和 $\bmod 3 = 0$,则 $t$ 合法。

于是可以简单的 $\mathcal O(n)$ DP 求出答案了。

代码

const int N = 1e5 + 7;
int n, a[N], p[N][3];
char s[N];
modint f[N], ans;

inline bool pd() {
    for (int i = 1; i < n; i++)
        if (s[i] == s[i+1]) return 0;
    return 1;
}

int main() {
    rds(s, n);
    if (pd()) return print(1), 0;
    for (int i = 1; i <= n; i++) a[i] = (a[i-1] + (s[i] & 1) + 1) % 3;
    for (int i = 0; i < 3; i++) p[n+1][i] = n + 1;
    for (int i = n; i; i--) {
        for (int j = 0; j < 3; j++) p[i][j] = p[i+1][j];
        p[i][a[i]] = i;
    }
    f[0] = 1;
    for (int i = 0; i <= n; i++) {
        if (i && a[i] == a[n]) ans += f[i];
        for (int j = 1; j < 3; j++)
            f[p[i+1][(a[i]+j)%3]] += f[i];
    }
    print(ans);
    return 0;
}

Grafting

题意

  • 给定两棵 $n$ 个点的树 $A,B$。
  • 一开始 $A$ 的所有点都是白色,你可以对 $A$ 进行若干次下列操作使得 $A$ 与 $B$ 相同:
    • 选择一个白色的叶子节点 $x$。
    • 删掉与 $x$ 相连的边。
    • 加上一条连接 $x$ 与另一个节点 $y$ 的边。
    • 将 $x$ 染成黑色。
  • 判断是否可行,如果可行,请最小化操作步数。
  • $n \le 50$,多组数据组数 $T \le 20$。

题解

首先判一下 $A,B$ 是否本身就相同,如果是就直接输出 $0$。

否则枚举第一次操作的 $x,y$,然后以 $x$ 为根把两棵树拎起来(其中 $A$ 是操作后的树)。

那么某个节点会被修改当且仅当这个点在两棵树上的父亲不同。

另外可以得到一些约束条件:

  • 若某个点不需要被修改,这意味着它在 $A$ 上的父亲不可能成为叶子,因此若它在 $A$ 上的父亲需要被修改,那么无解。
  • 在 $A$ 中,一个点一定比它的父亲先被修改(如果都要被修改的话)。
  • 在 $B$ 中,一个点一定比它的父亲后被修改(如果都要被修改的话)。

根据后两个条件我们可以得到一个有向图,如果这个有向图无环则说明有解,否则无解。

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

代码

const int N = 57, inf = 1e9;
int n, f[2][N], d[N];
vi e[2][N], g[N];
bool v[N];
queue<int> q;

inline bool pd0() {
    for (int i = 1; i <= n; i++)
        if (e[0][i] != e[1][i]) return 0;
    return 1;
}

inline void change(int x, int y, int z) {
    e[0][x][0] = z;
    for (int &o : e[0][y])
        if (o == x) {
            swap(o, e[0][y].back());
            break;
        }
    e[0][y].pop_back(), e[0][z].pb(x);
}

void dfs(int o, int x, int fa) {
    f[o][x] = fa;
    for (int y : e[o][x])
        if (y != fa) dfs(o, y, x);
}

inline void add(int x, int y) {
    g[x].pb(y), ++d[y];
}

inline int calc(int x, int y) {
    int z = e[0][x][0], now = y != z;
    change(x, z, y);
    dfs(0, x, 0), dfs(1, x, 0);
    change(x, y, z);
    for (int i = 1; i <= n; i++)
        now += v[i] = f[0][i] != f[1][i], g[i].clear(), d[i] = 0;
    for (int i = 1; i <= n; i++)
        if (!v[i] && v[f[0][i]]) return inf;
    for (int o = 0; o < 2; o++)
        for (int i = 1; i <= n; i++)
            if (v[i] && v[f[o][i]])
                add(o ? f[o][i] : i, o ? i : f[o][i]);
    for (int i = 1; i <= n; i++)
        if (v[i] && !d[i]) q.push(i);
    while (q.size()) {
        int x = q.front();
        q.pop(), v[x] = 0;
        for (int y : g[x])
            if (!--d[y]) q.push(y);
    }
    for (int i = 1; i <= n; i++)
        if (v[i]) return inf;
    return now;
}

inline void solve() {
    rd(n);
    for (int o = 0; o < 2; o++) {
        for (int i = 1; i <= n; i++) e[o][i].clear();
        for (int i = 1, x, y; i < n; i++)
            rd(x, y), e[o][x].pb(y), e[o][y].pb(x);
        for (int i = 1; i <= n; i++)
            sort(e[o][i].begin(), e[o][i].end());
    }
    if (pd0()) return print(0);
    int ans = inf;
    for (int x = 1; x <= n; x++)
        if (e[0][x].size() == 1u)
            for (int y = 1; y <= n; y++)
                ans = min(ans, calc(x, y));
    print(ans == inf ? -1 : ans);
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

发表评论

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