2025春训第二场 - Star's Blog

考场上只做出来了 A、B、C，拼尽全力无法战胜数学题😭😭😭。

D 一开始想错了方向，各种分解质因数把自己搞头疼了都，事后暴力莽出来了；E 事后打表打了 20min 以惊人的毅力拿下（别急，还有反转）。

A. 矩形#

把三个矩形的左下角坐标取 max，右上角坐标取 min，就是重叠部分的矩形。

ps：注意判断是否重叠，否则不重叠的可能会负负得正，然后 WA.

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
    long long x1, y1, x2, y2;
9
    long long a1, b1, a2, b2;
10
    cin >> x1 >> y1 >> x2 >> y2;
11
    cin >> a1 >> b1 >> a2 >> b2;
12
    x1 = max(x1, a1), y1 = max(y1, b1), x2 = min(x2, a2), y2 = min(y2, b2);
13
    cin >> a1 >> b1 >> a2 >> b2;
14
    x1 = max(x1, a1), y1 = max(y1, b1), x2 = min(x2, a2), y2 = min(y2, b2);
15
    if (x2 - x1 <= 0 || y2 - y1 <= 0) cout << 0 << endl;
16
    else cout << max(0ll, (x2 - x1) * (y2 - y1)) << endl;
17
    return 0;
18
}

这么水的题还有人用 AI 写，还被抓了😲.

B. 全球通勤#

每条边的 VIP 是相互独立的，直接差分前缀和统计每条边经过的次数，最后遍历一次算出来每条边的最优解加起来即可。

ps：注意 l 可能大于 r，可能需要 swap 一下。

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

4
using namespace std;
5

6
const int N = 5000010;
7
int a[N], b[N], c[N];
8
int t[N];
9

10
int main() {
11
    int n, m;
12
    scanf("%d%d", &n, &m);
13
    for (int i = 1; i < n; ++i) {
14
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
15
    }
16
    while (m--) {
17
        int l, r;
18
        scanf("%d%d", &l, &r);
19
        if (l > r) swap(l, r);
20
        t[l]++, t[r]--;
21
    }
22
    long long res = 0;
23
    for (int i = 1; i < n; ++i) {
24
        t[i] += t[i - 1];
25
        res += min(t[i] * a[i], t[i] * c[i] + b[i]);
26
    }
27
    printf("%lld\n", res);
28
    return 0;
29
}

C. 社交网络#

不能继续执行操作的情况只有一种，任何一个点所在的连通块都是完全图。所以直接找连通块，统计连通块的点数和边数算出每个连通块的操作次数累加即可。

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

5
using namespace std;
6

7
const int N = 200010;
8
vector<int> ed[N];
9
int id[N], tot;
10
int cnt[N], ed_cnt[N];
11

12
void dfs(int x) {
13
    if (id[x]) return;
14
    id[x] = tot;
15
    cnt[tot]++;
16
    for (int y : ed[x]) {
17
        dfs(y);
18
    }
19
}
20

21
int main() {
22
    int n, m;
23
    scanf("%d%d", &n, &m);
24
    for (int i = 0; i < m; ++i) {
25
        int x, y;
26
        scanf("%d%d", &x, &y);
27
        ed[x].push_back(y);
28
        ed[y].push_back(x);
29
    }
30
    for (int i = 1; i <= n; ++i) {
31
        sort(ed[i].begin(), ed[i].end());
32
        ed[i].erase(unique(ed[i].begin(), ed[i].end()), ed[i].end());
33
    }
34
    for (int i = 1; i <= n; ++i) {
35
        if (!id[i]) {
36
            ++tot;
37
            dfs(i);
38
        }
39
    }
40
    for (int i = 1; i <= n; ++i) {
41
        ed_cnt[id[i]] += ed[i].size();
42
    }
43
    long long res = 0;
44
    for (int i = 1; i <= tot; ++i) {
45
        res += (long long)cnt[i] * (cnt[i] - 1) / 2 - ed_cnt[i] / 2;
46
    }
47
    cout << res << endl;
48
    return 0;
49
}

D. 数数#

我的做法有点暴力，但是时间复杂度是没有问题的。

首先考虑暴力如何解决，直接枚举指数 i in [2, 60]，底数 j in [1, $n^{\frac{1}{i}}$ ]，把所有 $j^i$ 去重统计个数。
不难发现暴力的瓶颈在 $\sqrt{n}$ 上，如果 i 从 3 开始枚举，那么就不会 TLE，所以干脆直接从 3 枚举，如果 $j^i$ ，是平方数就直接忽略，最后一次性加进去一个 $\sqrt n$ 即可。
n = 1e18 时时间复杂度是 1e6 级别的，完全可行。

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

5
using namespace std;
6

7
long long power(long long n, long long p) {
8
    long long res = 1, base = n;
9
    while (p) {
10
        if (p & 1) res = res * base;
11
        base = base * base;
12
        p >>= 1;
13
    }
14
    return res;
15
}
16

17
unordered_set<long long> s;
18

19
int main() {
20
    long long n;
21
    cin >> n;
22
    for (int i = 60; i >= 3; --i) {
23
        for (int j = (long long)pow(n, 1.0 / i); j; --j) {
24
            long long t = power(j, i);
25
            if (power((int)sqrt(t), 2) != t) s.insert(t);
26
        }
27
    }
28
    cout << s.size() + (int)(sqrt(n) + 1e-9) << endl;
29
    return 0;
30
}

E. 出题 (problem)#

我能力不足，找不到选择策略，只能暴搜了😭

**迭代加深：**因为要求方案字典序最小，所以必须优先搜小的，然而优先搜小的可能会导致递归层数增长过快爆栈或者 TLE，所以用迭代加深一步步试探可行性更高。
剪枝1: 当前序列最后一位大于 n 时，直接不用搜了。
剪枝2: 当前序列最后一位的 2^cnt 倍小于 n 时，一定不合法，即使不断翻倍也无法在指定步数内到达 n。（其中cnt = 后续空位数）

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

4
using namespace std;
5

6
int cur[20];
7
int n;
8

9
bool dfs(int x, int d) {
10
    if (x > d) {
11
        if (cur[x - 1] == n) return true;
12
        else return false;
13
    }
14
    if (cur[x - 1] > n || (long long)cur[x - 1] * (1 << (d - x + 1)) < n) return false;
15
    for (int i = 0; i < x; ++i) {
16
        for (int j = 0; j <= i; ++j) {
17
            if (cur[i] + cur[j] > cur[x - 1]) {
18
                cur[x] = cur[i] + cur[j];
19
                if (dfs(x + 1, d)) return true;
20
            }
21
        }
22
    }
23
    return false;
24
}
25

26
int main() {
27
    scanf("%d", &n);
28
    int l;
29
    cur[0] = 1;
30
    for (l = 1; !dfs(1, l); ++l);
31
    for (int i = 1; i <= l; ++i) {
32
        printf("%d ", cur[i]);
33
    }
34
    printf("\n");
35
    return 0;
36
}

WARNINGS#

不要用 vector 频繁 push_back 和 pop_back，会严重超时！！！~~害我打了 20min 表~~
注意常数优化，能算一次就不算第二次，否则搜索规模会指数级扩大。

F. 连续段 (row)#

这道题目前 0/0，我量力而为💔