2025春训第十五场

A. Lucky 7#

一道签到题。

1
#include <iostream>
2

3
using namespace std;
4

5
bool cont(int n) {
6
    for (char c : to_string(n)) {
7
        if (c == '7') return true;
8
    }
9
    return false;
10
}
11

12
int main() {
13
    int n;
14
    cin >> n;
15
    bool c1 = cont(n), c2 = n % 7 == 0;
16
    if (!c1 && !c2) cout << 0 << endl;
17
    else if (!c1 && c2) cout << 1 << endl;
18
    else if (c1 && !c2) cout << 2 << endl;
19
    else cout << 3 << endl;
20
    return 0;
21
}

B. We Want You Happy!#

两道签到题。

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

4
using namespace std;
5

6
struct Customer
7
{
8
    int id, s, d, t;
9
} a[1010];
10

11
int main() {
12
    int n;
13
    cin >> n;
14
    for (int i = 1; i <= n; ++i) {
15
        cin >> a[i].id >> a[i].s >> a[i].d >> a[i].t;
16
    }
17
    sort(a + 1, a + n + 1, [](Customer a, Customer b) {
18
        return a.s < b.s;
19
    });
20
    int curt = 0;
21
    for (int i = 1; i <= n; ++i) {
22
        if (curt > a[i].s + a[i].t) continue;
23
        if (curt < a[i].s) curt = a[i].s;
24
        curt += a[i].d;
25
        cout << a[i].id << endl;
26
    }
27
    return 0;
28
}

C. Snailography#

生成一个下标矩阵然后对着矩阵输出。

1
#include <iostream>
2

3
using namespace std;
4

5
int t[30][30];
6

7
int main() {
8
    int n;
9
    string s;
10
    cin >> n >> s;
11
    int x = 0, y = 1;
12
    int cur = n * n;
13
    while (cur > 0) {
14
        while (x + 1 <= n && t[x + 1][y] == 0) t[++x][y] = cur--;
15
        while (y + 1 <= n && t[x][y + 1] == 0) t[x][++y] = cur--;
16
        while (x - 1 > 0 && t[x - 1][y] == 0) t[--x][y] = cur--;
17
        while (y - 1 > 0 && t[x][y - 1] == 0) t[x][--y] = cur--;
18
    }
19
    for (int i = 1; i <= n; ++i) {
20
        for (int j = 1; j <= n; ++j) {
21
            if (t[i][j] <= s.length()) cout << s[t[i][j] - 1];
22
        }
23
    }
24
    cout << endl;
25
    return 0;
26
}

D. Good Goalie#

肯定不行的情况，原点到直线的距离大于 r；
肯定是 0 的情况 $|x|$ ≤ r；
其余情况，先把 x, y 取一下绝对值，对称变换不会影响答案

答案是蓝色的角 $\arctan \frac{x}{y} - \arccos \frac{d}{r}$

1
#include <iostream>
2
#include <cmath>
3
#include <iomanip>
4

5
using namespace std;
6

7
int main() {
8
    double y, x, r;
9
    while (cin >> y >> x >> r) {
10
        double d = fabs(x * y) / sqrt(x * x + y * y);
11
        if (d <= r) {
12
            if (fabs(r) >= fabs(x)) cout << 0 << endl;
13
            else {
14
                x = fabs(x), y = fabs(y);
15
                double theta = atan(x / y) - acos(d / r);
16
                cout << fixed << setprecision(6) << theta * 180 / acos(-1) << endl;
17
            }
18
        }
19
        else cout << -1 << endl;
20
    }
21
    return 0;
22
}

E. Most Valuable Pez#

分组背包。

1
#include <iostream>
2

3
using namespace std;
4

5
int f[12010], s[13];
6

7
int main() {
8
    int n, m;
9
    scanf("%d%d", &n, &m);
10
    for (int i = 1; i <= n; ++i) {
11
        for (int j = 1; j <= 12; ++j) {
12
            scanf("%d", &s[j]);
13
            s[j] += s[j - 1];
14
        }
15
        for (int j = m; j; --j) {
16
            for (int k = 1; k <= 12 && k <= j; ++k) {
17
                f[j] = max(f[j], f[j - k] + s[k]);
18
            }
19
        }
20
    }
21
    printf("%d\n", f[m]);
22
    return 0;
23
}

G. Not So Close#

经典的状压dp，用一个二进制数 mask 表示一行的状态。只考虑当前行合法状态需要满足 mask » 1 & mask == 0，因为不能相邻；相邻两行的状态 i，j 需要满足 i « 1 & j == 0 and i & j == 0 and i » 1 & j == 0。

1
#include <iostream>
2

3
using namespace std;
4

5
const int MOD = 1000000007;
6

7
long long f[1010][1 << 10];
8

9
int main() {
10
    int r, n;
11
    cin >> r >> n;
12
    f[0][0] = 1;
13
    for (int i = 1; i <= n; ++i) {
14
        for (int j = 0; j < (1 << r); ++j) {
15
            if (j >> 1 & j) continue;
16
            for (int k = 0; k < (1 << r); ++k) {
17
                if ((k >> 1 & k) || (k & j) || (k >> 1 & j) || (k << 1 & j)) continue;
18
                f[i][j] = (f[i][j] + f[i - 1][k]) % MOD;
19
            }
20
        }
21
    }
22
    long long res = 0;
23
    for (int mask = 0; mask < (1 << r); ++mask) {
24
        res = (res + f[n][mask]) % MOD;
25
    }
26
    cout << res << endl;
27
    return 0;
28
}

H. The Duel of Smokin’ Joe#

统计逆序对数量，如果是奇数就是 Smokin Joe!，否则就是 Oh No!.

原理是一次交换一定会改变逆序对数量的奇偶性，如果原来是奇数，那一定需要奇数次，先手必胜；反之后手必胜。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 1000010;
6
int tr[N], a[N], n;
7

8
void add(int u) {
9
    for (; u <= n; u += u & -u) {
10
        tr[u]++;
11
    }
12
}
13

14
int query(int u) {
15
    int res = 0;
16
    for (; u; u -= u & -u) {
17
        res += tr[u];
18
    }
19
    return res;
20
}
21

22
int main() {
23
    scanf("%d", &n);
24
    for (int i = 1; i <= n; ++i) {
25
        scanf("%d", &a[i]);
26
    }
27
    long long cnt = 0;
28
    for (int i = n; i; --i) {
29
        cnt += query(a[i]);
30
        add(a[i]);
31
    }
32
    if (cnt & 1) printf("Smokin Joe!\n");
33
    else printf("Oh No!\n");
34
    return 0;
35
}

~~归并排序是什么，感觉不如树状数组（）~~

J. Grow Measure Cut Repeat#

因为每次 cut 都是单调不增的，所以不会发生第一次 cut 过的树第二次不 cut 的情况，这就好办了。维护两个线段树，一个维护忽略所有裁剪的前提下的高度，一个维护只考虑最后一次裁剪的情况下的高度。

说起来简单，但是实际上非常不好写，毕竟用线段树维护等差数列本来就比较复杂。具体的，第一颗树需要两个懒标记一个是首项，一个是公差；第二棵树需要三个懒标记，一个首项，一个公差，还有一个覆盖标记（因为裁剪之后要把所有的数覆盖成新的H），同时需要注意边界，我就因为边界快调死了😭。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 500000;
6

7
int seq[N];
8

9
struct SemgentTree {
10
    long long a[N], tag[N];
11
    bool cover[N];
12

13
    void pushdown(int u, int l, int r) {
14
        if (cover[u]) {
15
            int mid = (l + r) >> 1;
16
            a[u << 1] = a[u], a[u << 1 | 1] = a[u] + tag[u] * (mid - l + 1);
17
            tag[u << 1] = tag[u], tag[u << 1 | 1] = tag[u];
18
            tag[u] = 0;
19
            a[u] = 0;
20
            cover[u << 1] = cover[u << 1 | 1] = true;
21
            cover[u] = 0;
22
        }
23
        if (a[u] || tag[u]) {
24
            int mid = (l + r) >> 1;
25
            a[u << 1] += a[u], a[u << 1 | 1] += a[u] + tag[u] * (mid - l + 1);
26
            tag[u << 1] += tag[u], tag[u << 1 | 1] += tag[u];
27
            tag[u] = 0;
28
            a[u] = 0;
29
        }
30
    }
31

32
    void reset(int u, int l, int r, long long val) {
33
        cover[u] = true;
34
        a[u] = val, tag[u] = 0;
35
    }
36

37
    void modify(int u, int l, int r, int ql, int qr, int a1, int d) {
38
        if (ql > qr) return; // !!!!!
39
        if (ql <= l && r <= qr) {
40
            a[u] += a1 + (l - ql) * d; // 首项
41
            tag[u] += d; // 公差
42
        }
43
        else {
44
            pushdown(u, l, r);
45
            int mid = (l + r) >> 1;
46
            if (ql <= mid) modify(u << 1, l, mid, ql, qr, a1, d);
47
            if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, a1, d);
48
        }
49
    }
50

51
    long long query(int u, int l, int r, int p) {
52
        if (l == r) return a[u];
53
        else {
54
            pushdown(u, l, r);
55
            int mid = (l + r) >> 1;
56
            if (p <= mid) return query(u << 1, l, mid, p);
57
            else return query(u << 1 | 1, mid + 1, r, p);
58
        }
59
    }
60
} smt, limt;
61

62
void print(int t) {
63
    for (int i = 1; i <= t; ++i) {
64
        printf("%lld ", min(limt.query(1, 1, 100000, i), smt.query(1, 1, 100000, i)));
65
    }
66
    printf("\n");
67
}
68

69
int main() {
70
    int q, n = 100000;
71
    scanf("%d", &q);
72
    while (q--) {
73
        char s[2];
74
        scanf("%s", s);
75
        if (s[0] == 'A') {
76
            int l, k;
77
            scanf("%d%d", &l, &k);
78
            smt.modify(1, 1, n, max(1, l - k + 1), l, max(1, k - l + 1), 1);
79
            smt.modify(1, 1, n, l + 1, min(n, l + k - 1), k - 1, -1);
80
            limt.modify(1, 1, n, max(1, l - k + 1), l, max(1, k - l + 1), 1);
81
            limt.modify(1, 1, n, l + 1, min(n, l + k - 1), k - 1, -1);
82
        }
83
        else if (s[0] == 'B') {
84
            int p;
85
            scanf("%d", &p);
86
            printf("%lld\n", min(smt.query(1, 1, n, p), limt.query(1, 1, n, p)));
87
        }
88
        else {
89
            int H;
90
            scanf("%d", &H);
91
            limt.reset(1, 1, n, H);
92
        }
93
    }
94
    return 0;
95
}

K. Bad Bunny#

点双联通分量缩点，然后树上倍增求路径上割点的个数，如果端点不是割点，就额外加上端点。

说着很简单，调的时候也是很折磨，因为我是现学的点双联通分量缩点，之前只学过强联通和边双联通。点双的缩点更复杂，把双联通分量缩点，同时还需要把割点复制一份单独拎出来连接，第一次写的时候容易挂。

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

5
using namespace std;
6

7
const int N = 200010;
8

9
int head[N], head2[N], ver[N * 4], ne[N * 4], tot = 1;
10
int dfn[N], low[N], id[N], t, bcc_cnt, rt;
11
vector<int> bcc[N];
12
int cut[N], cut_id[N];
13
int f[N][20], g[N][20], dep[N];
14
stack<int> st;
15

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

22
void tarjan(int x, int from) {
23
    dfn[x] = low[x] = ++t;
24
    st.push(x);
25
    int cnt = 0;
26
    for (int i = head[x]; i; i = ne[i]) {
27
        if (i == (from ^ 1)) continue;
28
        int y = ver[i];
29
        if (!dfn[y]) {
30
            cnt++;
31
            tarjan(y, i);
32
            low[x] = min(low[x], low[y]);
33
            if (dfn[x] <= low[y]) {
34
                bcc_cnt++;
35
                int tp;
36
                if (x != rt || cnt >= 2) cut[x] = true;
37
                do {
38
                    tp = st.top();
39
                    st.pop();
40
                    id[tp] = bcc_cnt;
41
                    bcc[bcc_cnt].push_back(tp);
42
                } while (tp != y);
43
                bcc[bcc_cnt].push_back(x);
44
                id[x] = bcc_cnt;
45
            }
46
        }
47
        else {
48
            low[x] = min(low[x], dfn[y]);
49
        }
50
    }
51
}
52

53
void dfs(int x) {
54
    g[x][0] = cut_id[x];
55
    for (int i = 1; i < 20; ++i) {
56
        f[x][i] = f[f[x][i - 1]][i - 1];
57
        g[x][i] = g[x][i - 1] + g[f[x][i - 1]][i - 1];
58
    }
59
    for (int i = head2[x]; i; i = ne[i]) {
60
        int y = ver[i];
61
        if (y == f[x][0]) continue;
62
        f[y][0] = x;
63
        dep[y] = dep[x] + 1;
64
        dfs(y);
65
    }
66
}
67

68
int main() {
69
#ifndef ONLINE_JUDGE
70
    freopen("input", "r", stdin);
71
#endif // !ONLINE_JUDGE
72
    int n, m;
73
    scanf("%d%d", &n, &m);
74
    for (int i = 1; i <= m; ++i) {
75
        int x, y;
76
        scanf("%d%d", &x, &y);
77
        add(head, x, y);
78
        add(head, y, x);
79
    }
80
    rt = 1;
81
    tarjan(1, 0);
82
    for (int i = 1; i <= n; ++i) {
83
        if (cut[i]) {
84
            id[i] = ++bcc_cnt;
85
            cut_id[bcc_cnt] = true;
86
        }
87
    }
88
    for (int i = 1; i <= bcc_cnt; ++i) {
89
        for (int y : bcc[i]) {
90
            if (cut[y]) {
91
                add(head2, id[y], i);
92
                add(head2, i, id[y]);
93
            }
94
        }
95
    }
96

97
    dep[1] = 1;
98
    dfs(1);
99
    int q;
100
    scanf("%d", &q);
101
    while (q--) {
102
        int x, y;
103
        scanf("%d%d", &x, &y);
104
        int res = !cut[x] + !cut[y];
105
        x = id[x], y = id[y];
106
        if (dep[x] < dep[y]) swap(x, y);
107
        for (int i = 19; i >= 0; --i) {
108
            if (dep[f[x][i]] >= dep[y]) {
109
                res += g[x][i];
110
                x = f[x][i];
111
            }
112
        }
113
        if (x != y) {
114
            for (int i = 19; i >= 0; --i) {
115
                if (f[x][i] != f[y][i]) {
116
                    res += g[x][i] + g[y][i];
117
                    x = f[x][i], y = f[y][i];
118
                }
119
            }
120
            res += g[x][0] + g[y][0];
121
            x = f[x][0];
122
        }
123
        if (cut_id[x]) res++;
124
        printf("%d\n", res);
125
    }
126
    return 0;
127
}

Star's Blog