发表更新算法11 分钟读完 (大约1609个字)

2024年传智杯A组初赛

游游的重组偶数

题意

重排正整数 $n$ 的数位，使得它变成偶数（不能有前导零）。

思考

枚举找到偶数位，特判 $s_0$ 是偶数但 $s_{1}$ 是 ‘0’ 的情况，substr 直接输出即可。

小欧的平面连线

题意

平面直角坐标系上（除坐标轴上）有 $n$ 个整数点（$n$ 是偶数），将这些点任意两两配对形成线段，线段穿过的坐标轴个数即为这一点对的贡献。求最大的权值和。

思考

贪心。直接考虑按象限划分，先将对角象限的点们进行配对。
此时未配对的点一定只位于一个象限或两个相邻象限。如果是前者则没有额外贡献了，否则再加上能产生的大小为 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
/********************************************************
> File Name: e.cpp
> Author: zylll
> Blog: https://ylzhang.top
> Created Time: Mon Oct 27 22:52:47 2025
 *******************************************************/

#include <bits/stdc++.h>

int check(int x, int y) {
    if (x > 0 && y > 0) return 1;
    else if (x < 0 && y > 0) return 2;
    else if (x < 0 && y < 0) return 3;
    else return 4;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);
    // freopen("in", "r", stdin);
    
    int n, x, y;
    std::vector<int> part(5, 0);

    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> x >> y;
        part[check(x, y)]++;
    }

    int ans = 0, cnt1 = std::min(part[1], part[3]), cnt2 = std::min(part[2], part[4]);
    ans += (cnt1 + cnt2) * 2;
    part[1] -= cnt1; part[3] -= cnt1;
    part[2] -= cnt2; part[4] -= cnt2;

    int cnt = 0;
    std::vector<int> last;
    for (int i = 1; i <= 4; i++) {
        if (part[i] != 0) last.push_back(i);
    }
    if (last.size() == 2) {
        ans += std::min(part[last[0]], part[last[1]]);
    }

    std::cout << ans << "\n";
    return 0;
}

小红的四子棋

题意

给一个“四子棋”的结局地图，判断输赢还是平局。

思考

四个方向直接枚举即可。

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
121
122
123
124
125
126
/********************************************************
> File Name: f.cpp
> Author: zylll
> Blog: https://ylzhang.top
> Created Time: Mon Oct 27 23:10:47 2025
 *******************************************************/

#include <bits/stdc++.h>

const int MAXN = 105;
const int ASCII_SIZE = 200;
int n, m;
std::vector<std::string> a, b;

int vnum[ASCII_SIZE][MAXN], hnum[ASCII_SIZE][MAXN];

bool check_v(char c) {
    for (int i = 1; i <= n; i++) {
        if (vnum[c][i] < 4) continue;
        for (int j = 1; j + 3 <= m; j++) {
            if (a[i][j] == c && a[i][j + 1] == c && a[i][j + 2] == c && a[i][j + 3] == c) {
                return 1;
            }
        }
    }
    return 0;
}

bool check_h(char c) {
    for (int j = 1; j <= m; j++) {
        if (hnum[c][j] < 4) continue;
        
        for (int i = 0; i + 3 < n; i++) { 
            if (b[j][i] == c && b[j][i + 1] == c && b[j][i + 2] == c && b[j][i + 3] == c) {
                return 1;
            }
        }
    }
    return 0;
}

bool check_vh(char c) {
    int delx = 1, dely = 1;
    for (int j = 1; j <= m; j++) {
        int sx = 1, sy = j, cnt = 0;

        while (sx <= n && sy <= m) {
            if (a[sx][sy] == c) cnt++;
            else cnt = 0;
            sx += delx;
            sy += dely;

            if (cnt == 4) return 1;
        }
    }

    for (int i = 2; i <= n; i++) {
        int sx = i, sy = 1, cnt = 0;
        while (sx <= n && sy <= m) {
            if (a[sx][sy] == c) cnt++;
            else cnt = 0;
            sx += delx;
            sy += dely;

            if (cnt == 4) return 1;
        }
    }

    dely = -1;
    for (int j = 1; j <= m; j++) {
        int sx = 1, sy = j, cnt = 0;
        while (sx <= n && sy > 0) {
            if (a[sx][sy] == c) cnt++;
            else cnt = 0;
            sx += delx;
            sy += dely;

            if (cnt == 4) return 1;
        }
    }

    for (int i = 2; i <= n; i++) {
        int sx = i, sy = m, cnt = 0;
        while (sx <= n && sy > 0) {
            if (a[sx][sy] == c) cnt++;
            else cnt = 0;
            sx += delx;
            sy += dely;

            if (cnt == 4) return 1;
        }
    }

    return 0;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);
    // freopen("in", "r", stdin);

    std::cin >> n >> m;
    
    a.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i].resize(m + 1);
        for (int j = 1; j <= m; j++) {
            std::cin >> a[i][j];
            vnum[a[i][j]][i]++;
            hnum[a[i][j]][j]++;
        }
    }

    b.resize(m + 1);
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            b[j] += a[i][j];
        }
    }

    if (check_v('r') || check_h('r') || check_vh('r')) std::cout << "kou" << "\n";
    else if (check_v('p') || check_h('p') || check_vh('p')) std::cout << "yukari" << "\n";
    else std::cout << "to be continued" << "\n";

    return 0;
}

小红的数组操作

题意

数组 $a$ 有 $n$ 个数，对 $a$ 每次可以进行如下操作：

  • 选择一个数，使其减去 $x$。

求出 $k$ 次操作之后，$a$ 里元素的最大值最小可能是多少。

数据范围：$1 \leq n \leq 10 ^ 5, 1 \leq a_i, k, x \leq 10 ^ 9$。

思考

第一次看到的时候纯糖了；第二次看到以为是数学题（找循环结去了）；最后一看这不就一个简单二分吗？

注意一下 $l, 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/********************************************************
> File Name: g_1.cpp
> Author: zylll
> Blog: https://ylzhang.top
> Created Time: Tue Oct 28 13:17:30 2025
 *******************************************************/

#include <bits/stdc++.h>

int n, k, x;

int check(std::vector<int> &a, long long now) {
    long long cnt = 0;

    for (int i = 1; i <= n; i++) {
        if (a[i] <= now) continue;
        cnt += (a[i] - now + x - 1) / x;
        if (cnt > k) return 0;
    }

    return cnt <= k;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);
    // freopen("in", "r", stdin);

    std::cin >> n >> k >> x;

    std::vector<int> a(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    long long l = -1e18, r = 1e9, ans;

    while (l <= r) {
        long long mid = l + (r - l) / 2;

        if (check(a, mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    std::cout << ans << "\n";
    return 0;
}

游游的不相邻取数

题意

从数组 $a$ 中取数，使得最终取出来的所有数的乘积末尾的 0 尽可能多。取的数不允许相邻。

数据范围：$ 1 \leq n \leq 1000, 1 \leq a_i \leq 10 ^ 9$。

思考

本质是每个元素有一定个数的 $2$ 因子和 $5$ 因子，最终答案为 $\max(\min(\sum C_2, \sum C_5))$。一眼 dp 之后，思考如何转移。

首先意识到无法通过直接转移求最优解，所以思路转变为找到全集再遍历找最优。

不难发现：若出现 $(C_2=10, C_5=5)$，$(C_2=8, C_5=5)$时，后者是无用的（不需要被统计的），所以思路从找全集变为：对于每一个可能的 $\sum C_5 = j$，我们能得到的最大的 $\sum C_2$ 是多少。

思考到这就会定义状态以及转移了:

目标： $\max(\min(\sum C_2, \sum C_5))$。
状态定义： $f[i][j]$ = 考虑前 $i$ 个数，得到 $j$ 个 5 因子时，能获得的最大 2 因子数。
状态转移： 考虑第 $i$ 个数选或不选：$f[i][j] = \max(f[i-1][j], \quad f[i-2][j - c5_i] + c2_i)$。
初始化： $f$ 数组为 $-\text{INF}$，$f[0][0] = 0$。
最终答案： 遍历所有 $j$，$\text{ans} = \max(\text{ans}, \min(f[n][j], j))$。

还要注意 $i = 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
56
57
58
59
60
61
62
63
64
65
66
67
/********************************************************
> File Name: h.cpp
> Author: zylll
> Blog: https://ylzhang.top
> Created Time: Tue Oct 28 14:48:35 2025
 *******************************************************/

#include <bits/stdc++.h>

const int INF = 1 << 30;

struct node {
    int x, y;
};

int check_2(int x) {
    int cnt = 0;
    while (x % 2 == 0) {
        cnt++;
        x = x / 2;
    }
    return cnt;
}

int check_5(int x) {
    int cnt = 0;
    while (x % 5 == 0) {
        cnt++;
        x = x / 5;
    }
    return cnt;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);
    // freopen("in", "r", stdin);

    int n, x;
    std::cin >> n;

    std::vector<node> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> x;
        a[i] = (node){check_2(x), check_5(x)};
    }

    std::vector<std::vector<int>> f(n + 1, std::vector<int>(12001, -INF));
    f[0][0] = 0;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 12000; j++) {
            f[i][j] = f[i - 1][j];
            if (j - a[i].y >= 0) {
                f[i][j] = std::max(f[i][j], f[std::max(i - 2, 0)][j - a[i].y] + a[i].x);
            }
        }
    }
    
    int ans = 0;
    for (int j = 0; j <= 12000; j++) {
        ans = std::max(ans, std::min(f[n][j], j));
    }

    std::cout << ans << "\n";
    return 0;
}

2024年传智杯A组初赛

http://example.com/2025/10/28/2024传智杯初赛/

作者

Zylll

发布于

2025-10-28

更新于

2025-10-28

许可协议

#
×