JoeyDDong's Blog
AtCoder Beginner Contest 397 Summary
JoeyDDong
  2025-03-20   2025-03-21  2.1k Words  9 Mins

本文是 AtCoder Beginner Conteset（ABC）397 的总结笔记。

A - Thermometer

Problem：A - Thermometer

题目：

模拟。

非常简单的签到题。

题目中已经明说了小数只有一位，所以这里用 double 或者 float 都可以，一般更推荐使用 double。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Problem: https://atcoder.jp/contests/abc397/tasks/abc397_a

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

void solve() {
    double a;
    cin >> a;
    if (a >= 38.0)
        cout << 1 << endl;
    else if (a < 37.5)
        cout << 3 << endl;
    else
        cout << 2 << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

B - Ticket Gate Log

Problem：B - Ticket Gate Log

贪心。

思路也非常的简单。

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
// Problem: https://atcoder.jp/contests/abc397/tasks/abc397_b

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

string s;
void solve() {
    cin >> s;
    int res = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'i' && i + 1 < s.size() && s[i + 1] == 'o') {
            i++;
            continue;
        }
        res += 1;
    }
    cout << res << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

C - Variety Split Easy

Problem：C - Variety Split Easy

题目：

（题目是 F 题的简化版）

给定长度为 N 的整数序列。

在中间某一位置，将 A 分割为两个非空集合。求两个集合不同整数计数之和的最大值。

约束条件：

思路：

思路 1：

简单来说需要解决下面几个问题：

  1. 如何求出集合中的不同整数的个数？

    使用 unordered_set 就可以去除重复数字，得到集合的大小。

  2. 如何维护集合中各个元素的个数？

    使用 cnt 数组来维护。index 是元素的值，value 是元素的个数。

时间复杂度。

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
// Problem: https://atcoder.jp/contests/abc397/tasks/abc397_c

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 3e5 + 10;
int num[N], cnt[N];                      // b 表示右边集合中，各个元素的个数
unordered_set<int> num_left, num_right;  // 左边集合，右边集合
int n, x;

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        num[i] = x;           // 保存数字
        cnt[x]++;             // 记录右边集合数字出现的次数
        num_right.insert(x);  // 将元素插入右边的集合
    }

    int res = 0;
    // 遍历每一个数字
    for (int i = 1; i <= n; i++) {
        x = num[i];          // 获取当前数字
        num_left.insert(x);  // 将当前数字插入左边集合
        cnt[x]--;            // 右边集合中数量减少 1
        // 如果当前元素恰好被清空，就从右边集合中清除当前数字
        if (cnt[x] == 0 && num_right.count(x) > 0)
            num_right.erase(x);
        // 记录答案
        res = max(res, (int)(num_left.size() + num_right.size()));
    }

    cout << res << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

思路 2：

提前预处理出来 pre 和 suc 数组，分别表示“从前往后”和“从后往前”看，截止每个位置的不重复数字的个数。

时间复杂度

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
// Problem: https://atcoder.jp/contests/abc397/tasks/abc397_c

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 3e5 + 10;
int num[N];  // 记录原始数组
// 记录，从“前往后看”和从“后往前看”，截止每个位置的不重复数字个数
int pre[N], suc[N];
unordered_set<int> s;
int n, x;

void solve() {
    // 读入数据
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> num[i];

    // 从前往后看
    for (int i = 1; i <= n; i++) {
        s.insert(num[i]);
        pre[i] = s.size();
    }
    // 清空 set
    s.clear();
    // 从后往前看
    for (int i = n; i >= 1; i--) {
        s.insert(num[i]);
        suc[i] = s.size();
    }

    // 开始求前后集合的最大值
    int res = 0;
    for (int i = 1; i <= n - 1; i++)
        res = max(res, pre[i] + suc[i + 1]);

    cout << res << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

D - Cubes

Problem：D - Cubes

题目：

给定正整数 N。求满足的正整数对。如果不存在，输出 -1

约束条件：

思路：

Tips：long long 的最大值是

如果直接枚举 x 和 y 的话，时间复杂度大约为，肯定是不能被接受的。理想的时间复杂度应该是或者。

那么最好的思路应该是：枚举一个数，然后快速的算出另一个数，判断是否满足条件。

推导思路如下：

image-20250321164444712

通过上面的流程，就可以在枚举 a 的情况下，快速计算出 b，同时快速计算出 x 和 y 的值。（注意流程中的几个隐藏条件即可）

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
// Problem: https://atcoder.jp/contests/abc397/tasks/abc397_d

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

LL N;

void solve() {
    cin >> N;

    // 开始枚举 a
    for (LL a = 1; a * a <= N / a; a++) {
        // 判断是否存在 b
        if (N % a == 0) {
            LL b = N / a;

            // 判断 z 是否是个整数
            LL z = a * a - b;
            if (z % 3 == 0) {
                z /= 3;
                // 判断 y 是否存在
                if (a * a - 4 * z >= 0) {
                    LL root = sqrt(a * a - 4 * z);
                    LL y = (-a + root) / 2;
                    if (y > 0 && (-a + root) % 2 == 0) {
                        LL x = y + a;
                        // 输出答案，结束程序
                        if (x * x * x - y * y * y == N) {
                            cout << x << " " << y << endl;
                            return;
                        }
                    }
                }
            }
        }
    }

    cout << -1 << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

补充题目：

Problem：D - I hate Factorization

这道题目和本题类似，但是难度大大降低。

我们首先考虑一个数列：

简单计算一下这个数列，可以得到下列数据：

1
2
3
4
5
6
7
n = 1: value = 1
n = 2: value = 31
n = 3: value = 211
n = 4: value = 781
……………………
n = 118: value = 953097211
n = 119: value = 985959031

从上面可以知道，前后两个数的五次方之间的差，第一次超过 1e9 是在下标为 120 的时候。

如果两个数之间差距越大，那么他们五次方的差超过 1e9 的速度就越快。从上可以知道，实际上我们仅仅遍历 [-120,120] 之间的数其实就够枚举出答案了。

使用最暴力的全枚举，或者引入 map 预先保存预处理的五次方值，均可以解出本题。

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
// Problem: https://atcoder.jp/contests/abc166/tasks/abc166_d

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

LL X;
void solve() {
    cin >> X;

    // 预处理出来范围内的 五次方值
    unordered_map<LL, LL> mp;
    for (int a = -120; a < 121; a++)
        mp[1ll * a * a * a * a * a] = a;

    // 看一下能不能找到配对的值
    for (pair<LL, LL> d : mp) {
        LL b5 = d.first, b = d.second;
        if (mp.count(X + b5)) {
            LL a = mp[X + b5];
            cout << a << " " << b << endl;
            return;
        }
    }
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

E - Path Decomposition of a Tree

Problem：E - Path Decomposition of a Tree

树状 DP + DFS

题目：

给定一棵树，有个节点，编号为。有条无向边。

判断这棵树是否能被分解为 N 条长度为 K 的路径。

更准确的说，是否存在一个的矩阵 P，满足：

  • 矩阵的所有元素是的一种排列。
  • 矩阵中的元素中，和之间有边相连。（即矩阵中每一行，前后两个节点间都有边）

约束条件：

思路：

详细思路如下图所示：

image-20250321233034316
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
// Problem: https://atcoder.jp/contests/abc397/tasks/abc397_e

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int NK = 2e5 + 10;

vector<int> G[NK];
int n, k, sz[NK];

// 输出 No 并直接结束程序
void NO() {
    cout << "No" << endl;
    // 直接结束程序
    exit(0);
}

void dfs(int u, int fa) {
    sz[u] = 1;
    int son = 0;
    // 遍历 u 的所有子节点
    for (int v : G[u])
        if (v != fa) {
            dfs(v, u);
            // 如果子节点尺寸还有剩余
            if (sz[v]) {
                son++;
                sz[u] += sz[v];
            }
        }

    // 如果 sz[u]<k，说明此时 u 只能形成单链结构
    if (sz[u] < k) {
        // 如果 u 是根节点 或 u 有超过 2 个儿子
        if (u == 1 || son > 1)
            NO();
    }
    // 如果 sz[u]==k，说明此时 u 可以有两个儿子
    else if (sz[u] == k) {
        if (son > 2)
            NO();
        // 清空该子树
        sz[u] = 0;
    }
    // 直接判断不成立
    else
        NO();
}

void solve() {
    // 读入数据 并 建图
    cin >> n >> k;
    for (int i = 1; i < n * k; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }

    // 1号节节点为根节点，0为虚拟父节点
    dfs(1, 0);

    cout << "Yes" << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

F - Variety Split Hard（TODO）

Problem：F - Variety Split Hard

线段树

题目：

给定长度为 N 的整数序列。

在中间某两个位置，将 A 分割为三个非空集合。求三个集合不同整数计数之和的最大值。

约束条件：

思路：

C 题中只切了一刀，分割为了两个集合。

本题中是切了两刀，分割为了三个集合。

AtCoder Beginner Contest 397 Summary
2025/blog/58927/
Author
JoeyDDong
Published
2025-03-20 22:01
License
  1. A - Thermometer
    1. 题目：
  2. B - Ticket Gate Log
  3. C - Variety Split Easy
    1. 题目：
    2. 约束条件：
    3. 思路：
      1. 思路 1：
      2. 思路 2：
  4. D - Cubes
    1. 题目：
    2. 约束条件：
    3. 思路：
    4. 补充题目：
  5. E - Path Decomposition of a Tree
    1. 题目：
    2. 约束条件：
    3. 思路：
  6. F - Variety Split Hard（TODO）
    1. 题目：
    2. 约束条件：
    3. 思路：
  1. A - Thermometer
    1. 题目：
  2. B - Ticket Gate Log
  3. C - Variety Split Easy
    1. 题目：
    2. 约束条件：
    3. 思路：
      1. 思路 1：
      2. 思路 2：
  4. D - Cubes
    1. 题目：
    2. 约束条件：
    3. 思路：
    4. 补充题目：
  5. E - Path Decomposition of a Tree
    1. 题目：
    2. 约束条件：
    3. 思路：
  6. F - Variety Split Hard（TODO）
    1. 题目：
    2. 约束条件：
    3. 思路：