AtCoder Beginner Contest 287

ABCD 比较简单就不写了。

E - Karuta

给 \(n\) 个字符串 \(S_i\ (\sum |S_i|\le 10^5)\) ，问每个串和其他所有串的 LCP 的最大值。

先把所有串建 Trie ，再查一遍，走到计数器只有 \(1\) 的时候就停。复杂度 \(O(n+\sum |S_i|)\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int tot;

struct node {int cnt, son[26];} c[500007];

inline void insert(string &s) {
    int rt = 0;
    for (auto x : s) {
        x -= 'a';
        if (!c[rt].son[x]) c[rt].son[x] = ++tot;
        rt = c[rt].son[x];
        ++c[rt].cnt;
    }
}

inline int calc(string &s) {
    int ans = 0, rt = 0;
    for (auto x : s) {
        x -= 'a';
        rt = c[rt].son[x];
        if (c[rt].cnt == 1) return ans;
        ++ans;
    }
    return ans;
}

string str;

vector<string> s;

int main() {
    int n; cin >> n;
   	rep(i, 1, n) {cin >> str; s.pb(str); insert(str);}
    for (auto &st : s) printf("%d\n", calc(st));
    return 0;
}

F - Components

给一棵树 \((n\le 5000)\) ，问有多少个点集的导出子图恰好有 \(x=0,1,\dots,n\) 个联通分量（定义含极大性）。

树形背包计数，加一维 \(0/1\) 表示当前点选/不选，如果父子两个都上选会合并一个联通块。复杂度 \(O(n^2)\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#define N 5007
#define mod 998244353
inline int add(int x, int y) {return (x + y >= mod ? x + y - mod : x + y);}
inline int mul(int x, int y) {return 1ll * x * y % mod;}

int f[N][N][2], sz[N], n, g[N][2];

vector<int> e[N];

void dfs(int u, int fa) {
    sz[u] = 1;
    f[u][0][0] = f[u][1][1] = 1; 
    for (auto v : e[u])
        if (v != fa) {
            dfs(v, u);
            for (int j = 0; j <= sz[u] + sz[v]; ++j) {
                g[j][0] = f[u][j][0]; 
                g[j][1] = f[u][j][1];
                f[u][j][0] = f[u][j][1] = 0;
            }
            for (int j = sz[u] + sz[v]; j >= 0; --j) 
                for (int k = max(0, j - sz[u]); k <= min(j, sz[v]); ++k) {
                    f[u][j][0] = add(f[u][j][0], mul(g[j - k][0], add(f[v][k][0], f[v][k][1])));
                    f[u][j][1] = add(f[u][j][1], add(mul(g[j - k][1], f[v][k][0]), mul(g[j - k][1], f[v][k + 1][1])));
                }
            sz[u] += sz[v];
        }
}

int main() {
    n = rd();
    for (int i = 1; i < n; ++i) {
        int u = rd(), v = rd(); 
      	e[u].pb(v); e[v].pb(u);
    }
    dfs(1, 1);
    for (int i = 1; i <= n; ++i) printf("%d\n", add(f[1][i][0], f[1][i][1]));
    return 0;
}

G - Balance Update Query

有 \(n\ (n\le 2\times 10^5)\) 组数，开始第 \(i\) 组有 \(b_i\ (b_i\le 10^4)\) 个 \(a_i\ (a_i\le 10^9)\) ，接下来 \(q\) 次操作：

  • 1 x y 把 \(a_x\) 修改为 \(y\ (y\le 10^9)\)
  • 2 x y 把 \(b_x\) 修改为 \(y\ (y\le 10^4)\)
  • 3 x 查询所有数字的前 \(x\ (x\le 10^9)\) 大和。

离线，离散化全部做过 \(a_i\) 的值，以此为下标建立线段树。

节点维护价值区间内数字个数和 \(\sum\) 个数 \(\times\) 价值 ，查询在线段树上二分即可。复杂度 \(O(n\log n)\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#define N 300007
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid ((l + r) >> 1)

vector<int> w;

int a[N], b[N];

vector<tii> work;

int cnt[N << 2];

ll sum[N << 2];

inline void pushup(int rt) {
    cnt[rt] = cnt[ls] + cnt[rs];
    sum[rt] = sum[ls] + sum[rs]; 
}

void upd(int rt, int l, int r, int p, int dlt) {
    if (l == r) {
        cnt[rt] += dlt;
        sum[rt] += 1ll * dlt * w[l];
        return;
    }
    p <= mid ? upd(ls, l, mid, p, dlt) : upd(rs, mid + 1, r, p, dlt);
    pushup(rt);
}

ll query(int rt, int l, int r, int tot) {
    if (cnt[rt] < tot) return -1;
    if (l == r) return 1ll * tot * w[l];
    if (cnt[rs] >= tot) return query(rs, mid + 1, r, tot);
    else return query(ls, l, mid, tot - cnt[rs]) + sum[rs];
}

int main() {
    int n = rd(); 
    rep(i, 1, n) {a[i] = rd(); b[i] = rd(); w.pb(a[i]);}
    int q = rd();
    rep(i, 1, q) {
        int op = rd(), x = rd();
        if (op == 1) {int y = rd(); w.pb(y); work.eb(op, x, y);}
        else if (op == 2) work.eb(op, x, rd());
        else work.eb(op, x, 0);
    }
    
    w.pb(-1); sort(all(w)); w.erase(unique(all(w)), w.end());
    auto getw = [&](int x) {return lower_bound(all(w), x) - w.begin();};
    
    int m = w.size();
    rep(i, 1, n) {a[i] = getw(a[i]); upd(1, 1, m, a[i], b[i]);}
    for (auto [op, x, y] : work) 
        if (op == 3) printf("%lld\n", query(1, 1, m, x));
        else {
            upd(1, 1, m, a[x], -b[x]);
            op == 1 ? a[x] = getw(y) : b[x] = y;
            upd(1, 1, m, a[x], b[x]);
        } 
    return 0;
}

Ex - Directed Graph and Query

给定一个 \(n\ (n\le 2000)\) 个点的有向图，\(q\ (q\le 10^4)\) 次询问从 \(s_i\) 到 \(t_i\) 经过的节点编号最大值的最小值。

Floyd 最外层枚举到 \(k\) 的含义就是只经过编号为 \(1\dots k\) 的节点的最短路。

因此 bitset 维护传递闭包，每次更新完一个 \(k\) 就扫描全部询问，看看有没有已满足的即可。

复杂度 \(O(\frac{n^3}{64} + nq)\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define N 2007
#define M 10007

int ans[M], s[M], t[M];

bitset<N> adj[N];

int main() {
    int n = rd(), m = rd();
    rep(u, 1, n) adj[u][u] = true;
    rep(i, 1, m) {int u = rd(), v = rd(); adj[u][v] = true;}
    int q = rd();
    rep(i, 1, q) {s[i] = rd(); t[i] = rd(); ans[i] = -1;}
    rep(v, 1, n) {
        rep(u, 1, n) if (adj[u][v]) adj[u] |= adj[v]; 
        rep(i, 1, q) if (ans[i] == -1 && adj[s[i]][t[i]]) ans[i] = v;
    }
    rep(i, 1, q) printf("%d\n", ans[i] == -1 ? -1 : max({ans[i], s[i], t[i]}));
    return 0;
}