1561 字

8 分钟

Codeforces Round 981 (Div. 3)

2024-10-25

2024-10-26

算法

Codeforces

/

Div. 3

/

cpp

Codeforces Round 981 (Div. 3)#

唉唉，这场搁楼道里打的，降温了忘添衣了，打得冻死了，咳嗽似乎还加重了。

水逆、衰。

A. Sakurako and Kosuke#

读题读完直觉就是判奇偶。何况依据题意双方路线固定。

复杂度 $\Theta(1)$ 。

代码如下：

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
#define rep(i, a, b) for (auto i = (a); i <= decltype(i)(b); ++i)
6

7
inline void solve() {
8
    int n; cin >> n;
9
    if (n & 1) cout << "Kosuke" << char(10);
10
    else cout << "Sakurako" << char(10);
11
}
12

13
signed main() {
14
    cin.tie(nullptr)->sync_with_stdio(false);
15

16
    int T; cin >> T;
17
    while (T--) solve();
18
    return 0;
19
}

B. Sakurako and Water#

n范围很小。实际上就是求每一个斜行的最小的负数的总和。

复杂度 $\Theta(n)$ 。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
#define rep(i, a, b) for (auto i = (a); i <= decltype(i)(b); ++i)
6
#define per(i, a, b) for (decltype(b) i = (a); i >= b; --i)
7

8
inline void solve() {
9
    int n; cin >> n;
10
    vector< vector<int> > a(n + 10, vector<int>(n + 10));
11
    rep (i, 1, n) rep (j, 1, n)
12
        cin >> a[i][j];
13

14
    int ans = 0;
15
    rep (i, 1, n) {
16
        int mi = 0;
17
        for (int x = 1, y = i; x <= n && y <= n; ++x, ++y)
18
            if (a[x][y] < 0) mi = min(mi, a[x][y]);
19
        ans += -mi;
20
    }
21
    per (i, n, 2) {
22
        int mi = 0;
23
        for (int x = i, y = 1; x <= n && y <= n; ++x, ++y)
24
            if (a[x][y] < 0) mi = min(mi, a[x][y]);
25
        ans += -mi;
26
    }
27
    cout << ans << char(10);
28
}
29

30
signed main() {
31
    cin.tie(nullptr)->sync_with_stdio(false);
32

33
    int T; cin >> T;
34
    while (T--) solve();
35
    return 0;
36
}

C. Sakurako’s Field Trip#

一道莫名其妙通过率挺低的题。

实际上好像有dp解法，奈何我是dp苦手。

但是做题时贪心过的挺快的。

首先，注意到该题目对称性，故考虑 $i$ 与 $n - i + 1$ 的对称位置。

注意到对答案贡献的方式，不妨考虑相邻的对称位置，在确定思考方向是由中间向两边还是两边向中间的前提下，在已经确定一部分组的解时，考虑新的一组位置的贡献是无后效性的。

故考虑贪心。

实际上回头思考从两边向中间贪心和中间向两边贪心应该相似，因为考虑的第一组最外层或者最内层交换与否只是影响 $[L, mid - 1], [mid + 1, R]$ 是否需要对调。

实现的时候分奇偶了，实际上感觉或许不需要。

复杂度 $\Theta(n)$ 。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
#define rep(i, a, b) for (auto i = (a); i <= decltype(i)(b); ++i)
6

7
inline void solve() {
8
    int n; cin >> n;
9
    vector<int> a(n + 10);
10
    rep (i, 1, n) cin >> a[i];
11

12
    int mid = midpoint(1, n);
13
    auto check = [&](int i, int j) {
14
        return ((a[i] == a[i + 1]) + (a[j - 1] == a[j])) > ((a[j] == a[i + 1]) + (a[j - 1] == a[i]));
15
    };
16
    if (n & 1) { // odd
17
        for (int i = mid - 1, j = mid + 1; i >= 1 && j <= n; --i, ++j)
18
            if (check(i, j)) swap(a[i], a[j]);
19
    } else {
20
        for (int i = mid - 1, j = mid + 2; i >= 1 && j <= n; --i, ++j)
21
            if (check(i, j)) swap(a[i], a[j]);
22
    }
23

24
    int ans = 0;
25
    rep (i, 1, n - 1)
26
        if (a[i] == a[i + 1]) ++ans;
27
    cout << ans << char(10);
28
}
29

30
signed main() {
31
    cin.tie(nullptr)->sync_with_stdio(false);
32

33
    int T; cin >> T;
34
    while (T--) solve();
35
    return 0;
36
}

D. Kousuke’s Assignment#

做题时脑子抽了 insert(val) 写成 insert(a[i]) 错了就开始怀疑人生的一道题。。。

实际上思路没有太大毛病。

考虑如下转化：找到所有满足题设的 $[L, R]$ ，显然可以转化为给定区间，求最多多少区间覆盖问题。

则实际上我们只要发现出现相同的前缀和时就截断区间统计答案就好。如此可以尽可能让后方的区间有更多“空间”对答案进行贡献。

注意 Codeforces 需要 C++23 才能正常使用 __gnu_pbds。

复杂度 $\Theta(n)$ 。

1
#include <bits/stdc++.h>
2
#include <bits/extc++.h>
3

4
using namespace std;
5
using namespace __gnu_pbds;
6

7
#define int long long
8
#define rep(i, a, b) for (auto i = (a); i <= decltype(i)(b); ++i)
9

10
inline void solve() {
11
    int n; cin >> n;
12
    vector<int> a(n + 10);
13
    rep (i, 1, n) cin >> a[i];
14

15
    gp_hash_table<int, bool> hsh;
16
    int val = 0, ans = 0;
17
    hsh[0] = 1;
18
    rep (i, 1, n) {
19
        val += a[i];
20
        if (hsh.find(val) != hsh.end()) {
21
            hsh.clear(); hsh[0] = 1;
22
            ++ans; val = 0;
23
        } else hsh[val] = 1;
24
    }
25

26
    cout << ans << char(10);
27
}
28

29
signed main() {
30
    cin.tie(nullptr)->sync_with_stdio(false);
31

32
    int T; cin >> T;
33
    while (T--) solve();
34
    return 0;
35
}

E. Sakurako, Kosuke, and the Permutation#

额啊，是一道挺玄学的题。。。（仅仅对我个人而言）

听同学和jiangly群u说其实挺典的？（冒汗）

大致思路如下：

题意要求每个 $i$ ，都要满足自己构成自环或者二元环。故每次暴力的将点数大于二的环拆开即可。

以下是证明：拆环顺序与解的最优性无关来自jiangly二群群友 @Arkweedy：

首先交换的两点必然是同一个点数大于二的环，在环内交换实际上是每次将一个环破成两个环，其中一个环点数为二。每次环点数个数减二，故分解次数和分解顺序或方式无关。

复杂度 $\Theta(n)$ 。

1
#include <bits/stdc++.h>
2
#include <bits/extc++.h>
3

4
using namespace std;
5
using namespace __gnu_pbds;
6

7
#define rep(i, a, b) for (auto i = (a); i <= decltype(i)(b); ++i)
8

9
inline void solve() {
10
    int n; cin >> n;
11
    vector<int> a(n + 10);
12
    gp_hash_table<int, int> hsh;
13
    rep (i, 1, n) { cin >> a[i]; hsh[a[i]] = i; }
14

15
    int ans = 0;
16
    rep (i, 1, n) {
17
        if (a[i] == i || a[a[i]] == i) continue;
18
        int x = a[a[i]];
19
        swap(a[a[i]], a[hsh[i]]);
20
        hsh[x] = hsh[i];
21
        hsh[i] = a[i];
22
        ++ans;
23
    }
24
    cout << ans << char(10);
25
}
26

27
signed main() {
28
    cin.tie(nullptr)->sync_with_stdio(false);
29

30
    int T; cin >> T;
31
    while (T--) solve();
32
    return 0;
33
}

F. Kosuke’s Sloth#

实际上普遍认为这题比 E 简单。。。

显然在模 $k$ 意义下斐波那契数列仍然成立，不过将会退化成一个循环数列。

故每次直接将循环节暴力找出然后乘 $n$ 即可。

实际循环节长度不会很大，最大为 $6k$ 。

证明~~我也不会~~详见 zky’s blog。

时间复杂度 $\Theta(k)$ 。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using i64 = long long;
5

6
#define rep(i, a, b) for (auto i = (a); i <= decltype(i)(b); ++i)
7

8
constexpr int P = 1e9 + 7;
9

10
inline void solve() {
11
    i64 n; int k;
12
    cin >> n >> k;
13
    vector<int> a(6 * k + 10);
14

15
    int len = 1;
16
    if (k == 1) goto lab;
17

18
    a[1] = 1 % k; a[2] = 1 % k;
19
    rep (i, 3, 6 * k) {
20
        a[i] = (1ll * a[i - 2] + a[i - 1]) % k;
21
        if (a[i] == 0) { len = i; break; }
22
    }
23

24
    lab:;
25
    n %= P;
26
    cout << (1ull * len * n) % P << endl;
27
}
28

29
signed main() {
30
    cin.tie(nullptr)->sync_with_stdio(false);
31

32
    int T; cin >> T;
33
    while (T--) solve();
34
    return 0;
35
}