没什么意思的一场div3

1238A Divisibility Problem

求给$a$加$1$几次可以成为$b$的倍数，$O(1)$。

A.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << (b - a % b) % b << endl;
    }
    return 0;
}

1238B K-th Beautiful String

一个长度为$n$的字符串，只有$2$个$b$,剩下都是$a$，问字典序第$k$大的是哪个串。

因为只有$2$个$b$，所以通过两个$b$的位置知道是第几词典序，$O(k)$。

B.cpp
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
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int q;
    cin >> q;
    while (q--) {
        int n, k, i1 = 2, i2;
        cin >> n >> k;
        while (k) {
            if (k <= (i1 - 1)) break;
            k -= i1 - 1;
            ++i1;
        }
        i2 = k;
        for (int i = n; i > 0; --i) {
            if (i == i1 || i == i2)
                cout << 'b';
            else
                cout << 'a';
        }
        cout << endl;
    }
    return 0;
}

1238C Ternary XOR

有两个长为$n$仅由$0,1,2$组成的数，定义它们的异或是模不进位$3$加法，给出结果，求一组原始的数$a,b$，要求$max(a,b)$最小。

  • 如果$x_i = 0$，那么$a_i = b_i = 0$；
  • 第一次$x_i = 1$，给$a,b$之一赋$1$，之后出现的话给另一个数赋$1$；
  • 如果$x_i = 2$，且$a,b$一直相等，那么$a_i = b_i = 0$，如果已经不相等，给小的数赋$2$。
    $O(n)$
C.cpp
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
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int q;
    cin >> q;
    string s, a, b;
    while (q--) {
        int n;
        cin >> n >> s;
        a.resize(n);
        b.resize(n);
        int f = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '2') {
                if (!f)
                    a[i] = b[i] = '1';
                else
                    a[i] = '2', b[i] = '0';
            } else if (s[i] == '0')
                a[i] = b[i] = '0';
            else if (!f) {
                b[i] = '1', a[i] = '0';
                f = 1;
            } else
                a[i] = '1', b[i] = '0';
        }
        cout << a << endl << b << endl;
    }
    return 0;
}

一个长$n$的环，环上每个数都有种类，要求相邻且不同种类的数被涂的颜色不同，问最少颜色数的方案。

  • 如果只有一种，全部涂一种颜色；
  • 如果每种颜色一个，环长为偶数，只需要两种颜色间隔涂；环长为奇数，必须有一个涂颜色$3$；
  • 如果某种颜色有多个，环长为偶数，只需要间隔涂色；环长为奇数，从某个相邻为同种的数断开间隔涂色。
    $O(n)$
D.cpp
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
#include <bits/stdc++.h>

#define endl '\n'
using namespace std;

const int N = 5e5 + 5;

int a[N];

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        a[n] = a[0];
        int f = 1;
        for (int i = 1; i <= n; ++i) {
            if (a[i - 1] != a[i]) {
                f = 0; break;
            }
        }
        if (f) {
            cout << 1 << endl;
            while (n--) cout << "1 ";
            cout << endl;
            continue;
        }

        f = 0;
        for (int i = 1; i <= n; ++i) {
            if (a[i - 1] == a[i]) {
                f = i; break;
            }
        }
        if (!f && (n & 1)) {
            cout << 3 << endl;
            for (int i = 0; i < n - 1; ++i) cout << i % 2 + 1 << ' ';
            cout << 3 << endl;
            continue;
        }
        cout << 2 << endl;
        if (n % 2 == 0) {
            for (int i = 0; i < n; ++i) cout << i % 2 + 1 << ' ';
        } else {
            for (int i = 0; i < f; ++i) cout << i % 2 + 1 << ' ';
            for (int i = f; i < n; ++i) cout << 2 - i % 2 << ' ';
        }
        cout << endl;
    }
    return 0;
}

1238E Tree Queries

一个有$n$个点以$1$为根的树，每次询问问$k$个点，是否有一条从根到某个节点$u$的路径，使得每个点距离这条路$≤1$。

做法很多，我这里是找出深度最深的点，和其他询问点求出$LCA$，其他点和对应的$LCA$深度差$≤1$。
$O(q\log n)$

E.cpp
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
#include <bits/stdc++.h>
 
#define endl '\n'
using namespace std;
 
const int N = 2e5 + 5;
 
int fa[N][22], dpt[N], n;
vector<int> g[N];
 
void init() {
    for (int i = 1; i < 20; ++i) {
        for (int j = 1; j <= n; ++j) {
            fa[j][i] = fa[fa[j][i - 1]][i - 1];
        }
    }
}
 
int lca(int a, int b) {
    if (dpt[a] < dpt[b]) {
        swap(a, b);
    }
    for (int i = 20; i >= 0; --i) {
        while (dpt[a] - (1 << i) >= dpt[b])
            a = fa[a][i];
    }
    for (int i = 20; i >= 0; --i) {
        while (fa[a][i] != fa[b][i]) {
            a = fa[a][i];
            b = fa[b][i];
        }
    }
    if (a == b)
        return a;
    return fa[a][0];
}
 
void dfs(int u = 1, int pre = 0) {
    fa[u][0] = pre;
    dpt[u] = dpt[pre] + 1;
    for (int &v : g[u]) {
        if (v == pre) continue;
        dfs(v, u);
    }
}
 
int main() {
    int q;
    cin >> n >> q;
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs();
    init();
    vector<int> v;
    int k;
    while (q--) {
        cin >> k;
        v.resize(k);
        int mi = 1;
        for (int i = 0; i < k; ++i) {
            cin >> v[i];
            if (dpt[v[i]] > dpt[mi]) mi = v[i];
        }
 
        int f = 1;
        for (int i = 0; i < k; ++i) {
            if (dpt[v[i]] - dpt[lca(mi, v[i])] > 1) {
                f = 0; break;
            }
        }
        if (f)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

1238F Make k Equal

一个长为$n$的数列，每次可以选择一个最大值$-1$，或选一个最小值$+1$，问最少操作几次可以让$k$个数相等。

首先最后相等的值是数列里的值，那么枚举这些值，比较从小操作，从大操作，两边操作的答案取最小就好了$($竟然$2400$这分也飘的太远了$)$。$O(n\log n)$

F.cpp
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
#include <bits/stdc++.h>
 
#define endl '\n'
using namespace std;
 
const int N = 2e5 + 5;
 
ll a[N];
ll pre[N], suf[N];
map<int, int> mp;
 
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        ++mp[a[i]];
        if (mp[a[i]] == k) {
            cout << 0 << endl;
            return 0;
        }
    }
    ll ans = INF64, lcnt = 0, rcnt = n;
    sort(a, a + n + 1);
    n = unique(a, a + n + 1) - a;
 
    for (int i = 1; i < n; ++i) {
        pre[i] = pre[i - 1] + mp[a[i - 1]] * a[i - 1];
    }
    for (int i = n - 2; i > 0; --i) {
        suf[i] = suf[i + 1] + mp[a[i + 1]] * a[i + 1];
    }
    for (int i = 1; i < n; ++i) {
        ll t = k - mp[a[i]];
        rcnt -= mp[a[i]];
        ll t1 = lcnt * a[i] - pre[i];
        ll t2 = suf[i] - rcnt * a[i];
        if (lcnt >= t) ans = min(ans, t1 - (lcnt - t));
        if (rcnt >= t) ans = min(ans, t2 - (rcnt - t));
        ans = min(ans, t1 + t2 - (lcnt + rcnt - t));
        lcnt += mp[a[i]];
    }
    cout << ans << endl;
    return 0;
}