2024-2025 ICPC NERC, Kyrgyzstan Qualification Contest

题目链接#

2024-2025 ICPC NERC, Kyrgyzstan Qualification Contest

A. Problem Statement #

题意#

给 $n$ 行字符串，问输入了几个回车

题解#

输出 $n-1$

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n;
4
    cin >> n;
5
    cout << n - 1 << '\n';
6
}

B. Ant Hill #

题意#

给定 $n$ 个数表示蚂蚁山中，蚂蚁的进出，蚂蚁山在任何时刻蚂蚁的数量都不为负数，求最开始至少有几只蚂蚁

题解#

从头开始模拟蚂蚁的进出，设 $res$ 为当前蚂蚁山的数量， $ans = -\min\{res | res \leq 0\}$

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n;
4
    cin >> n;
5
    ll ans = 0;
6
    ll p = 0;
7
    for(int i = 1;i <= n; i++){
8
        ll x;
9
        cin >> x;
10
        p += x;
11
        if(p <= 0) ans = max(ans, -p);
12
    }
13
    cout << ans << '\n';
14
}

C. Linear Maze #

题意#

$n$ 个房间，每次可以从房间 $n$ 转移到房间 $n + 1$ ，有 $k$ 个特殊房间，如果在奇数次访问这样一个房间，下一步则会传送到房间 $1$ ，问离开迷宫要经过几个房间

题解#

当访问到普通房间时，步数 + 1，如果访问到特殊房间，则步数 + 1后翻倍，显然访问到特殊房间后，回到该房间需要重新走相同的路程

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n, k;
4
    cin >> n >> k;
5
    vector<int> a(n + 1);
6
    for(int i = 1;i <= k; i ++){
7
        int x;
8
        cin >> x;
9
        a[x] = 1;
10
    }
11
    ll ans = 0;
12
    for(int i = 1;i <= n; i++){
13
        ans ++;
14
        if(a[i]) ans *= 2;
15
    }
16
    cout << ans << '\n';
17
}

D. Grouping #

题意#

将 $n$ 个数字分为最小数目的好数集，好数集的定义如下：

集合的大小不超过 $k$
集合的最大值和最小值之差不超过 $M$

题解#

排序原数组，贪心地将其放入当前集合中，若满足则放入，否则另开一个新集合

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n, m, k;
4
    cin >> n >> m >> k;
5
    vector<ll> a(n);
6
    for (int i = 0; i < n; i++) cin >> a[i];
7
    sort(a.begin(), a.end());
8
    ll num = -INF;
9
    int cnt = m;
10
    int ans = 0;
11
    for (int i = 0; i < n; i++) {
12
        if (cnt == k) {
13
            cnt = 1;
14
            num = a[i];
15
            ans++;
16
        } else if (a[i] - num > m) {
17
            cnt = 1;
18
            num = a[i];
19
            ans++;
20
        } else {
21
            cnt++;
22
        }
23
    }
24
    cout << ans << endl;
25
}

H. Hierarchy #

题意#

给定几个公司的员工架构树，求员工数量最多的一个公司

题解#

DFS求每个树的大小即可

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n;
4
    cin >> n;
5
    vector<vector<int> > son(n + 1);
6
    for (int i = 1; i <= n; i++) {
7
        int x;
8
        cin >> x;
9
        son[x].push_back(i);
10
    }
11
    vector<int> dp(n + 1, 0);
12
    int ans = 0;
13
    int maxn = 0;
14
    function<void(int)> dfs = [&](int u) {
15
        if (son[u].empty()) {
16
            dp[u] = 1;
17
            return;
18
        }
19
        for (auto v : son[u]) {
20
            dfs(v);
21
            dp[u] += dp[v];
22
            if (u == 0 && dp[v] > maxn) {
23
                maxn = dp[v];
24
                ans = v;
25
            }
26
        }
27
        dp[u] += 1;
28
    };
29
    dfs(0);
30
    cout << ans << ' ' << maxn << endl;
31
}

I. Study Day #

题意#

参加 $n$ 次讲座，每次可以获得 $a_i$ 点知识点，可以在参加前进行冥想使得这次获得的知识点翻倍，不能连续冥想两次，问知识点最多为多少？

题解#

令 $dp_m(i)$ 表示第 $i$ 次未冥想获得的最多知识点， $dp_o(i)$ 表示第 $i$ 次冥想获得的最多的知识点，那么满足：

dp_m(i) = \max(dp_o(i - 1), dp_m(i - 1)) + a_i \\ dp_o(i) = dp_m(i-1) + 2 \times a_i

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n;
4
    cin >> n;
5
    vector<vector<ll> > dp(2, vector<ll>(n + 1));
6
    vector<string> ans(2);
7
    for (int i = 1; i <= n; i++) {
8
        ll x;
9
        cin >> x;
10
        auto tmp = ans;
11
        if (dp[0][i - 1] > dp[1][i - 1]) {
12
            dp[0][i] = dp[0][i - 1] + x;
13
            ans[0] = tmp[0] + 'O';
14
        } else {
15
            dp[0][i] = dp[1][i - 1] + x;
16
            ans[0] = tmp[1] + 'O';
17
        }
18
        dp[1][i] = dp[0][i - 1] + 2 * x;
19
        ans[1] = tmp[0] + 'M';
20
    }
21
    if (dp[0][n] > dp[1][n]) {
22
        cout << dp[0][n] << endl;
23
        cout << ans[0] << endl;
24
    } else {
25
        cout << dp[1][n] << endl;
26
        cout << ans[1] << endl;
27
    }
28
}

F. Traffic Lights #

题意#

有 $n$ 个路口，到达一个路口花费 $a_i$ ，路口处红灯亮 $r_i$ 秒，绿灯亮 $g_i$ 秒，一开始红灯亮了 $d_i$ 秒，求通过所有路口花费的总时间

题解#

令 $time$ 为到达路口时花费的总时间，那么该路口的灯已经亮了 $time + d_i$ 秒，显然路口的灯以 $r_i + g_i$ 为周期循环，令 $rem = (time + d_i) \mod (r_i + g_i)$ ，当 $rem < g_i$ 时，为绿灯，直接通过，当 $rem > r_i$ 时为红灯， $time := time + r_i + g_i - rem$

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n;
4
    cin >> n;
5
    vector<int> a(n + 1), r(n + 1), g(n + 1), d(n + 1);
6
    for(int i = 1; i <= n; i++){
7
        cin >> a[i];
8
    }
9
    for(int i = 1; i <= n; i++){
10
        cin >> r[i] >> g[i] >> d[i];
11
    }
12
    ll time = 0;
13
    for(int i = 1;i <= n; i++){
14
        time += a[i];
15
        ll t = time + d[i];
16
        ll rem = t % (r[i] + g[i]);
17
        if(rem < g[i]){
18
            continue;
19
        }
20
        else{
21
            time += r[i] + g[i] - rem;
22
        }
23
    }
24
    cout << time << endl;
25
}

G. Need More Gold #

题意#

有 $n$ 个怪物，每个怪物打败需要 $b_i$ 个金币（不花费），打败后获得 $g_i$ 个金币，求积累 $w$ 个金币最少打败怪物的数量和顺序

题解#

维护优先队列，每一次选择当前可打败的价值最高的怪物。

代码#

1
struct node {
2
    int id;
3
    ll x, y;
4
    bool operator<(const node &rhs) const { return x < rhs.x; }
5
};
6
void idol_produce(int testCase) {
7
    /*Code Here*/
8
    ll w, n;
9
    cin >> w >> n;
10
    vector<node> a(n + 1);
11
    for (int i = 0; i < n; i++) {
12
        cin >> a[i].x >> a[i].y;
13
        a[i].id = i + 1;
14
    }
15
    sort(a.begin(), a.end(), [](node a, node b) { return a.y > b.y; });
16
    priority_queue<node> q;
17
    vector<int> ans;
18
    ll now = 0;
19
    while (!a.empty() && a.back().y == 0) {
20
        q.push(a.back());
21
        a.pop_back();
22
    }
23
    while (!q.empty() && now < w) {
24
        node t = q.top();
25
        q.pop();
26
        now += t.x;
27
        ans.emplace_back(t.id);
28
        while (!a.empty() && a.back().y <= now) {
29
            q.push(a.back());
30
            a.pop_back();
31
        }
32
    }
33
    if (now < w) {
34
        cout << -1 << endl;
35
        return;
36
    }
37
    cout << ans.size() << endl;
38
    for (auto i : ans) {
39
        cout << i << " ";
40
    }
41
}

E. Mountain Ranges #

题意#

$n$ 座山，假如相邻两座山之间的高度差不大于 $k$ ，则视为同一座山脉，问最小的 $k$ 使得恰好划分为 $m$ 座山脉

题解#

二分 $k$ ，当 $ans > m$ 时， $k$ 向上二分，否则向上二分

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n, m;
4
    cin >> n >> m;
5
    vector<int> a(n + 1);
6
    for(int i = 1;i <= n; i++){
7
        cin >> a[i];
8
    }
9
    if(n == 1){
10
        cout << 1 << '\n';
11
        return;
12
    }
13
    int l = 1, r = 1e6;
14
    int ans = -1;
15
    while(l <= r){
16
        int mid = (l + r) >> 1;
17
        int cnt = 1;
18
        for(int i = 2;i <= n; i++){
19
            if(abs(a[i] - a[i - 1]) > mid){
20
                cnt++;
21
            }
22
        }
23
        if(cnt > m){
24
            l = mid + 1;
25
        }
26
        else if(cnt == m){
27
            ans = mid;
28
            r = mid - 1;
29
        }
30
        else{
31
            r = mid - 1;
32
        }
33
    }
34
    cout << ans << endl;
35
}