2026寒假集训个人训练赛第十五场

罚时吃饱了（bushi

A. 奶牛大会#

二分答案，间隔越长越容易成功，二分能成功和不能成功的边界。

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

4
using namespace std;
5

6
const int N = 100010;
7

8
int a[N];
9
int n, m, c;
10

11
bool check(int mid) {
12
    int t = -100000000, cur = 0, cnt = 0;
13
    for (int i = 1; i <= n; ++i) {
14
        if (a[i] - t > mid || cur == c) cnt++, t = a[i], cur = 0;
15
        cur++;
16
    }
17
    return cnt <= m;
18
}
19

20
int main() {
21
    ios::sync_with_stdio(0);
22
    cin.tie(0), cout.tie(0);
23
    cin >> n >> m >> c;
24
    for (int i = 1; i <= n; ++i) cin >> a[i];
25
    sort(a + 1, a + n + 1);
26
    int l = 0, r = 1000000000;
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
}

B. 面积 (area)#

往外面框一个圈，从外面的新加的点开始搜一遍，没被标记的就是内部点。

然后我因为无视了右边那条和下边那条挂到了好几次。

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

4
using namespace std;
5

6
const int N = 20;
7
int a[N][N];
8
int n = 10;
9

10
void dfs(int x, int y) {
11
    if (x < 0 || x > n + 1 || y < 0 || y > n + 1 || a[x][y] != 0) return;
12
    a[x][y] = 1;
13
    if (x <= n) dfs(x + 1, y);
14
    if (x > 0) dfs(x - 1, y);
15
    if (y <= n) dfs(x, y + 1);
16
    if (y > 0) dfs(x, y - 1);
17
}
18

19
int main() {
20
    ios::sync_with_stdio(0);
21
    cin.tie(0), cout.tie(0);
22
    for (int i = 1; i <= n; ++i) {
23
        for (int j = 1; j <= n; ++j) {
24
            cin >> a[i][j];
25
        }
26
    }
27
    for (int i = 0; i <= n + 1; ++i) dfs(0, i), dfs(n + 1, i), dfs(i, 0), dfs(i, n + 1);
28
    int res = 0;
29
    for (int i = 1; i <= n; ++i) {
30
        for (int j = 1; j <= n; ++j) {
31
            if (a[i][j] == 0) res++;
32
        }
33
    }
34
    cout << res << endl;
35
    return 0;
36
}

C. 营救 (save)#

bfs 第一次搜到用的步数就是答案。

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

5
using namespace std;
6

7
const int N = 1010;
8
char a[N][N];
9

10
int main() {
11
    ios::sync_with_stdio(0);
12
    cin.tie(0), cout.tie(0);
13
    int n;
14
    cin >> n;
15
    for (int i = 1; i <= n; ++i) {
16
        for (int j = 1; j <= n; ++j) {
17
            cin >> a[i][j];
18
        }
19
    }
20
    queue<tuple<int, int, int>> q;
21
    int sx, sy, tx, ty;
22
    cin >> sx >> sy >> tx >> ty;
23
    q.emplace(0, sx, sy);
24
    while (!q.empty()) {
25
        auto [d, x, y] = q.front();
26
        q.pop();
27
        if (tx == x && ty == y) {
28
            cout << d << endl;
29
            break;
30
        }
31
        if (a[x][y] == '1') continue;
32
        a[x][y] = '1';
33
        if (x < n) q.emplace(d + 1, x + 1, y);
34
        if (x > 1) q.emplace(d + 1, x - 1, y);
35
        if (y < n) q.emplace(d + 1, x, y + 1);
36
        if (y > 1) q.emplace(d + 1, x, y - 1);
37
    }
38
    return 0;
39
}

D. 最少转弯问题 (turn)#

相当于建了一个分层图在分层图上 bfs，边权只有 0 和 1，所以可以用双端队列做 bfs，还是第一次搜到的就是答案。

1
#include <iostream>
2
#include <deque>
3
#include <tuple>
4

5
using namespace std;
6

7
const int N = 110;
8
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
9
char a[N][N];
10

11
int main() {
12
    ios::sync_with_stdio(0);
13
    cin.tie(0), cout.tie(0);
14
    int n, m;
15
    cin >> n >> m;
16
    for (int i = 1; i <= n; ++i) {
17
        for (int j = 1; j <= m; ++j) {
18
            cin >> a[i][j];
19
        }
20
    }
21
    deque<tuple<int, int, int, int>> q;
22
    int sx, sy, tx, ty;
23
    cin >> sx >> sy >> tx >> ty;
24
    q.emplace_back(0, 0, sx, sy);
25
    q.emplace_back(1, 0, sx, sy);
26
    q.emplace_back(2, 0, sx, sy);
27
    q.emplace_back(3, 0, sx, sy);
28
    while (!q.empty()) {
29
        auto [dis, dir, x, y] = q.front();
30
        q.pop_front();
31
        if (tx == x && ty == y) {
32
            cout << dir << endl;
33
            break;
34
        }
35
        if (x < 1 || x > n || y < 1 || y > m || a[x][y] == '1') continue;
36
        a[x][y] = '1';
37
        for (int i = 0; i < 4; ++i) {
38
            if (i == dir) q.emplace_front(dir, dis, x + dx[i], y + dy[i]);
39
            else q.emplace_back(dir, dis + 1, x + dx[i], y + dy[i]);
40
        }
41
    }
42
    return 0;
43
}

E. 社交网络#

Floyd 板子，统计最短路和最短路条数然后按要求直接算就行。

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

4
using namespace std;
5

6
typedef long long LL;
7
typedef pair<LL, LL> PLL;
8
const int N = 110;
9

10
PLL merge(PLL a, PLL b) {
11
    if (a.first == b.first) return {a.first, a.second + b.second};
12
    else return a.first < b.first ? a : b;
13
}
14

15
PLL f[N][N];
16

17
int main() {
18
    ios::sync_with_stdio(0);
19
    cin.tie(0), cout.tie(0);
20
    int n, m;
21
    cin >> n >> m;
22
    for (int i = 1; i <= n; ++i) {
23
        for (int j = 1; j <= n; ++j) {
24
            f[i][j] = {1000LL * 500000000, 0};
25
        }
26
    }
27
    for (int i = 1; i <= m; ++i) {
28
        int x, y, z;
29
        cin >> x >> y >> z;
30
        f[x][y] = f[y][x] = merge(f[x][y], {z, 1});
31
    }
32
    for (int k = 1; k <= n; ++k) {
33
        for (int i = 1; i <= n; ++i) {
34
            for (int j = 1; j <= n; ++j) {
35
                if (i != j && j != k) f[i][j] = merge(f[i][j], {f[i][k].first + f[k][j].first, f[i][k].second * f[k][j].second});
36
            }
37
        }
38
    }
39
    for (int i = 1; i <= n; ++i) {
40
        double res = 0;
41
        for (int j = 1; j <= n; ++j) {
42
            for (int k = 1; k <= n; ++k) {
43
                if (i != j && j != k && i != k && f[j][k].first == f[j][i].first + f[i][k].first) res += (double)f[j][i].second * f[i][k].second / f[j][k].second;
44
            }
45
        }
46
        cout << fixed << setprecision(3) << res << endl;
47
    }
48
    return 0;
49
}

F. Play on Words#

我一直理解错了题面，他问的是前面输入的 m 个串中某个子序列和询问的串相等的串个数，直接双指针扫描就可以。

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

4
using namespace std;
5

6
const int N = 5010;
7

8
string s[N];
9

10
int main() {
11
    ios::sync_with_stdio(0);
12
    cin.tie(0), cout.tie(0);
13
    int m, n;
14
    cin >> m;
15
    for (int i = 1; i <= m; ++i) cin >> s[i];
16
    cin >> n;
17
    for (int i = 1; i <= n; ++i) {
18
        string t;
19
        cin >> t;
20
        int cnt = 0;
21
        for (int j = 1; j <= m; ++j) {
22
            int l = 0;
23
            for (int k = 0; k < s[j].length(); ++k) {
24
                if (s[j][k] == t[l]) l++;
25
                if (l == t.length()) break;
26
            }
27
            cnt += l == t.length();
28
        }
29
        cout << cnt << endl;
30
    }
31
    return 0;
32
}

G. 【树型DP】叶子的染色#

不妨先假设都染到叶子上，然后让叶子上的颜色不断往上走，在路径上合并。记. $f_{x,i}$ 为结点 x 涂颜色 i 且子树合法需要的最少次数。枚举每个非叶子结点的颜色

f_{x, j} = 1 + \sum_{y \text{is a son of} x}\max\{f_{y, i} - 1, f_{y, i \oplus 1}\}

如果儿子和父亲颜色一样，那么都能并到父亲，只用计算父亲那一个代价就行了，如果不一样那么只能留在儿子。

然后这道题的数据只有 $10^4$ 我幻想着直接对每个非叶子结点都暴力一遍能过，然后就正好被卡了，无奈之下只能再写个换根 DP 了。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 10010;
6
int head[N], ver[N * 2], ne[N * 2], tot;
7
int f[N][2], n, m, res;
8

9
void add(int x, int y) {
10
    ver[++tot] = y;
11
    ne[tot] = head[x];
12
    head[x] = tot;
13
}
14

15
void dp(int x, int fa) {
16
    if (x > m) f[x][1] = f[x][0] = 1;
17
    for (int i = head[x]; i; i = ne[i]) {
18
        int y = ver[i];
19
        if (y == fa) continue;
20
        dp(y, x);
21
        f[x][1] += min(f[y][1] - 1, f[y][0]);
22
        f[x][0] += min(f[y][0] - 1, f[y][1]);
23
    }
24
}
25

26
void dfs(int x, int fa) {
27
    res = min(res, min(f[x][0], f[x][1]));
28
    for (int i = head[x]; i; i = ne[i]) {
29
        int y = ver[i];
30
        if (y == fa || y <= m) continue;
31
        int bk[4] = {f[x][0], f[x][1], f[y][0], f[y][1]};
32
        f[x][0] -= min(f[y][0] - 1, f[y][1]);
33
        f[x][1] -= min(f[y][1] - 1, f[y][0]);
34
        f[y][1] += min(f[x][1] - 1, f[x][0]);
35
        f[y][0] += min(f[x][0] - 1, f[x][1]);
36
        f[x][0] = bk[0], f[x][1] = bk[1], f[y][0] = bk[2], f[y][1] = bk[3];
37
    }
38
}
39

40
int main() {
41
    ios::sync_with_stdio(0);
42
    cin.tie(0), cout.tie(0);
43
    cin >> n >> m;
44
    for (int i = 1; i <= m; ++i) {
45
        int c;
46
        cin >> c;
47
        f[i][c] = 1;
48
        f[i][c ^ 1] = m;
49
    }
50
    for (int i = 1; i < n; ++i) {
51
        int x, y;
52
        cin >> x >> y;
53
        add(x, y), add(y, x);
54
    }
55
    dp(m + 1, 0);
56
    res = m;
57
    dfs(m + 1, 0);
58
    cout << res << endl;
59
    return 0;
60
}

Star's Blog