AtCoder Beginner Contest 213

发表于2021-08-24更新于2023-09-15字数统计3.3k阅读时长36分

比赛链接

D Takahashi Tour

Description

题目链接

Solution

vectorvector 存图，将后继节点从小到大排序，然后按序深搜即可。

Code

Takahashi Tour
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n;
vector<int> G[MAXN], ans;

void dfs(int now, int fa) {
    ans.push_back(now);
    for (auto& to : G[now]) {
        if (to == fa) continue;
        dfs(to, now);
        ans.push_back(now);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) sort(G[i].begin(), G[i].end());
    dfs(1, 1);
    for (auto& v : ans) cout << v << " ";
    return 0;
}

E Stronger Takahashi

Description

题目链接

Solution

建图后跑 DijkstraDijkstra 或者 01BFS01BFS，具体建法如下：

  • 设当前位置为 (i,j)(i,j)。
  • 由 (i,j)(i,j) 向四周的 '.' 连代价为 0 的边。这些点不需要 punch 即可到达。
  • 由 (i,j)(i,j) 向四周的 '#' 的 3×33×3 范围内的所有点连代价为 1 的边。若经由 '#' 到这些点，需要 punch 一次。

Code

Stronger Takahashi
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>

using namespace std;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 3e5 + 5, MOD = 1e9 + 7;

int H, W;
char g[505][505];

void print() {
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            cout << g[i][j];
        }
        cout << "\n";
    }
}

int getId(int x, int y) {
    if (!(1 <= x && x <= H && 1 <= y && y <= W)) return 0;
    return W * (x - 1) + y;
}

vector<pair<int, int>> G[MAXN];

void add(int u, int v, int w) {
    if (!u || !v) return;
    if (u == v) return;
    G[u].emplace_back(v, w);
}

int dis[MAXN], vis[MAXN];
void dijkstra() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    int cur, dist;
    for (int i = 1; i < MAXN; i++) dis[i] = 1e9;
    dis[getId(1, 1)] = 0;
    q.emplace(0, getId(1, 1));
    while (!q.empty()) {
        tie(dist, cur) = q.top();
        q.pop();
        if (vis[cur]) continue;
        for (auto& e : G[cur]) {
            int to = e.first, w = e.second;
            if (dis[to] > dis[cur] + w) {
                dis[to] = dis[cur] + w;
                q.emplace(dis[to], to);
            }
        }
        vis[cur] = true;
    }
    cout << dis[getId(H, W)] << "\n";
}

vector<pair<int, int>> delta = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 0}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

int main() {
    boost;
    cin >> H >> W;
    for (int i = 1; i <= H; i++) {
        cin.ignore(10, '\n');
        for (int j = 1; j <= W; j++) {
            cin >> g[i][j];
        }
    }
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if (g[i - 1][j] == '#') {
                for (auto& d : delta) {
                    int toi = i - 1 + d.first;
                    int toj = j + d.second;
                    add(getId(i, j), getId(toi, toj), 1);
                }
            } else if (g[i - 1][j] == '.') {
                add(getId(i, j), getId(i - 1, j), 0);
            }

            if (g[i + 1][j] == '#') {
                for (auto& d : delta) {
                    int toi = i + 1 + d.first;
                    int toj = j + d.second;
                    add(getId(i, j), getId(toi, toj), 1);
                }
            } else if (g[i + 1][j] == '.') {
                add(getId(i, j), getId(i + 1, j), 0);
            }

            if (g[i][j + 1] == '#') {
                for (auto& d : delta) {
                    int toi = i + d.first;
                    int toj = j + 1 + d.second;
                    add(getId(i, j), getId(toi, toj), 1);
                }
            } else if (g[i][j + 1] == '.') {
                add(getId(i, j), getId(i, j + 1), 0);
            }

            if (g[i][j - 1] == '#') {
                for (auto& d : delta) {
                    int toi = i + d.first;
                    int toj = j - 1 + d.second;
                    add(getId(i, j), getId(toi, toj), 1);
                }
            } else if (g[i][j - 1] == '.') {
                add(getId(i, j), getId(i, j - 1), 0);
            }
        }
    }
    dijkstra();
    return 0;
}

F Common Prefixes

Description

题目链接

Solution

本题求两个后缀的 LCPLCP，等价于将原串翻转后，求某两个前缀的 LCSLCS。我们知道 SAMSAM 的后缀树中，原串两个前缀对应节点的 LCALCA 是这两个前缀的 LCSLCS 对应的节点（该 LCSLCS 一定是这个状态中最长的一个串）。利用这个性质可以求解本题。

令 G(Sk)=f(Sk,S1)+f(Sk,S2)+…+f(Sk,SN)G(S_k)=f(S_k,S_1)+f(S_k,S_2)+\ldots+f(S_k,S_N)。显然对每个 SkS_k 求 f(Sk,S1),f(Sk,S2),…,f(Sk,SN)f(S_k,S_1),f(S_k,S_2),\ldots,f(S_k,S_N) 效率太低。我们不妨考虑每个 LCSLCS 对 G(S1),…,G(Sn)G(S_1),\dots,G(S_n) 的贡献。具体的，我们预处理出后缀树上每个节点 uu 的子树中包含前缀的数目，记为 fuf_u，那么 uu 对儿子 vv 的子树中所有前缀的答案贡献为 (fu−fv)∗maxsubu(f_u-f_v)*maxsub_u。此外，若 uu 包含了某一前缀 SiS_i，那么 G(Si)G(S_i) 还要加上 fu∗maxsubuf_u*maxsub_u。

上述解法涉及子树修改加单次查询，利用 DFSDFS 序 + 差分即可。

Code

Common Prefixes
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 1E6 + 5;
const int MOD = 1E9 + 7;
string s;
int n;
array<LL, MAXN * 2> dp, in, out, ans;
vector<int> G[MAXN * 2], pre;

struct SAM {
    int size, last;
    // 各状态最长子串长度，后缀链接
    vector<int> len, link;
    // 转移数组
    vector<vector<int>> to;
    // 字符串长度，字符集大小
    SAM(int _len, int _szC = 26) : size(0), last(0) {
        len.resize(_len * 2, 0);
        link.resize(_len * 2, -1);
        to.resize(_len * 2, vector<int>(_szC, -1));
    }

    void insert(int c) {
        int cur = ++size, p = last;
        dp[cur] = 1, pre.push_back(cur);
        len[cur] = len[last] + 1;
        while (p != -1 && to[p][c] == -1) {
            to[p][c] = cur;
            p = link[p];
        }
        if (p == -1)
            link[cur] = 0;
        else {
            int q = to[p][c];
            if (len[q] == len[p] + 1)
                link[cur] = q;
            else {
                int clone = ++size;
                len[clone] = len[p] + 1;
                to[clone] = to[q];
                link[clone] = link[q];
                while (p != -1 && to[p][c] == q) {
                    to[p][c] = clone;
                    p = link[p];
                }
                link[q] = link[cur] = clone;
            }
        }
        last = cur;
    }

    void update(int l, int r, LL v) { ans[l] += v, ans[r + 1] -= v; }

    void dfs(int now) {
        static int times = 0;
        in[now] = times++;
        for (auto& to : G[now]) {
            if (to == -1) continue;
            dfs(to);
            dp[now] += dp[to];
        }
        out[now] = times;
        for (auto& to : G[now]) {
            if (to == -1) continue;
            update(in[to], out[to] - 1, 1ll * len[now] * (dp[now] - dp[to]));
        }
        update(in[now], in[now], 1ll * len[now] * dp[now]);
    }

    void calcLCPs() {
        for (int i = 1; i <= size; i++)
            if (link[i] != -1) G[link[i]].push_back(i);
        dfs(0);
        for (int i = 1; i <= size; i++) ans[i] += ans[i - 1];
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> s;
    reverse(s.begin(), s.end());
    SAM mySAM(s.size());
    for (auto& c : s) mySAM.insert(c - 'a');
    mySAM.calcLCPs();
    for (int i = pre.size() - 1; ~i; i--) cout << ans[in[pre[i]]] << endl;
    return 0;
}

G Connectivity 2

Description

题目链接

Solution

设 f[S]f[S] 表示点集为 SS 的联通子图的个数，g[S]g[S] 表示点集为 SS 的子图的个数，那么答案可以表示为 ∑{1,k}⊆S⊆Vf[S]g[V−S]\sum\limits_{\{1,k\}⊆S⊆V}f[S]g[V-S]。下面考虑如何求解 f[S],g[S]f[S],g[S]。

设有 mm 条边两端都在 SS 中，则 g[S]=2mg[S]=2^m。求 f[S]f[S] 可以利用容斥，从 g[S]g[S] 中扣除不联通的部分，而不联通的部分可以拆成一个联通子图和一个另一个子图，因此可以粗略得到 f[S]=g[S]−∑T⊆Sf[T]g[S−T]f[S] = g[S] - \sum\limits_{T⊆S} f[T]g[S-T]，这可通过枚举子集求得。由于 g[S]g[S] 是包含 f[S]f[S] 的，因此 f[T]g[S−T]f[T]g[S-T] 和 f[S−T]g[T]f[S-T]g[T] 都包含了 f[T]f[S−T]f[T]f[S-T]，这一部分要扣除，故当 T>S−TT>S-T 时，要从 g[S−T]g[S-T] 中扣除 f[S−T]f[S-T]。

求 g[S]g[S] 的时间复杂度为 O(m2n)O(m2^n)，求 f[S]f[S] 的时间复杂度为 O(3n)O(3^n)，因此总的时间复杂度为 O(3n+m2n)O(3^n+m2^n)。

Code

Connectivity 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 18;
const int MAXS = (1 << 17) - 1;
const int MOD = 998244353;
int n, m;
int u[MAXN * MAXN], v[MAXN * MAXN];
LL f[MAXS], g[MAXS];

LL qpow(LL a, LL b, LL MOD) {
    LL ans = 1, base = a % MOD;
    while (b) {
        if (b & 1) ans = ans * base % MOD;
        b >>= 1, base = base * base % MOD;
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i];
        u[i]--, v[i]--;
    }
    for (int s = 0; s < (1 << n); s++) {
        int cnte = 0;
        for (int i = 1; i <= m; i++)
            if (((s >> u[i]) & 1) && ((s >> v[i]) & 1)) cnte++;
        g[s] = qpow(2, cnte, MOD);
        f[s] = g[s];
        for (int t = s - 1; t > 0; t--) {
            t &= s;
            f[s] -= f[t] * (g[s - t] - (t > s - t ? f[s - t] : 0)) % MOD;
            f[s] %= MOD;
        }
    }
    for (int k = 1; k < n; k++) {
        int ans = 0;
        for (int s = 0; s < (1 << n); s++) {
            if ((s & 1) && ((s >> k) & 1)) {
                ans += f[s] * g[(1 << n) - 1 - s] % MOD;
                ans %= MOD;
            }
        }
        cout << (ans + MOD) % MOD << endl;
    }
    return 0;
}

H Stroll

Description

题目链接

Solution

设 ds,td_{s,t} 表示以 ss 为终点，长度为 tt 的路径条数。

按 tt 递增的顺序，并按边转移，可以得到状态转移如下：

ds,t=∑bi=s,1≤i≤M(∑0≤u≤t−1dai,u∗pi,t−u)+∑ai=s,1≤i≤M(∑0≤u≤t−1dbi,u∗pi,t−u)d_{s,t}=\sum\limits_{bi=s, 1\le i\le M}(\sum\limits_{0\le u\le t-1}d_{a_i, u} * p_{i,t-u}) + \sum\limits_{ai=s, 1\le i\le M}(\sum\limits_{0\le u\le t-1}d_{b_i, u} * p_{i,t-u})

上述转移过程的时间复杂度为 O(MT2)O(MT^2)。观察式子发现可以通过分治 fftfft 优化。见 分治 fft 模板。

即对于区间 l=0,r=tl = 0, r = t，先递归求出 d1...n,l...midd_{1...n, l...mid} 的结果，然后枚举每条边，通过卷积计算 dfrom,l...mid∗p...d_{from, l...mid} * p_{...} 对 dto,mid+1...rd_{to, mid + 1...r} 的贡献。

最终的时间复杂度为 O(MTlog2T)O(MTlog^2T)。

Code

Stroll
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << " = " << x << endl
#define PI acos(-1)
#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 4e4 + 5;

namespace NTT {
    constexpr int NR = 1 << 22, g = 3, gi = 332748118, mod = 998244353;

    long long qpow(long long a, long long b) {
        long long res = 1;
        while (b) {
            if (b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }

    int R[4000001];
    void init(int& sz) {
        if (__builtin_popcount(sz) != 1) sz = 1 << (1 + (int)log2(sz));
        for (int i = 0; i < sz; i++) R[i] = (R[i >> 1] >> 1) | ((i & 1) ? (sz >> 1) : 0);
    }

    void dft(long long a[], int sz, int type) {
        for (int i = 0; i < sz; i++)
            if (i < R[i]) swap(a[i], a[R[i]]);
        for (int m = 2; m <= sz; m <<= 1) {
            long long gn = qpow(type == 1 ? g : gi, (mod - 1) / m); // 单位原根 g_n
            for (int k = 0; k < sz; k += m) {
                long long g0(1);
                for (int j = 0; j < m / 2; j++) {
                    long long t = g0 * a[k + j + m / 2] % mod;
                    long long u = a[k + j];
                    a[k + j] = (u + t) % mod;
                    a[k + j + m / 2] = (u - t + mod) % mod;
                    g0 = g0 * gn % mod;
                }
            }
        }
        if (type == -1) {
            long long inv = qpow(sz, mod - 2);
            for (int i = 0; i < sz; i++) a[i] = a[i] * inv % mod;
        }
    }
}

namespace Polynomial {
    using namespace NTT;

    void Convolution(int n, int m, int a[], int b[], int c[]) { // a[0, n] b[0, m]
        int N = n + m + 1;
        init(N);
        long long f[N], g[N];
        for (int i = 0; i < N; i++) f[i] = g[i] = 0;
        for (int i = 0; i <= n; i++) f[i] = a[i];
        for (int i = 0; i <= m; i++) g[i] = b[i];
        dft(f, N, 1), dft(g, N, 1);
        long long res[N];
        for (int i = 0; i < N; i++) res[i] = 0;
        for (int i = 0; i < N; i++) res[i] = f[i] * g[i] % mod;
        dft(res, N, -1);
        for (int i = 0; i <= n + m; i++) c[i] = res[i];
    }
};

int n, m, t;
int d[10][MAXN];
int p[10][10][MAXN];
vector<pair<int, int>> e;

using namespace Polynomial;
void divide_and_conquer(int l, int r) {
    if (l == r) {
        if (!l) d[0][0] = 1;
        return ;
    }
    int mid = (l + r) >> 1;
    divide_and_conquer(l, mid);

    for (auto& i : e) {
        int x = i.first, y = i.second;
        int f[mid - l + 1], g[r - l + 1], c[r - l + 1 + mid - l + 1];
        for (int i = 0; i < mid - l + 1; i++) f[i] = d[x][i + l];
        for (int i = 0; i < r - l + 1; i++) g[i] = p[x][y][i];
        Convolution(mid - l, r - l, f, g, c);
        for (int i = mid + 1; i <= r; i++) d[y][i] = (d[y][i] + c[i - l]) % mod;

        for (int i = 0; i < mid - l + 1; i++) f[i] = d[y][i + l];
        Convolution(mid - l, r - l, f, g, c);
        for (int i = mid + 1; i <= r; i++) d[x][i] = (d[x][i] + c[i - l]) % mod;
    }

    divide_and_conquer(mid + 1, r);
}

int main() {
    boost;
    cin >> n >> m >> t;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b, a--, b--;
        e.push_back({a, b});
        for (int j = 1; j <= t; j++) cin >> p[a][b][j];
    }
    divide_and_conquer(0, t);
    cout << d[0][t] << "\n";
    return 0;
}