2025夏季个人训练赛第二十九场

早上不知道要不要打，交了一道题，后来说可以不打了，但是来都来了，所以又打了一上午……

B. 甜点#

其实就是个多重背包问题，二进制拆分一下暴力做两次就可以了。

1
#include <iostream>
2
#include <vector>
3
#include <cstring>
4

5
using namespace std;
6
const int N = 210;
7
const int M = 50010;
8

9
int t[N], u[N], v[N];
10
int x[N], y[N], z[N];
11
int f[M];
12

13
int main() {
14
    memset(f, 0x3f, sizeof(f));
15
    int n, m, p, k;
16
    scanf("%d%d%d%d", &n, &m, &p, &k);
17
    for (int i = 1; i <= n; ++i) {
18
        scanf("%d%d%d", &t[i], &u[i], &v[i]);
19
    }
20
    for (int i = 1; i <= m; ++i) {
21
        scanf("%d%d%d", &x[i], &y[i], &z[i]);
22
    }
23
    f[0] = 0;
24
    for (int i = 1; i <= n; ++i) {
25
        for (int b = 0; b < 8; ++b) {
26
            if (v[i] > (1 << b)) {
27
                v[i] -= (1 << b);
28
                int tt = (1 << b) * t[i], uu = (1 << b) * u[i];
29
                if (p - tt < 0) f[p] = min(f[p], uu);
30
                else
31
                    for (int j = p - tt; j < p; ++j) {
32
                        f[p] = min(f[p], f[j] + uu);
33
                    }
34
                for (int j = p - 1; j >= tt; --j) {
35
                    f[j] = min(f[j], f[j - tt] + uu);
36
                }
37
            }
38
            else {
39
                int tt = v[i] * t[i], uu = v[i] * u[i];
40
                if (p - tt < 0) f[p] = min(f[p], uu);
41
                else
42
                    for (int j = p - tt; j < p; ++j) {
43
                        f[p] = min(f[p], f[j] + uu);
44
                    }
45
                for (int j = p - 1; j >= tt; --j) {
46
                    f[j] = min(f[j], f[j - tt] + uu);
47
                }
48
                break;
49
            }
50
        }
51
    }
52
    int minu = f[p];
53
    printf("%d\n", minu);
54
    memset(f, 0x3f, sizeof(f));
55
    f[0] = 0;
56
    for (int i = 1; i <= m; ++i) {
57
        for (int b = 0; b < 8; ++b) {
58
            if (z[i] > (1 << b)) {
59
                z[i] -= (1 << b);
60
                int tt = (1 << b) * x[i], uu = (1 << b) * y[i];
61
                if (minu - tt < 0) f[minu] = min(f[minu], uu);
62
                else
63
                    for (int j = minu - tt; j < minu; ++j) {
64
                        f[minu] = min(f[minu], f[j] + uu);
65
                    }
66
                for (int j = minu - 1; j >= tt; --j) {
67
                    f[j] = min(f[j], f[j - tt] + uu);
68
                }
69
            }
70
            else {
71
                int tt = x[i] * z[i], uu = y[i] * z[i];
72
                if (minu - tt < 0) f[minu] = min(f[minu], uu);
73
                else
74
                    for (int j = minu - tt; j < minu; ++j) {
75
                        f[minu] = min(f[minu], f[j] + uu);
76
                    }
77
                for (int j = minu - 1; j >= tt; --j) {
78
                    f[j] = min(f[j], f[j - tt] + uu);
79
                }
80
                break;
81
            }
82
        }
83
    }
84
    if (f[minu] <= k) printf("%d\n", f[minu]);
85
    else printf("FAIL\n");
86
    return 0;
87
}

C. 喜爱#

直接暴力就行了，顶多 60 位，(59 * (59 + 1)) / 2 + 1 = 1771，一共就这点数。

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <bitset>
5

6
using namespace std;
7

8
typedef long long LL;
9
vector<LL> v;
10

11
void init() {
12
    v.emplace_back(0);
13
    for (int b = 1; b <= 60; ++b) {
14
        LL msk = (1LL << b) - 1;
15
        for (int i = b - 2; i >= 0; --i) {
16
            v.emplace_back(msk ^ (1LL << i));
17
            // cout << bitset<60>(msk ^ (1LL << i)) << endl;
18
        }
19
    }
20
}
21

22
int count(LL x) {
23
    if (x == -1) return 0;
24
    else {
25
        int l = 0, r = v.size() - 1;
26
        while (l < r) {
27
            int mid = l + r + 1 >> 1;
28
            if (v[mid] <= x) l = mid;
29
            else r = mid - 1;
30
        }
31
        return l + 1;
32
    }
33
}
34

35
int main() {
36
    init();
37
    int T;
38
    scanf("%d", &T);
39
    while (T--) {
40
        LL l, r;
41
        scanf("%lld%lld", &l, &r);
42
        printf("%d\n", count(r) - count(l - 1));
43
    }
44
    return 0;
45
}

D. 计算#

我发现了一种稍微取巧一点的做法，开一个 stringstream 初始化一下原来的表达式，每次读入的时候 peek 一下检验是数字还是字符，然后直接用对应的数据类型 >> 就读进去了，其他地方还是正常的中缀表达式求值，开两个栈模拟即可。

刚开始我其实没用 peek，是真读进来一个字符检查一下如果 isdigit 再开一个 int 读，然后被 100 卡了，先读一个 1，然后新的 int 读进来一个 0，然后这个数字就变成 10 了😭

1
#include <iostream>
2
#include <sstream>
3
#include <map>
4

5
using namespace std;
6

7
int num[50], tp1;
8
char op[50], tp2;
9
map<char, int> mp = {{'(', 0}, {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}};
10

11
void calc() {
12
    int &n1 = num[tp1 - 1], n2 = num[tp1], o = op[tp2];
13
    if (o == '+') n1 += n2;
14
    else if (o =='-') n1 -= n2;
15
    else if (o == '*') n1 *= n2;
16
    else if (o == '/') n1 /= n2;
17
    else if (o == '^') {
18
        int bs = n1;
19
        n1 = 1;
20
        for (int i = 0; i < n2; ++i) n1 *= bs;
21
    }
22
    tp1--, tp2--;
23
}
24

25
int main() {
26
    string s;
27
    cin >> s;
28
    stringstream ss(s);
29
    char c;
30
    while (ss.peek() != EOF) {
31
        if (isdigit(ss.peek())) {
32
            int t;
33
            ss >> t;
34
            num[++tp1] = t;
35
        }
36
        else {
37
            char c;
38
            ss >> c;
39
            if (c == '(') op[++tp2] = c;
40
            else if (c == ')') {
41
                while (op[tp2] != '(') calc();
42
                tp2--;
43
            }
44
            else {
45
                while (mp[op[tp2]] >= mp[c]) calc();
46
                op[++tp2] = c;
47
            }
48
        }
49
    }
50
    while (tp1 > 1) calc();
51
    printf("%d\n", num[tp1]);
52
    return 0;
53
}

E. 子序列连续和#

很水，前缀和 + 二分。

1
#include <iostream>
2

3
using namespace std;
4
const int N = 100010;
5
long long a[N];
6

7
int main() {
8
    int n, s;
9
    scanf("%d%d", &n, &s);
10
    for (int i = 1; i <= n; ++i) {
11
        scanf("%lld", &a[i]);
12
        a[i] += a[i - 1];
13
    }
14
    int res = 0x3f3f3f3f;
15
    for (int i = 1; i <= n; ++i) {
16
        int l = 0, r = i;
17
        while (l < r) {
18
            int mid = l + r + 1 >> 1;
19
            if (a[i] - a[mid] >= s) l = mid;
20
            else r = mid - 1;
21
        }
22
        if (a[i] - a[l] >= s) res = min(res, i - l);
23
    }
24
    printf("%d\n", res == 0x3f3f3f3f ? 0 : res);
25
    return 0;
26
}

G. 苹果树（tree）^补#

这道当时没想到，后来看了题解，统计的是每条树边被非树边覆盖的次数，枚举边统计答案

如果没有覆盖，这条边是一个桥，删了他之后剩下的非树边随便删，贡献 m；
如果覆盖一次，删这条树边只能同时删覆盖他的非树边，贡献 1；
如果覆盖多次，那删了这条边无论怎么删别的都是连通的，贡献 0.

问题就转化成了一个树上差分。

1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5

6
typedef long long LL;
7
const int N = 300010;
8
vector<int> ed[N];
9
int s[N], f[N][20], dep[N];
10
int n, m;
11
LL res;
12

13
void dfs(int x) {
14
    for (int i = 1; i < 20; ++i) {
15
        f[x][i] = f[f[x][i - 1]][i - 1];
16
    }
17
    for (int y : ed[x]) {
18
        if (y == f[x][0]) continue;
19
        f[y][0] = x;
20
        dep[y] = dep[x] + 1;
21
        dfs(y);
22
    }
23
}
24

25
int lca(int x, int y) {
26
    if (dep[y] > dep[x]) swap(x, y);
27
    for (int i = 19; i >= 0; --i) {
28
        if (dep[f[x][i]] >= dep[y]) x = f[x][i];
29
    }
30
    if (x == y) return x;
31
    for (int i = 19; i >= 0; --i) {
32
        if (f[x][i] != f[y][i]) {
33
            x = f[x][i], y = f[y][i];
34
        }
35
    }
36
    return f[x][0];
37
}
38

39
void dfs2(int x) {
40
    for (int y : ed[x]) {
41
        if (y == f[x][0]) continue;
42
        dfs2(y);
43
        if (s[y] == 0) res += m;
44
        else if (s[y] == 1) res++;
45
        s[x] += s[y];
46
    }
47
}
48

49
int main() {
50
    scanf("%d%d", &n, &m);
51
    for (int i = 1; i < n; ++i) {
52
        int x, y;
53
        scanf("%d%d", &x, &y);
54
        ed[x].emplace_back(y);
55
        ed[y].emplace_back(x);
56
    }
57
    dep[1] = 0;
58
    dfs(1);
59
    for (int i = 1; i <= m; ++i) {
60
        int x, y;
61
        scanf("%d%d", &x, &y);
62
        s[x]++, s[y]++;
63
        s[lca(x, y)] -= 2;
64
    }
65
    dfs2(1);
66
    printf("%lld\n", res);
67
    return 0;
68
}

I. 狼和羊的故事 ^补#

开一个源点一个汇点 🐑 (->空地) ->🐺 求最小割

1
#include <iostream>
2
#include <cstring>
3
#include <queue>
4

5
using namespace std;
6

7
const int N = 10010;
8
int head[N], ne[N * 6], ver[N * 6], w[N * 6], tot = 1;
9
int mp[110][110], dis[N], pre[N];
10
bool vis[N];
11
int n, m;
12
int S, T;
13
int cur[N], dep[N];
14

15
void add(int x, int y, int z) {
16
    ver[++tot] = y;
17
    ne[tot] = head[x];
18
    head[x] = tot;
19
    w[tot] = z;
20
}
21

22
int id(int x, int y) {
23
    return (x - 1) * m + y;
24
}
25

26
bool bfs() {
27
    memset(dep, 0, sizeof(dep));
28
    cur[S] = head[S];
29
    dep[S] = 1;
30
    queue<int> q;
31
    q.emplace(S);
32
    while (!q.empty()) {
33
        int x = q.front();
34
        q.pop();
35
        for (int i = head[x]; i; i = ne[i]) {
36
            int y = ver[i];
37
            if (dep[y] || !w[i]) continue;
38
            dep[y] = dep[x] + 1;
39
            cur[y] = head[y];
40
            if (y == T) return true;
41
            q.emplace(y);
42
        }
43
    }
44
    return false;
45
}
46

47
int find(int x, int lim) {
48
    if (x == T) return lim;
49
    int flow = 0;
50
    for (int i = cur[x]; i && flow < lim; i = ne[i]) {
51
        int y = ver[i];
52
        if (dep[y] == dep[x] + 1 && w[i]) {
53
            int t = find(y, min(w[i], lim - flow));
54
            if (!t) dep[y] = -1;
55
            w[i] -= t, w[i ^ 1] += t, flow += t;
56
        }
57
    }
58
    return flow;
59
}
60

61
int dinic() {
62
    int res = 0, flow;
63
    while (bfs()) while (flow = find(S, 0x3f3f3f3f)) res += flow;
64
    return res;
65
}
66

67
int main() {
68
    scanf("%d%d", &n, &m);
69
    int t = n * m + 1;
70
    for (int i = 1; i <= n; ++i) {
71
        for (int j = 1; j <= m;++j) {
72
            scanf("%d", &mp[i][j]);
73
            if (mp[i][j] == 1) {
74
                add(0, id(i, j), N), add(id(i, j), 0, 0);
75
                if (i < n && mp[i + 1][j] != 1) add(id(i, j), id(i + 1, j), 1), add(id(i + 1, j), id(i, j), 0);
76
                if (j < m && mp[i][j + 1] != 1) add(id(i, j), id(i, j + 1), 1), add(id(i, j + 1), id(i, j), 0);
77
            }
78
            else if (mp[i][j] == 2) {
79
                add(id(i, j), t, N), add(t, id(i, j), N);
80
                if (i < n && mp[i + 1][j] != 1) add(id(i, j), id(i + 1, j), 0), add(id(i + 1, j), id(i, j), 1);
81
                if (j < m && mp[i][j + 1] != 1) add(id(i, j), id(i, j + 1), 0), add(id(i, j + 1), id(i, j), 1);
82
            }
83
            else {
84
                if (i < n) {
85
                    if (mp[i + 1][j] == 0) add(id(i, j), id(i + 1, j), 1), add(id(i + 1, j), id(i, j), 1);
86
                    else if (mp[i + 1][j] == 1) add(id(i, j), id(i + 1, j), 0), add(id(i + 1, j), id(i, j), 1);
87
                    else add(id(i, j), id(i + 1, j), 1), add(id(i + 1, j), id(i, j), 0);
88
                }
89
                if (j < m) {
90
                    if (mp[i][j + 1] == 0) add(id(i, j), id(i, j + 1), 1), add(id(i, j + 1), id(i, j), 1);
91
                    else if (mp[i][j + 1] == 1) add(id(i, j), id(i, j + 1), 0), add(id(i, j + 1), id(i, j), 1);
92
                    else add(id(i, j), id(i, j + 1), 1), add(id(i, j + 1), id(i, j), 1);
93
                }
94
            }
95
        }
96
    }
97
    S = 0, T = t;
98
    printf("%d\n", dinic());
99
    return 0;
100
}

Star's Blog