2025春训第二十七场

A. 序列#

逻辑非常简单，先输出 k 个 0 之后 01 交替输出直到把 0 用完，最后输出剩下的 1.

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    int n, m, k;
7
    scanf("%d%d%d", &n, &m, &k);
8
    for (int i = 1; i <= k; ++i) {
9
        printf("0");
10
        m--;
11
    }
12
    while (n || m) {
13
        if (n) printf("1"), n--;
14
        if (m) printf("0"), m--;
15
    }
16
    printf("\n");
17
    return 0;
18
}

B. 异或之力#

也比较容易，不难想到最优方案是取 11111…0，因为这是个偶数，对半分异或 = 0；任意从中间断开，然后异或还是原数，答案是 $2^{n} - 2$ .

需要特判 2，因为 2 只能分出正整数 1，答案是 0.

1
#include <iostream>
2

3
using namespace std;
4

5
const int MOD = 1e9 + 7;
6
int power(int n, int p) {
7
    long long res = 1, base = n;
8
    while (p) {
9
        if (p & 1) res = res * base % MOD;
10
        base = base * base % MOD;
11
        p >>= 1;
12
    }
13
    return res;
14
}
15

16
int main() {
17
    int n;
18
    cin >> n;
19
    if (n <= 2) cout << 0 << endl;
20
    else cout << (power(2, n) - 2 + MOD) % MOD << endl;
21
    return 0;
22
}

C. 队伍集结#

看着吓人，实则不是，直接暴力 $\Theta(n^4)$ 预处理所有区间的最小不满度，然后开一个二维状态 $f_{i, j}$ 表示以 i 结尾的区间加了 j 个汇合点时不满都的最小值，枚举最后一段区间 dp 即可。

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

4
using namespace std;
5

6
const int N = 210;
7
long long d[N], f[N][N], s[N][N];
8

9
int main() {
10
    int n, k;
11
    cin >> n >> k;
12
    for (int i = 1; i <= n; ++i) {
13
        int a, b;
14
        cin >> a >> b;
15
        d[a + 1] += b;
16
    }
17
    memset(f, 0x3f, sizeof(f));
18
    memset(s, 0x3f, sizeof(s));
19
    for (int i = 1; i <= 201; ++i) {
20
        for (int j = i; j <= 201; ++j) {
21
            for (int k = i; k <= j; ++k) {
22
                long long res = 0;
23
                for (int l = i; l <= j; ++l) {
24
                    res += (long long)(l - k) * (l - k) * d[l];
25
                }
26
                s[i][j] = min(s[i][j], res);
27
            }
28
        }
29
    }
30
    f[0][0] = 0;
31
    for (int i = 1; i <= 201; ++i) {
32
        for (int j = 1; j <= k; ++j) { // 使用次数
33
            for (int l = 1; l <= i; ++l) {
34
                f[i][j] = min(f[i][j], f[l - 1][j - 1] + s[l][i]);
35
            }
36
        }
37
    }
38
    cout << f[201][k] << endl;
39
    return 0;
40
}

D. 花#

子树在 dfs 序下一定是一段连续区间，把节点按 dfs 序建一棵线段树维护单点修改和区间查询即可。

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

5
using namespace std;
6

7
const int N = 200010;
8

9
vector<int> ed[N];
10
int dfn[N], cnt[N], t;
11
int tr[N * 4];
12
int a[N];
13

14
void dfs(int x, int fa) {
15
    dfn[x] = ++t;
16
    cnt[x] = 1;
17
    for (int y : ed[x]) {
18
        if (y == fa) continue;
19
        dfs(y, x);
20
        cnt[x] += cnt[y];
21
    }
22
}
23

24
void pushup(int u) {
25
    tr[u] = max(tr[u << 1], tr[u << 1 | 1]);
26
}
27

28
void modify(int u, int l, int r, int p, int val) {
29
    if (l == r) tr[u] = val;
30
    else {
31
        int mid = l + r >> 1;
32
        if (p <= mid) modify(u << 1, l, mid, p, val);
33
        else modify(u << 1 | 1, mid + 1, r, p, val);
34
        pushup(u);
35
    }
36
}
37

38
int query(int u, int l, int r, int ql, int qr) {
39
    if (ql <= l && r <= qr) return tr[u];
40
    else {
41
        int mid = l + r >> 1;
42
        int res = 0;
43
        if (ql <= mid) res = query(u << 1, l, mid, ql, qr);
44
        if (qr > mid) res = max(res, query(u << 1 | 1, mid + 1, r, ql, qr));
45
        return res;
46
    }
47
}
48

49
int main() {
50
    int n, m;
51
    scanf("%d%d", &n, &m);
52
    for (int i = 1; i <= n; ++i) {
53
        scanf("%d", &a[i]);
54
    }
55
    for (int i = 1; i < n; ++i) {
56
        int a, b;
57
        scanf("%d%d", &a, &b);
58
        ed[a].push_back(b);
59
        ed[b].push_back(a);
60
    }
61
    dfs(1, 0);
62
    for (int i = 1; i <= n; ++i) {
63
        modify(1, 1, n, dfn[i], a[i]);
64
    }
65
    while (m--) {
66
        int op;
67
        scanf("%d", &op);
68
        if (op == 1) {
69
            int u, w;
70
            scanf("%d%d", &u, &w);
71
            modify(1, 1, n, dfn[u], w);
72
        }
73
        else {
74
            int u;
75
            scanf("%d", &u);
76
            printf("%d\n", query(1, 1, n, dfn[u], dfn[u] + cnt[u] - 1));
77
        }
78
    }
79
    return 0;
80
}

E. 分糖果#

水题

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    int a, b;
7
    cin >> a >> b;
8
    cout << (b + a - 1) / a << endl;
9
    return 0;
10
}

F. 新字典#

水题

1
#include <iostream>
2

3
using namespace std;
4

5
int p[26];
6

7
char check(string a, string b) {
8
    int l = min(a.length(), b.length());
9
    for (int i = 0; i < l; ++i) {
10
        if (a[i] != b[i]) return p[a[i] - 'a'] < p[b[i] - 'a'] ? 's' : 't';
11
    }
12
    return a.length() < b.length() ? 's' : 't';
13
}
14

15
int main() {
16
    ios::sync_with_stdio(0);
17
    cin.tie(0), cout.tie(0);
18
    int n, m;
19
    cin >> n >> m;
20
    string s, t;
21
    cin >> s >> t;
22
    int T;
23
    cin >> T;
24
    while (T--) {
25
        string dic;
26
        cin >> dic;
27
        for (int i = 0; i < 26; ++i) p[dic[i] - 'a'] = i;
28
        cout << check(s, t) << endl;
29
    }
30
    return 0;
31
}

G. 机器人#

二分答案，需要注意二分下界是 $\max_{i=1}^na_i$ ，初始任务也是任务😭

1
#include <iostream>
2
#include <vector>
3
#include <climits>
4
#define int long long
5

6
using namespace std;
7

8
const int N = 100010;
9
int n, m, t;
10
int a[N];
11

12
bool check(int mid) {
13
    long long cnt = 0;
14
    for (int i = 1; i <= m; ++i) {
15
        cnt += max(0ll, (mid - a[i]) / t);
16
    }
17
    return cnt >= n;
18
}
19

20
signed main() {
21
    cin >> n >> m >> t;
22
    int l = 0, r = 1000000000000;
23
    for (int i = 1; i <= m; ++i) {
24
        cin >> a[i];
25
        l = max(l, a[i]);
26
    }
27
    while (l < r) {
28
        int mid = l + r >> 1;
29
        if (check(mid)) r = mid;
30
        else l = mid + 1;
31
    }
32
    cout << l << endl;
33
    return 0;
34
}

H. 游戏#

基础的二维 dp， $f_{i, j}$ 表示第 i 天还剩 j 资源能获得的最大强度值，每天枚举所有的 j 和买不买更新状态。

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

4
using namespace std;
5

6
const int N = 5010;
7
int f[N][N];
8

9
int main() {
10
    int n;
11
    scanf("%d", &n);
12
    memset(f, -0x3f, sizeof(f));
13
    f[0][0] = 0;
14
    for (int i = 1; i <= n; ++i) {
15
        int a, b;
16
        scanf("%d%d", &a, &b);
17
        for (int j = 0; j < i; ++j) {
18
            // 不买
19
            f[i][j + 1] = max(f[i][j + 1], f[i - 1][j]);
20
            // 买
21
            if (j + 1 >= a) {
22
                f[i][j + 1 - a] = max(f[i][j + 1 - a], f[i - 1][j] + b);
23
            }
24
        }
25
    }
26
    int res = 0;
27
    for (int i = 0; i <= n; ++i) res = max(res, f[n][i]);
28
    printf("%d\n", res);
29
    return 0;
30
}

I. ABB#

水题

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

4
using namespace std;
5

6
set<string> a;
7

8
int main() {
9
    ios::sync_with_stdio(0);
10
    cin.tie(0), cout.tie(0);
11
    int n;
12
    cin >> n;
13
    string s;
14
    cin >> s;
15
    for (int i = 0; i < s.length() - 2; ++i) {
16
        if (s[i] != s[i + 1] && s[i + 1] == s[i + 2]) a.insert(s.substr(i, 3));
17
    }
18
    cout << a.size() << endl;
19
    return 0;
20
}

J. 负重爬楼梯#

水题（线性 dp）

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

4
using namespace std;
5

6
const int N = 100010;
7
int a[N];
8
long long f[N];
9

10
int main() {
11
    int n;
12
    scanf("%d", &n);
13
    for (int i = 1; i <= n; ++i) {
14
        scanf("%d", &a[i]);
15
    }
16
    memset(f, 0x3f, sizeof(f));
17
    f[1] = a[1];
18
    f[0] = 0;
19
    for (int i = 2; i <= n; ++i) {
20
        f[i] = min(f[i - 2] + a[i], f[i - 1] + a[i]);
21
    }
22
    printf("%lld\n", min(f[n], f[n - 1]));
23
    return 0;
24
}

K. 洒水器#

直接暴力维护等差数列不好维护，但是我们可以维护等差数列的差分数列，等差数列公差一定，所以这个差分数列可以再用它的差分数列维护，最后前缀和两次输出答案即可。

需要特判左边界，不需要特判右边界，因为已经出界了无所谓了。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 1000010;
6
long long s[N];
7
int p[N];
8

9
int main() {
10
    int n, m;
11
    scanf("%d%d", &n, &m);
12
    for (int i = 1; i <= n; ++i) {
13
        scanf("%d", &p[i]);
14
    }
15
    for (int i = 1; i <= n; ++i) {
16
        int w;
17
        scanf("%d", &w);
18
        int lp = max(p[i] - w + 1, 1), rp = min(p[i] + w - 1, m);
19
        s[lp] += w - abs(p[i] - lp);
20
        s[lp + 1] -= w - abs(p[i] - lp);
21
        s[lp + 1] += 1;
22
        s[p[i] + 1] -= 2;
23
        s[rp + 2]++;
24
    }
25
    for (int i = 1; i <= m; ++i) {
26
        s[i] += s[i - 1];
27
    }
28
    for (int i = 1; i <= m; ++i) {
29
        s[i] += s[i - 1];
30
        printf("%lld ", s[i]);
31
    }
32
    printf("\n");
33
    return 0;
34
}

Star's Blog