今天生日上大分，${\color{red}win}$！

虽然没做出来期望 $dp$ 题，但是最后三分钟极限过了道网络流，罚时很逆天！

截屏2022-08-06 23.35.43

A - Full House

题目描述

给出 $5$ 个数，判断是否可以分成 $3$ 个一样的和 $2$ 个一样的。

思路

暴力。

题目意思看瓢了， $wa$了 $3$ 发。

代码

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
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int a[5];
    map< int, int > cnt;
    for (int i = 1; i <= 5; ++ i) {
        cin >> a[i];
        ++ cnt[a[i]];
    }
    for (int i = 1; i <= 5; ++ i) {
        for (int j = 1; j <= 5; ++ j) {
            if (i == j) continue;
                if (cnt[a[i]] == 3 && cnt[a[j]] == 2) {
                    cout << "Yes" << '\n';
                    exit(0);
                }
        }
    }
    cout << "No" << '\n';
    return 0;
}

B - Ancestor

题目描述

给出以 $1$ 为根节点的树， 计算 $1$ 到 $n$ 的距离。

思路

暴力

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    cin >> n;
    vector< int > d(n + 1);
    for (int i = 2; i <= n; ++ i) {
        int x;
        cin >> x;
        d[i] = d[x] + 1;
    }
    cout << d[n] << '\n';
    return 0;
}

C - Monotonically Increasing

题目描述

求出所有严格递增的且长度为 $m$ ，值域为 $[1, n]$ 的数列。

思路

就暴力？最开始接触的 $dfs$。

代码

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
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 20, MOD = 998244353, INF = 0x3f3f3f3f;

int n, m;
int a[N];
void dfs(int x, int cnt) {
    if (cnt == m) {
        for (int i = 1; i <= m; ++ i) {
            cout << a[i] << " \n"[i == m];
        }
        return;
    }
    for (int i = x + 1; i <= n; ++ i) {
        a[cnt + 1] = i;
        dfs(i, cnt + 1);
    }
}
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n >> m;
    swap(n, m);
    dfs(0, 0);
    return 0;
}

D - Left Right Operation

题目描述

一个长度为 $n$ 的序列，允许你进行若干次如下操作

  • 选择一个数 $x$ ，将 $a_1,a_2, \cdots ,a_{1+x-1}$ 全部置为 L
  • 选择一个数 $y$ ，将 $a_{n-y+1}, \cdots ,a_{n-1},a_n$ 全部置为 R

求最终 $\sum_{1}^{n}a_i$ 的最小值。

思路

一开始想的贪心，错了几次之后改为 $dp$ 了。

设 $f_{i,0}$ 为 $a_i$ 不变为 L 时的前缀最小值，相应的 $f_{i,1}$ 为 $a_i$ 变为 L 时的前缀最小值。

设 $g_{i,0}$ 为 $a_i$ 不变为 R 时的后缀最小值，相应的 $g_{i,1}$ 为 $a_i$ 变为 R 时的后缀最小值。

最后我们枚举中间点，将四个状态取最小值即可。

代码

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
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;

int n, L, R, a[N];
LL dp[N][2], sum[N], fdp[N][2];
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n >> L >> R;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        dp[i][0] = dp[i][1] = 1e18;
        fdp[i][0] = fdp[i][1] = 1e18;
    }
    for (int i = 1; i <= n; ++ i) {
        dp[i][0] = min({dp[i - 1][0] + a[i], dp[i - 1][1] + L});
        dp[i][1] = dp[i - 1][1] + L;
    }
    for (int i = n; i >= 1; -- i) {
        fdp[i][0] = min({fdp[i + 1][0] + a[i], fdp[i + 1][1] + R});
        fdp[i][1] = fdp[i + 1][1] + R;
    }
    LL ans = 1e18;
    for (int i = 0; i <= n; ++ i) {
        ans = min({ans, dp[i][0] + fdp[i + 1][0], dp[i][0] + fdp[i + 1][1], dp[i][1] + fdp[i + 1][0], dp[i][1] + fdp[i + 1][1]});
    }
    cout << ans << '\n';
    return 0;
}

E - Sugoroku 3

题目描述

起点为 $1$，当你目前处于 $x(1\leq x \leq n - 1)$ 时，你会等概率地停留在原地或者到达 $x+y(1\leq y \leq A_i)$ ，求到达 $n$ 点的期望步数。

思路

我们令 $dp_i$ 代表从 $i$ 走到 $n$ 的期望步数，$dp_n=0$。

那么 $dp_i = \frac { 1 + \sum_{j=1}^{A_i} dp_{i+j}} {A_i} + 1$。等式上方的 1 代表停留在原地不会走，但是步数增加了 1。

求和随便用啥来维护都可以。

代码

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
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;

int n, a[N], dp[N];
struct FenWick {
    int n;
    vector< int > c;
    FenWick(int n) : n(n), c(n + 1) {}
    void add(int i, int d) {
        for (; i <= n; i += i & -i) {
            c[i] += d;
            c[i] %= MOD;
        }
    }
    void add(int l, int r, int d) {
        add(l, d);
        add(r + 1, -d);
    }
    int get(int i) {
        int sum = 0;
        for (; i; i -= i & -i) {
            sum += c[i];
            sum %= MOD;
        }
        return sum;
    }
    int get(int l, int r) { 
        return (get(r) - get(l - 1) + MOD) % MOD;
    }
};
LL ksm(LL x, LL y, LL res = 1) {
    for (; y; y >>= 1, x = x * x % MOD) {
        if (y & 1) {
            res = res * x % MOD;
        }
    }
    return res;
}
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n;
    for (int i = 1; i < n; ++ i) {
        cin >> a[i];
    }
    FenWick d(n);
    for (int i = n - 1; i >= 1; -- i) {
        dp[i] = (1 + (d.get(i + 1, i + a[i]) + 1) % MOD * ksm(a[i], MOD - 2) % MOD) % MOD;
        d.add(i, dp[i]);
    }
    cout << dp[1] << '\n';
    return 0;
}

F - Tournament

题目描述

有 $2^n$ 个人打比赛， 我们设当前场上还剩下 $2m $ 个人 ，那么第 $2i - 1$ 个人与第 $2i$ 个人比赛。比赛胜利者晋级到下一轮，一共进行 $n$ 轮比赛。

设 $C_{i,j}$ 为第 $i$ 个人赢 $j$ 轮能得到的收益，求所有人得到收益的总和的最大值。

思路

可以看出比赛过程构成了一颗深度为 $n + 1$ 的满二叉树，其中最后一层为 $1 \backsim 2^n$ 。

我们不妨从根节点出发，枚举左子树或者右子树胜利的最大收益，设 $dp_{i,j}$ 为枚举到第 $i$ 个人连赢 $j$ 场能得到的最大收益，当枚举到最后一层也就是叶子结点时，我们便能得知每个人的胜场情况。

代码

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
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 17, MOD = 998244353, INF = 0x3f3f3f3f;

int n, c[1 << N][N];
LL dp[1 << N][N];
LL dfs(int x, int win) {
    if (x >= 1 << n) {
        return c[x ^ (1 << n)][win];
    }
    if (~dp[x][win]) {
        return dp[x][win];
    }
    LL lwin = dfs(x << 1, win + 1) + dfs(x << 1 | 1, 0);
    LL rwin = dfs(x << 1, 0) + dfs(x << 1 | 1, win + 1);
    return dp[x][win] = max(lwin, rwin);
}
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n;
    for (int i = 0; i < 1 << n; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            cin >> c[i][j];
        }
    }
    memset(dp, -1, sizeof dp);
    cout << dfs(1, 0) << '\n';
    return 0;
}

G - Erasing Prime Pairs

题目描述

给出 $n$ 种不同的数 $a_i$ ，以及每个 $a_i$ 的个数 $b_i$ 。

你每次都能拿出两个数$x \ y$ ，当 $x+y$ 为质数时，你可以将它们消除。

求能消除的最大对数。

思路

一眼网络流，但是在建图上挂了几次，这题的核心在于处理 $1$ 的归属问题，$1$ 可以和自身匹配构成 $2$ ，或者和其他的偶数构成一个质数。

我一开始按照奇数和偶数建图，把 $1$ 单独拿出来，然后跑 $Dinic$ ，但是发现这样不能使答案最优。

然后我考虑拆点跑最大流，这样就把这些限制因素给排除了，最后输出答案的一半即可。

很刺激，最后 $3 \min$ 过掉了。

代码

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
115
116
117
118
119
120
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

#define int LL
const int N = 300, INF = 1e12;
struct Edge {
    int from, to, cap, flow;

    Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};
struct Dinic {
    int n, m, S, T;
    vector< Edge > edges;
    vector< int > G[N];
    int d[N], cur[N];
    bool vis[N];

    Dinic(int S, int T) : S(S), T(T) {}
    
    void AddEdge(int from, int to, int cap) {
        edges.push_back(Edge(from, to, cap, 0));
        edges.push_back(Edge(to, from, 0, 0));
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }

    bool BFS() {
        memset(vis, false, sizeof(vis));
        queue<int> Q;
        Q.push(S);
        d[T] = 0;
        vis[S] = true;
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            for (int i = 0; i < G[x].size(); ++ i) {
                Edge& e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = true;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[T];
    }

    int DFS(int x, int a) {
        if (x == T || a == 0) {
            return a;
        }
        int flow = 0, f;
        for (int& i = cur[x]; i < G[x].size(); ++ i) {
            Edge& e = edges[G[x][i]];
            if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0) {
                    break;
                }
            }
        }
        return flow;
    }

    int Maxflow() {
        int flow = 0;
        while (BFS()) {
            memset(cur, 0, sizeof(cur));
            flow += DFS(S, INF);
        }
        return flow;
    }
};
int v[30000005], prime[30000005], tot;
void pre() {
    for (int i = 2; i <= 30000000; ++ i) {
        if (!v[i]) {
            v[i] = i;
            prime[++ tot] = i;
        }
        for (int j = 1; j <= tot && 1LL * prime[j] * i <= 30000000; ++ j) {
            if (prime[j] > v[i]) {
                break;
            }
            v[prime[j] * i] = prime[j];
        }
    }
}
int n;
pair< int, int > a[N];
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    pre();
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        int x, y;
        cin >> x >> y;
        a[i] = {x, y};
    }
    Dinic d(0, 250);
    for (int i = 1; i <= n; ++ i) {
        d.AddEdge(0, i, a[i].second);
        d.AddEdge(i + n, 250, a[i].second);
    }
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            if (v[a[i].first + a[j].first] == a[i].first + a[j].first) {
                d.AddEdge(i, j + n, INF);
            }
        }
    }
    cout << d.Maxflow() / 2 << '\n';
    return 0;
}