Visits: 370

AtCoder Grand Contest 029

Irreversible operation

最后的字符串一定是所有 W 在 B 前面，于是考虑对应位置下标差之和即可。

const int N = 2e5 + 7;
int n, p[N], t;
char s[N];
ll ans;

int main() {
    rds(s, n);
    for (int i = 1; i <= n; i++)
        if (s[i] == 'B') p[++t] = i;
    for (int i = 1; i <= t; i++)
        ans += n - t + i - p[i];
    print(ans);
    return 0;
}

Powers of two

注意到 $\le x$ 且能与 $x$ 匹配的数是唯一的，于是从大到小贪心即可。

const int N = 2e5 + 7, M = 31;
int n, a[N], b[N], ans;
map<int, int> c;

int main() {
    rd(n), rda(a, n);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        ++c[a[i]], b[i] = 1;
        while (b[i] <= a[i]) b[i] <<= 1;
        b[i] -= a[i];
    }
    for (int i = n; i; i--)
        if (c[a[i]]) {
            --c[a[i]];
            if (c[b[i]]) --c[b[i]], ++ans;
        }
    print(ans);
    return 0;
}

Lexicographic constraints

题意

• 有 $n$ 个字符串 $s_{1\dots n}$，对于 $i \in [1,n-1]$，满足 $s_i < s_{i+1}$。
• 现在你不知道 $s_{1\dots n}$，但你知道 $s_i$ 的长度为 $a_i$。
• 求最小的字符集大小，可以构造出合法的 $s_{1\dots n}$。
• $n \le 2 \times 10^5$，$a_i \le 10^9$。

题解

显然答案具有可二分性，先二分答案。

如果 $a_i > a_{i-1}$，则就是在 $s_{i-1}$ 的基础上后面加一堆 $a_i – a_{i-1}$ 个 $1$；否则，就是砍掉 $s_{i-1}$ 中 $> a_i$ 的部分然后 $+1$。

用栈维护 $s$ 中的每个相同字符连续段以及 $+1$ 操作，根据势能分析复杂度为 $\mathcal O(n)$。

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

代码

const int N = 2e5 + 7, M = 31;
int n, a[N], p[N], c[N], s[N], t;

inline void add(int x, int k) {
    if (x == p[t]) c[t] += k, s[t] += k;
    else p[++t] = x, c[t] = k, s[t] = c[t] + s[t-1];
}

inline bool add1(int m) {
    if (t == 1 && p[t] == m) return 0;
    if (p[t] != m) {
        if (c[t] == 1) --t, add(p[t+1] + 1, 1);
        else --c[t], --s[t], add(p[t] + 1, 1);
    } else {
        int k = c[t--];
        if (c[t] == 1) --t, add(p[t+1] + 1, 1);
        else --c[t], --s[t], add(p[t] + 1, 1);
        add(1, k);
    }
    return 1;
}

inline bool pd(int m) {
    t = 0, add(1, a[1]);
    for (int i = 2; i <= n; i++)
        if (a[i] > a[i-1]) add(1, a[i] - a[i-1]);
        else {
            while (s[t] > a[i]) --t;
            if (s[t] < a[i]) add(p[t+1], a[i] - s[t]);
            if (!add1(m)) return 0;
        }
    return 1;
}

int main() {
    rd(n), rda(a, n);
    int l = 1, r = n;
    while (l < r) {
        int d = (l + r) >> 1;
        if (pd(d)) r = d;
        else l = d + 1;
    }
    print(l);
    return 0;
}

Grid game

显然先手一直会往下走，后手需要找到一个格子让先手无法走。

求出到每一行时后手可以让棋子在哪些列，如果这些列中存在某个位置有障碍，则让棋子走到这个障碍上方即可。

const int N = 2e5 + 7;
int n, m, k, p[N];

int main() {
    rd(n, m, k);
    for (int i = 1; i <= n; i++) p[i] = m + 1;
    for (int i = 1, x, y; i <= k; i++)
        rd(x, y), p[x] = min(p[x], y);
    for (int i = 2, r = 1; i <= n; i++)
        if (r >= p[i]) return print(i - 1), 0;
        else if (r + 1 < p[i]) ++r;
    print(n);
    return 0;
}

Wandering TKHS

题意

• 给定一棵 $n$ 个点的树。
• 你现在在某个点 $r$，你要到 $1$ 去。
• 每次你会移动到未去过的，且与去过的点相邻的编号最小的点。
• 你要求出对于 $r \in [2,n]$，从 $r$ 到 $1$ 的移动次数。
• $n \le 2 \times 10^5$。

题解

把 $1$ 当做根，设 $f_x$ 表示 $x$ 的父亲，$m_x$ 表示 $1 \to f_X$ 的路径上编号最大的点，$h_{x,y}$ 表示从 $x$ 开始不经过 $f_x$ 和其它编号 $>y$ 的点的情况下能到达多少个点，$c_x$ 表示 $x$ 的答案。

考虑对于每个 $x$，讨论一下可知 $c_x – c_{f_x}$ 为 $h_{x,m_x} – [x < m_x][x < m_{f_x}]h_{x,m_{f_x}}$。

而对于 $h$ 有 $h_{x,y} = 1 + \sum_{z \in \text{son}(x)} [z \le y]h_{z,y}$。

注意到对于 $h_{x,y}$，有用的 $y$ 值只有 $m_x$ 和 $m_{f_X}$，因此总状态数为 $\mathcal O(n)$，时间复杂度也为 $\mathcal O(n)$。

代码

const int N = 2e5 + 7;
int n, m[N], c[N];
vi e[N];
unordered_map<int, int> h[N];

void dfs1(int x, int f) {
    if (x == 1) m[x] = -1;
    else {
        m[x] = max(m[f], f), h[x][m[x]] = 0;
        if (x < m[x] && m[f] > x) h[x][m[f]] = 0;
    }
    for (pi o : h[x])
        for (int y : e[x])
            if (y < o.fi) h[y][o.fi] = 0;
    for (int y : e[x])
        if (y != f) dfs1(y, x);
    for (auto &o : h[x]) {
        ++o.se;
        for (int y : e[x])
            if (y < o.fi) o.se += h[y][o.fi];
    }
    if (x == 1) return;
    if (x > m[x]) c[x] += h[x][m[x]];
    else {
        c[x] += h[x][m[x]];
        if (m[f] > x) c[x] -= h[x][m[f]];
    }
}

void dfs2(int x, int f) {
    c[x] += c[f];
    for (int y : e[x])
        if (y != f) dfs2(y, x);
}

int main() {
    rd(n);
    for (int i = 1, x, y; i < n; i++)
        rd(x, y), e[x].pb(y), e[y].pb(x);
    dfs1(1, 0), dfs2(1, 0);
    for (int i = 2; i <= n; i++)
        print(c[i], " \n"[i==n]);
    return 0;
}

Construction of a tree

题意

• 给定 $[1,n]$ 的 $n-1$ 个子集 $E_{1\dots n-1}$。
• 问是否能从每个子集中选择两个元素，使得将这两个元素相连后形成一棵树，如果可以请构造一组方案。
• $n \le 10^5$，$\sum_{i=1}^{n-1} |E_i| \le 2 \times 10^5$。

题解

考虑将 $1$ 作为根，那么之后每条边都可以看成是一个点和其父亲的连边。

建立二分图，左边是点 $2 \sim n$，右边是子集 $1 \sim n – 1$，若点 $i$ 在子集 $j$ 中则连边，那么如果有解就必须存在完备匹配。

任取一组完备匹配，从 $1$ 开始构造树。一开始将 $1$ 所在的所有点集的匹配点的父亲设为 $1$，然后从这些点递归下去。

如果递归到了所有点，则构造出了一组解，否则说明二分图不连通，从而一定无解。

Dinic 求二分图匹配，时间复杂度 $\mathcal O(m \sqrt n)$。

代码

namespace Dinic {
    const int N = 2e5 + 7, M = 2e6 + 7;
    const ll inf = 1e18;
    int n, S, T, d[N];
    int h[N], hi[N], e[M], t[M], tot;
    ll f[M], mxf;

    inline void add(int x, int y, ll z, bool o = 1) {
        e[++tot] = y, f[tot] = z, t[tot] = h[x], h[x] = tot;
        if (o) add(y, x, 0, 0);
    }

    inline bool bfs() {
        for (int i = 1; i <= n; i++) d[i] = 0;
        queue<int> q;
        q.push(S), d[S] = 1;
        while (q.size()) {
            int x = q.front();
            q.pop();
            for (int i = h[x]; i; i = t[i]) {
                int y = e[i];
                ll z = f[i];
                if (d[y] || !z) continue;
                q.push(y), d[y] = d[x] + 1;
                if (y == T) return 1;
            }
        }
        return 0;
    }

    ll dfs(int x, ll now = inf) {
        if (x == T) return now;
        ll rst = now;
        for (int &i = hi[x]; i; i = t[i]) {
            int y = e[i];
            ll z = f[i];
            if (d[y] != d[x] + 1 || !z) continue;
            ll k = dfs(y, min(z, rst));
            if (!k) d[y] = 0;
            else f[i] -= k, f[i^1] += k, rst -= k;
            if (!rst) break;
        }
        return now - rst;
    }

    inline void main() {
        while (bfs()) {
            for (int i = 1; i <= n; i++) hi[i] = h[i];
            ll now;
            while ((now = dfs(S))) mxf += now;
        }
    }

    inline void init(int _n, int _S, int _T) {
        n = _n, S = _S, T = _T, tot = 1, mxf = 0;
        for (int i = 1; i <= n; i++) h[i] = 0; 
    }
}
using Dinic::add;

const int N = 1e5 + 7;
int n, f[N], fa[N], id[N];
set<int> e[N], g[N];
bool v[N];
pi ans[N];

int main() {
    rd(n), Dinic::init(2 * n, 1, 2 * n);
    for (int i = 1, c, x; i < n; i++) {
        add(1, i + 1, 1), add(i + n, 2 * n, 1);
        rd(c);
        while (c--) {
            rd(x), e[i].insert(x), g[x].insert(i);
            if (x == 1) continue;
            add(x, i + n, 1);
        }
    }
    Dinic::main();
    if (Dinic::mxf != n - 1) return print(-1), 0;
    for (int x = 1; x < n; x++)
        for (int i = Dinic::h[x+n]; i; i = Dinic::t[i])
            if (Dinic::e[i] <= n && Dinic::f[i]) f[x] = Dinic::e[i];
    queue<int> q;
    q.push(1);
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int y : g[x])
            if (!v[y]) v[y] = 1, fa[f[y]] = x, id[f[y]] = y, q.push(f[y]);
    }
    for (int i = 1; i < n; i++)
        if (!v[i]) return print(-1), 0;
    for (int i = 2; i <= n; i++) ans[id[i]] = mp(fa[i], i);
    for (int i = 1; i < n; i++) print(ans[i].fi, ans[i].se);
    return 0;
}