第二周训练

1. ABC E - Chinese Restaurant (Three-Star Version)

题意

圆盘周围坐着 \(n\) 个人。圆盘上有 \(n\) 个菜，各有编号 \(C_i\)。圆盘可以随意转动，要求最小化 \[ \sum_1^n(dis(i, C_i)) \]

做法

每个菜对于那个人的距离实际上是一段 \(2\) 或者 \(3\) 段函数。将函数相加即可。函数用前缀数组 \(b\)，\(k\) 表示。

代码

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
/**
 * @author: XiaFan
 * @date: 09-12 20:49
 **/
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> pos(n);
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        pos[x] = i;
    }

    std::vector<i64> sk(n), sb(n);

    auto add = [&](int l, int r, int k, int b) {
        if (l > r) return;
        sk[l] += k;
        sb[l] += b;
        if (r + 1 < n) {
            sk[r + 1] -= k;
            sb[r + 1] -= b;
        }
    };

    auto fun = [&](int v) {
        if (v < n / 2) {
            add(0, v - 1, -1, v);
            add(v, v + n / 2, 1, -v);
            add(v + n / 2 + 1, n - 1, -1, n + v);
        } else {
            add(0, v - n / 2 - 1, 1, n - v);
            add(v - n / 2, v - 1, -1, v);
            add(v, n - 1, 1, -v);
        }
    };

    for (int i = 0; i < n; i++) {
        int v = (pos[i] - i + n) % n;
        fun(v);
    }
    for (int i = 1; i < n; i++) {
        sk[i] += sk[i - 1];
        sb[i] += sb[i - 1];
    }

    i64 ans = 1LL << 60;
    for (int i = 0; i < n; i++) {
        ans = std::min(ans, sk[i] * i + sb[i]);
    }
    std::cout << ans << "\n";

    return 0;
}

2. ABC G - Random Student ID

题意

按照某种顺序的字母表对人名经行词典排序，求每个人位次的期望

做法

如果 \(X\) 的人名的前缀字符串不是一个人名（\(Y\) 的），那就是 \(\lfloor \frac{n}{2} \rfloor\)，否则 \(Y\) 将一直在前面，\(X\) 名次向后
使用 \(Trie\) 来保存人名词典

代码

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
73
74
75
76
77
78
/**
 * @author: XiaFan
 * @date: 09-13 19:07
 **/
#include <bits/stdc++.h>
using i64 = long long;

constexpr i64 P = 998244353;

namespace Trie {
constexpr int N = 5E5 + 2;

int trie[N][26], have[N], sum[N];
int cnt = 1;

void insert(std::string s) {
    int p = 1;
    for (auto c : s) {
        int x = c - 'a';
        if (!trie[p][x]) {
            trie[p][x] = ++cnt;
        }
        p = trie[p][x];
        sum[p]++;
    }
    have[p] = 1;
}

bool find(const std::string &s) {
    int p = 1;
    for (const auto c : s) {
        int x = c - 'a';
        if (!trie[p][x]) {
            return false;
        }
        p = trie[p][x];
    }
    return have[p];
}

}  // namespace Trie

i64 fun(i64 x, i64 y) {
    for (i64 i = x; true; i += P) {
        if (i % y == 0) {
            return (i / y);
        }
    }
    return -1;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    std::vector<std::string> s(n);
    std::map<i64, i64> mp, ans; 
    for (int i = 0; i < n; i++) {
        std::cin >> s[i];
        Trie::insert(s[i]);
    }

    for (int i = 0; i < n; i++) {
        int p = 1;
        i64 ans = n;
        for (const auto c : s[i]) {
            int x = c - 'a';
            p = Trie::trie[p][x];
            ans = (ans + Trie::have[p]) % P;
        }
        ans = (ans - Trie::sum[p] + P) % P;
        std::cout << fun(ans + 1, 2) << "\n";
    }

    return 0;
}

3. ABC Ex - Taboo

题意

在 \(S\) 中选择任意位置改为 * 使得 \(S\) 中没有任何 \(T\)

做法

使用 \(AC\)自动机 保存词典，然后跑一边 \(S\) 就可以了

代码

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/**
 * @author: XiaFan
 * @date: 09-11 22:24
 **/
#include <bits/stdc++.h>
using i64 = long long;

namespace Trie {

constexpr int n = 5e5, m = 26;
int cnt = 1;
int trie[n][m];
int fail[n], have[n];

void init() {
    std::fill(trie[0], trie[0] + m, 1);
}

void insert(std::string t) {
    int p = 1;
    for (auto c : t) {
        int x = c - 'a';
        if (!trie[p][x]) {
            trie[p][x] = ++cnt;
        }
        p = trie[p][x];
    }
    have[p] = 1;
}

void build() {
    std::queue<int> q;
    q.push(1);

    while (!q.empty()) {
        int x = q.front();
        q.pop();

        have[x] |= have[fail[x]];
        for (int i = 0; i < m; i++) {
            if (trie[x][i]) {
                fail[trie[x][i]] = trie[fail[x]][i];
                q.push(trie[x][i]);
            } else {
                trie[x][i] = trie[fail[x]][i];
            }
        }
    }
}

bool find(const std::string &s) {
    int p = 1;
    for (const auto c : s) {
        int x = c - 'a';
        p = trie[p][x];
        if (have[p]) {
            return true;
        }
    }
    return false;
}

}  // namespace Trie

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string s;
    std::cin >> s;
    int n;
    std::cin >> n;
    std::vector<std::string> t(n);

    Trie::init();

    for (auto t_i : t) {
        std::cin >> t_i;
        Trie::insert(t_i);
    }

    Trie::build();

    int ans = 0;
    int p = 1;
    for (int i = 0; i < int(s.length()); i++) {
        int x = s[i] - 'a';
        p = Trie::trie[p][x];
        if (Trie::have[p]) {
            ans++;
            p = 1;
        }
    }
    std::cout << ans << "\n";

    return 0;
}

4. CF Round #820 F. Kirei and the Linear Function

题意

\(v(x, y)\) 是字符串 \(S\) 的从下表 \(x\) 到 \(y\) 的切片转为数字的函数，给定 \(l_i\)、\(r_i\)、\(w\)，使得 \[ (v(L1, L1 + w - 1) \times v(l_i, r_i) + v(L2, L2 + w - 1)) \equiv k\mod 9 \] 求 \(L1\)、\(L2\)，且最小化

做法

\(\mod 9\) 使得转数字函数原本 \(\times 10\) 进位可以变成加法，这样使用前缀和可以轻松求得片段和

代码

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
#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    std::string s;
    std::cin >> s;
    
    int n = s.length();
    
    int w, m;
    std::cin >> w >> m;
    
    std::vector<int> f(n + 1);
    for (int i = 0; i < n; i++) {
        f[i + 1] = f[i] + s[i] - '0';
    }
    
    std::vector<int> a[9];
    for (int i = 0; i + w <= n; i++) {
        int x = (f[i + w] - f[i]) % 9;
        a[x].push_back(i);
    }
    
    for (int i = 0; i < m; i++) {
        int l, r, k;
        std::cin >> l >> r >> k;
        
        int x = (f[r] - f[l - 1]) % 9;
        
        std::array<int, 2> ans{n, n};
        for (int u = 0; u < 9; u++) {
            if (a[u].size() > 1 && (u * x + u) % 9 == k) {
                ans = std::min(ans, std::array{a[u][0], a[u][1]});
            }
            for (int v = 0; v < 9; v++) {
                if (u != v && !a[u].empty() && !a[v].empty() && (u * x + v) % 9 == k) {
                    ans = std::min(ans, std::array{a[u][0], a[v][0]});
                }
            }
        }
        
        if (ans[0] == n) {
            std::cout << -1 << " " << -1 << "\n";
        } else {
            std::cout << ans[0] + 1 << " " << ans[1] + 1 << "\n";
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}