2025春训第二十八场

A. 评估#

关键在于 $|a_i| \le 1000$ ，所以可以开一个长度为 2000 的数组统计一下每个值的个数，然后 $\Theta(n^2)$ 处理这个 2000 的数组。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 2010;
6
int a[N];
7

8
int main() {
9
    int n;
10
    scanf("%d", &n);
11
    for (int i = 1; i <= n; ++i) {
12
        int t;
13
        scanf("%d", &t);
14
        a[t + 1000]++;
15
    }
16
    long long res = 0;
17
    for (int i = 0; i <= 2000; ++i) {
18
        for (int j = i + 1; j <= 2000; ++j) {
19
            res += (long long)a[i] * a[j] * (i - j) * (i - j);
20
        }
21
    }
22
    printf("%lld\n", res);
23
    return 0;
24
}

B. 拆分数字#

记 n 在三进制表示下的各位数之和为 t，想要满足要求的充要条件是 $t \le k \le n\ \land\ t \equiv k\ (mod\ 2)$ .

首先考虑边界情况，如果全用 1 那么需要 n 个；如果选择最优方案，全部按照三进制的表示那么需要 t 个；
其次考虑内部，按照要求，无论怎么拆，一个 3 的幂只能拆成奇数个更小的幂，所以最优方案拆出来的个数的奇偶性和任何方案的奇偶性相同。

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    int T;
7
    scanf("%d", &T);
8
    while (T--) {
9
        long long n, k;
10
        scanf("%lld%lld", &n, &k);
11
        long long bit = 0;
12
        bool f = false;
13
        while (n) {
14
            f ^= (n % 3) & 1;
15
            bit += n % 3;
16
            n /= 3;
17
        }
18
        if (bit <= k && !(f ^ (k & 1))) printf("Yes\n");
19
        else printf("No\n");
20
    }
21
    return 0;
22
}

C. 露营#

比较水，直接枚举一个中间点向三个点分别连线就行。

1
#include <iostream>
2

3
using namespace std;
4

5
int dis(pair<int, int> a, pair<int, int> b) {
6
    return abs(a.first - b.first) + abs(a.second - b.second);
7
}
8

9
int main() {
10
    pair<int, int> a[3];
11
    for (int i = 0; i < 3; ++i) scanf("%d%d", &a[i].first, &a[i].second);
12
    int res = 0x3f3f3f3f;
13
    for (int i = 0; i <= 1000; ++i) {
14
        for (int j = 0; j <= 1000; ++j) {
15
            pair<int, int> cur = {i, j};
16
            res = min(res, dis(cur, a[0]) + dis(cur, a[1]) + dis(cur, a[2]) + 1);
17
        }
18
    }
19
    printf("%d\n", res);
20
    return 0;
21
}

D. 寻宝#

思路比较简单，实际操作有点复杂

能放法术一定是最开始连续放，让前面都是 a，所以先做一个二维 dp 求出来左上角到每个点路径上最多 a 的个数。
遍历一遍 dp 的数组，找到能达到最长 a 的位置（可以是多个），从每个位置跑记搜（反拓扑序dp），dp 出后续的最优路线。

这道题需要注意爆空间的问题，不能每个点都存字符串，应该存一个方向或者下一个点的位置，比较字典序的时候按照记录的信息递归比较。

另外还要特判

如果一开始就没有 a，也不能施法的情况。
k 太大的情况。

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

4
using namespace std;
5

6
const int N = 1010;
7

8
char a[N][N];
9
int f[N][N];
10
int n, k;
11
bool vis[N][N], ne[N][N]; // 0 下 1 右
12

13
bool le(int x1, int y1, int x2, int y2) {
14
    while (x1 != n || y1 != n) {
15
        if (a[x1][y1] != a[x2][y2]) return a[x1][y1] < a[x2][y2];
16
        else {
17
            bool flag = ne[x1][y1];
18
            x1 = flag ? x1 : x1 + 1, y1 = flag ? y1 + 1 : y1;
19
            flag = ne[x2][y2];
20
            x2 = flag ? x2 : x2 + 1, y2 = flag ? y2 + 1 : y2;
21
        }
22
    }
23
    return true; // 相等，随便了
24
}
25

26
void dp(int x, int y) {
27
    if (vis[x][y]) return;
28
    vis[x][y] = true;
29
    if (x == n && y != n) {
30
        dp(x, y + 1);
31
        ne[x][y] = 1;
32
    }
33
    else if (x != n && y == n) {
34
        dp(x + 1, y);
35
        ne[x][y] = 0;
36
    }
37
    else if (x != n && y != n) {
38
        dp(x + 1, y), dp(x, y + 1);
39
        if (le(x + 1, y, x, y + 1)) ne[x][y] = 0;
40
        else ne[x][y] = 1;
41
    }
42
}
43

44
int main() {
45
    scanf("%d%d", &n, &k);
46
    for (int i = 1; i <= n; ++i) {
47
        scanf("%s", a[i] + 1);
48
    }
49
    int mxd = 0;
50
    for (int i = 1; i <= n; ++i) {
51
        for (int j = 1; j <= n; ++j) {
52
            f[i][j] = max(f[i - 1][j], f[i][j - 1]) + (a[i][j] == 'a');
53
            if (f[i][j] + k >= i + j - 1) mxd = max(mxd, i + j - 1);
54
        }
55
    }
56
    if (mxd == n * 2 - 1) {
57
        for (int i = 1; i < 2 * n; ++i) {
58
            printf("a");
59
        }
60
        printf("\n");
61
    }
62
    else if (!mxd) {
63
        dp(1, 1);
64
        int px = 1, py = 1;
65
        while (px != n || py != n) {
66
            printf("%c", a[px][py]);
67
            bool flag = ne[px][py];
68
            px = flag ? px : px + 1, py = flag ? py + 1 : py;
69
        }
70
        printf("%c\n", a[n][n]);
71
    }
72
    else {
73
        int px = 0, py = 0;
74
        for (int i = 1; i <= n; ++i) {
75
            int j = mxd + 1 - i;
76
            if (f[i][j] + k == i + j - 1) {
77
                dp(i, j);
78
                bool flag = ne[i][j];
79
                int npx = flag ? i : i + 1, npy = flag ? j + 1 : j;
80
                if (!px || le(npx, npy, px, py)) px = npx, py = npy;
81
            }
82
        }
83
        for (int i = 0; i < mxd; ++i) printf("a");
84
        while (px != n || py != n) {
85
            printf("%c", a[px][py]);
86
            bool flag = ne[px][py];
87
            px = flag ? px : px + 1, py = flag ? py + 1 : py;
88
        }
89
        printf("%c\n", a[n][n]);
90
    }
91
    return 0;
92
}

E. 饼干#

1
n, m = map(int, input().split())
2
print(n // m)

F. 方差#

水题++

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 100010;
6
long long a[N];
7

8
int main() {
9
    int n;
10
    long long ave = 0;
11
    scanf("%d", &n);
12
    for (int i = 1; i <= n; ++i) {
13
        scanf("%lld", &a[i]);
14
        ave += a[i];
15
    }
16
    ave /= n;
17
    long long res = 0;
18
    for (int i = 1; i <= n; ++i) {
19
        res += (a[i] - ave) * (a[i] - ave);
20
    }
21
    printf("%lld\n", res / n);
22
    return 0;
23
}

G. 正方形划分#

二维的有点乱，思路比较好猜，但是不好操作。

对于操作 0，可以用一种类似二分的思路（但是在二维空间应该叫四分[?]）分别给行号和列号一个左右端点，不断求中间的点，输出目标点相对中间点位置对应的字母，然后缩小区间直到左右端点重叠，循环结束。
对于操作 1，和之前类似，这次是通过给出的序列确定相对位置，缩小区间，相当于是反着来的。

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    ios::sync_with_stdio(0);
7
    cin.tie(0), cout.tie(0);
8
    int T;
9
    cin >> T;
10
    while (T--) {
11
        int op;
12
        cin >> op;
13
        if (!op) {
14
            int n, x, y;
15
            cin >> n >> x >> y;
16
            int lx = 1, ly = 1, rx = 1 << n, ry = 1 << n;
17
            while (lx != rx || ly != ry) {
18
                int mid_x = lx + rx >> 1, mid_y = ly + ry >> 1;
19
                if (x <= mid_x && y <= mid_y) {
20
                    cout << 'A';
21
                    rx = mid_x, ry = mid_y;
22
                }
23
                else if (x <= mid_x && y > mid_y) {
24
                    cout << 'B';
25
                    rx = mid_x, ly = mid_y + 1;
26
                }
27
                else if (x > mid_x && y <= mid_y) {
28
                    cout << 'C';
29
                    lx = mid_x + 1, ry = mid_y;
30
                }
31
                else {
32
                    cout << 'D';
33
                    lx = mid_x + 1, ly = mid_y + 1;
34
                }
35
            }
36
            cout << endl;
37
        }
38
        else {
39
            string s;
40
            cin >> s;
41
            int n = s.length();
42
            int lx = 1, ly = 1, rx = 1 << n, ry = 1 << n;
43
            for (int i = 0; i < n; ++i) {
44
                if (s[i] == 'A') {
45
                    rx = lx + rx >> 1;
46
                    ry = ly + ry >> 1;
47
                }
48
                else if (s[i] == 'B') {
49
                    rx = lx + rx >> 1;
50
                    ly = (ly + ry >> 1) + 1;
51
                }
52
                else if (s[i] == 'C') {
53
                    lx = (lx + rx >> 1) + 1;
54
                    ry = ly + ry >> 1;
55
                }
56
                else {
57
                    lx = (lx + rx >> 1) + 1;
58
                    ly = (ly + ry >> 1) + 1;
59
                }
60
            }
61
            if (lx == rx && ly == ry) cout << n << ' ' << lx << ' ' << ly << endl;
62
            else return 123;
63
        }
64
    }
65
    return 0;
66
}

Star's Blog