AtCoder Grand Contest 032 题解

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

点击数:48

AtCoder Grand Contest 032

Limited Insertion

倒着考虑,每次找到最大的 $i$ 满足 $a_i = i$ 然后删掉,如果不存在则无解。

const int N = 107;
int n, a[N], ans[N];

int main() {
    rd(n), rda(a, n);
    for (int i = n; i; i--) {
        int p = 0;
        for (int j = i; j && !p; j--)
            if (a[j] == j) p = j;
        if (!p) return prints("-1"), 0;
        ans[i] = p;
        for (int j = p; j < i; j++) a[j] = a[j+1];
    }
    for (int i = 1; i <= n; i++) print(ans[i]);
    return 0;
}

Balanced Neighbors

构造方式见代码。

int main() {
    int n;
    rd(n);
    if (n == 3) {
        print(2);
        print(1, 3);
        print(2, 3);
        return 0;
    }
    if (n == 4) {
        print(4);
        print(1, 2);
        print(1, 3);
        print(4, 2);
        print(4, 3);
        return 0;
    }
    vector<pi> e;
    vi a, b;
    int m = n & 1;
    n -= m;
    for (int i = 1; i <= n >> 1; i++) a.pb(i);
    for (int i = n; i > n >> 1; i--) b.pb(i);
    for (int i = 1; i < n >> 1; i++)
        e.pb(mp(a[i-1], a[i])),
        e.pb(mp(b[i-1], b[i])),
        e.pb(mp(a[i-1], b[i])),
        e.pb(mp(b[i-1], a[i]));
    if (m) {
        e.pb(mp(n + 1, a[0])),
        e.pb(mp(n + 1, b[0])),
        e.pb(mp(n + 1, a.back())),
        e.pb(mp(n + 1, b.back()));
    } else {
        e.pb(mp(a.back(), a[0])),
        e.pb(mp(b.back(), b[0])),
        e.pb(mp(a.back(), b[0])),
        e.pb(mp(b.back(), a[0]));
    }
    print(e.size());
    for (pi o : e) print(o.fi, o.se);
    return 0;
}

Three Circuits

题意

  • 给定一张 $n$ 个点 $m$ 条边的无向图,问能否将无向图拆成三个环,使得每条边恰好在一个环中。
  • $n,m \le 10^5$。

题解

首先要是欧拉回路。

若度数最大值 $\ge 6$ 则有解,$= 2$ 则无解,接下来考虑 $=4$ 的情况。

若度数为 $4$ 的点超过 $3$ 个则有解,$1$ 个则无解,接下来考虑 $2$ 个的情况。

只有两种形态,一种有解一种无解,讨论一下即可。

代码

const int N = 1e5 + 7;
int n, m, d[N], X, Y;
vi e[N];

void dfs(int x, int f) {
    if (x == Y) return;
    if (x == X) prints("Yes"), exit(0);
    for (int y : e[x])
        if (y != f) dfs(y, x);
}

int main() {
    rd(n, m);
    for (int i = 1, x, y; i <= m; i++)
        rd(x, y), ++d[x], ++d[y], e[x].pb(y), e[y].pb(x);
    for (int i = 1; i <= n; i++) if (d[i] & 1) return prints("No"), 0;
    int mx = *max_element(d + 1, d + n + 1);
    if (mx == 2) return prints("No"), 0;
    if (mx >= 6) return prints("Yes"), 0;
    int cnt = 0;
    for (int i = 1; i <= n; i++) cnt += d[i] == 4;
    if (cnt == 1) return prints("No"), 0;
    if (cnt >= 3) return prints("Yes"), 0;
    for (int i = 1; i <= n; i++)
        if (d[i] == 4) {
            if (X) Y = i;
            else X = i;
        }
    for (int z : e[X]) dfs(z, X);
    prints("No");
    return 0;
}

Rotation Sort

题意

  • 给定一个 $1 \sim n$ 的排列 $p$,你要将其变成升序。
  • 有两种操作:
    • 选择一个 $l,r$ 满足 $1 \le l < r \le n$,将 $p_{l\dots r}$ 替换为 $p_{l+1\dots r},p_l$,代价为 $a$。
    • 选择一个 $l,r$ 满足 $1 \le l < r \le n$,将 $p_{l\dots r}$ 替换为 $p_{r},p_{l\dots r-1}$,代价为 $b$。
  • 求最小代价。
  • $n \le 5\times 10^3$。

题解

显然操作等价于将某个数左移或者右移。

考虑 DP,设 $f_{i,j}$ 表示考虑前 $i$ 个数,其中最后一个没有被移动的数为 $j$ 的最小代价,分 $a_i > j$ 和 $a_i < j$ 转移即可,时间复杂度 $\mathcal O(n^2)$。

代码

const int N = 5e3 + 7;
const ll inf = 1e18;
int n, a, b, p[N];
ll f[N][N], ans = inf;

int main() {
    rd(n, a, b), rda(p, n);
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            f[i][j] = inf;
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n; j++)
            if (p[i] > j)
                f[i][j] = min(f[i][j], f[i-1][j] + a),
                f[i][p[i]] = min(f[i][p[i]], f[i-1][j]);
            else f[i][j] = min(f[i][j], f[i-1][j] + b);
    for (int i = 0; i <= n; i++) ans = min(ans, f[n][i]);
    print(ans);
    return 0;
}

Modulo Pairing

题意

  • 给定模数 $m$ 和 $2n$ 个整数,你要将这些整数分成 $n$ 对。
  • 对于每一对 $(x,y)$,其权值为 $(x+y) \bmod m$。
  • 你要最小化这 $n$ 对权值的最大值。
  • $n \le 10^5$,$m \le 10^9$。

题解

有结论:按从小到大排序后,一定存在一个最优解,是以某个位置为界,两边分别首位匹配,满足左边每一对的和都 $< m$,右边每一对的和都 $\ge m$。

二分这个位置,时间复杂度 $\mathcal O(n \log n)$。

代码

const int N = 2e5 + 7;
int n, m, a[N], ans;

inline bool pd(int o) {
    for (int i = o << 1 | 1; i <= n << 1; i++)
        if (a[i] + a[((n+o)<<1|1)-i] < m) return 0;
    return 1;
}

int main() {
    rd(n, m), rda(a, n << 1);
    sort(a + 1, a + (n << 1 | 1));
    int l = 0, r = n;
    while (l < r) {
        int d = (l + r) >> 1;
        if (pd(d)) r = d;
        else l = d + 1;
    }
    int p = l << 1;
    for (int i = 1; i <= p; i++)
        ans = max(ans, a[i] + a[p+1-i]);
    for (int i = p + 1; i <= n << 1; i++)
        ans = max(ans, a[i] + a[(n<<1|1)+p-i] - m);
    print(ans);
    return 0;
}

One Third

题意

  • 有一个披萨,将它在 $n$ 条随机的半径切一刀。
  • 你会选择若干块相邻的披萨饼,使其总和最接近 $\frac 13$。
  • 求选择的披萨饼大小与 $\frac 13$ 之差的绝对值的期望值。
  • $n \le 10^6$,答案对 $10^9+7$ 取模。

题解

先转化,对于每一刀,先将其染成红色,再在 $+ \frac 13$ 和 $-\frac 13$ 各切一刀,分别染蓝色和绿色。

将每一刀 $\bmod \frac 13$,于是问题等价于有一条长 $\frac 13$ 的线段,$0$ 处为红,$\frac 13$ 处为蓝,中间还有 $n-1$ 个位置和颜色随机的点,将整个线段分成了 $n$ 段,求最短的两端颜色不同的线段长度的期望。

把所有线段拿出来排序,考虑答案为第 $k$ 短的线段,经过积分可以得到为 $\sum_{i=1}^{k} \frac{1}{3n(n+1-i)}$。

考虑最短的,答案为 $\frac{1}{3n^2}$,如果同色考虑次短的,要加上 $\frac{1}{3n(n-1)}$ 乘上同色的概率 $\frac 13$,以此类推,答案为 $\sum_{k=1}^{n} \frac{1}{3^kn(n+1-k)}$。

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

代码

int n;
modint ans, a = 1;

int main() {
    rd(n), init(max(n, 3));
    for (int k = 1; k <= n; k++) ans += (a *= v[3]) * v[n+1-k];
    print(ans * v[n]);
    return 0;
}

发表评论

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