AtCoder Beginner Contest 380 (Virtual Participation)#

烂完了，读假又什么都不会呜呜呜。

要被自己菜哭了。

A - 133233#

很简单的签到。随便统计一下即可。

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> v(10, 0);
10
    while (n) {
11
        int x = n % 10; n /= 10;
12
        if (x == 1) ++ v[1];
13
        if (x == 2) ++ v[2];
14
        if (x == 3) ++ v[3];
15
    }
16
    if (v[1] == 1 && v[2] == 2 && v[3] == 3) cout << "Yes" << char(10);
17
    else cout << "No" << char(10);
18
}
19

20
signed main() {
21
    cin.tie(nullptr)->sync_with_stdio(false);
22
    int T; T = 1;
23
    while (T--) solve();
24
    return 0;
25
}

B - Hurdle Parsing#

签到 +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
    string str; getline(cin, str);
9
    vector<int> ans;
10
    for (auto it : str) {
11
        if (it == '|') ans.push_back(0);
12
        if (it == '-') ++ans.back();
13
    }
14
    rep (i, 0, ans.size() - 2)
15
        cout << ans[i] << " \n"[i == int(ans.size()) - 2];
16
}
17

18
signed main() {
19
    cin.tie(nullptr)->sync_with_stdio(false);
20
    int T; T = 1;
21
    while (T--) solve();
22
    return 0;
23
}

C - Move Segment#

有点讨厌的模拟。主要是 $1$ 子段的截取需要一点判断。

将所有 $1$ 子段的区间截取出来，然后调整其中的 $K$ 到 $K - 1$ 的后面即可。

时间复杂度 $\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
using pii = pair<int, int>;
8

9
inline void solve() {
10
    int n, k; cin >> n >> k;
11
    string str; cin >> str;
12
    vector<pii> blk;
13
    [&]() {
14
        pii tmp; bool flg = false;
15
        rep (i, 0, n - 1) {
16
            if (i == 0) {
17
                if (str[0] == '1') { tmp.first = 1; flg = 1; }
18
                continue;
19
            }
20
            if (str[i] == '0') {
21
                if (str[i - 1] == '1') {
22
                    tmp.second = i; flg = 0;
23
                    blk.push_back(tmp); tmp = {0, 0};
24
                }
25
            }
26
            if (str[i] == '1') {
27
                if (str[i - 1] == '0') { tmp.first = i + 1; flg = 1; }
28
            }
29
        }
30
        if (flg == 1 && str.back() == '1') {
31
            tmp.second = n; blk.push_back(tmp);
32
        }
33
    }();
34
    int len = blk[k - 1].second - blk[k - 1].first;
35
    blk[k - 1].first = blk[k - 2].second + 1;
36
    blk[k - 1].second = blk[k - 1].first + len;
37
    fill(str.begin(), str.end(), '0');
38
    for (auto &it : blk)
39
        fill(str.begin() + it.first - 1, str.begin() + it.second, '1');
40
    cout << str << char(10);
41
}
42

43
signed main() {
44
    cin.tie(nullptr)->sync_with_stdio(false);
45

46
    int T; T = 1;
47
    while (T--) solve();
48
    return 0;
49
}

D - Strange Mirroring#

注意到 $K_i$ 的范围很大，故而肯定考虑类似 $2$ 的次幂相关的化归。

不妨先观察最终串的组成，写出前几项

STTSTSST\ldots

不难发现，在 $1 \sim 2^n$ 的范围中， $1 \sim 2^{n - 1}$ 和 $2^{n - 1} + 1 \sim 2^n$ 应该是互反的。

所以可以考虑如下算法：

对于当前的位置 $p$ 所在串，通过不断减去 $2^{\lfloor \log_2{p} \rfloor}$ ，记录减去后的反转情况，可以最终规约到串 $S$ 以及是否需要翻转。

由于该题时限猜测一定不会太严，并且不高兴操心 $long\space long$ 溢出问题，故代码中存在 define int long long 之流的恶习，请不要随意模仿。

代码如下：

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

3
using namespace std;
4

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

8
inline void solve() {
9
    string s; cin >> s;
10
    int q; cin >> q;
11
    while (q--) {
12
        int k; cin >> k;
13
        int val = ((k-- + s.size() - 1) / s.size());
14
        bool flg = false;
15
        while (val > 1) {
16
            int tmp = (1ll << (long long)(__lg(val - 1)));
17
            val -= tmp;
18
            k -= tmp * s.size();
19
            flg ^= 1;
20
        }
21
        if (!flg) cout << s[k] << ' ';
22
        else {
23
            if (s[k] >= 97) cout << char(s[k] - 97 + 65) << ' ';
24
            else cout << char(s[k] - 65 + 97) << ' ';
25
        }
26
    }
27
}
28

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

32
    int T; T = 1;
33
    while (T--) solve();
34
    return 0;
35
}

E - 1D Bucket Tool#

额啊

我是冰茶姬实现低手 QwQ

赛时想到冰茶姬了，但是一度写错加读错题意 (size 函数返回 int 的笨比)，所以小寄一波。

实际上这题个人觉得比较自然的想法是，使用类似珂朵莉树存放区间的方法，进行类似的合并和删除，实际上速度还挺快的（？

在这里放出两种不同的写法，感觉是加强了类似区间处理的一些想法。

Notice: 本段代码中 dsu 的 merge 函数非标准实现。珂朵莉树的节点定义中的 $operator<$ 重载需要加上两个 $const$ ，不然容易报神必错误。

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
struct Node {
8
    int l, r;
9
    mutable int v;
10
    Node(int l_, int r_ = -1, int v_ = 0) : l(l_), r(r_), v(v_) {};
11
    bool operator < (const Node &o) const { return l < o.l; }
12
};
13

14
inline void solve() {
15
    int n, q; cin >> n >> q;
16
    set<Node> s;
17
    rep (i, 1, n) { s.insert(Node(i, i, i)); }
18
    vector<int> cnt(n + 10, 1);
19
    while (q--) {
20
        int opt; cin >> opt;
21
        if (opt == 1) {
22
            int x, c; cin >> x >> c;
23
            auto it = s.lower_bound(Node(x, x, 0));
24
            if (it->l != x) --it;
25
            auto &[l, r, v] = *it;
26
            cnt[v] -= r - l + 1; v = c; cnt[c] += r - l + 1;
27
            bool flg1 = false, flg2 = false;
28
            if (it != s.begin() && prev(it)->v == c) flg1 = true;
29
            if (next(it) != s.end() && next(it)->v == c) flg2 = true;
30
            if (flg1 || flg2) {
31
                int nl = l, nr = r, nv = c;
32
                if (flg1) { nl = prev(it)->l; s.erase(prev(it)); }
33
                if (flg2) { nr = next(it)->r; s.erase(next(it)); }
34
                s.erase(it); s.insert(Node(nl, nr, nv));
35
            }
36
        }
37
        if (opt == 2) {
38
            int c; cin >> c;
39
            cout << cnt[c] << char(10);
40
        }
41
    }
42
}
43

44
signed main() {
45
    cin.tie(nullptr)->sync_with_stdio(false);
46

47
    int T; T = 1;
48
    while (T--) solve();
49
    return 0;
50
}

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, q; cin >> n >> q;
9
    vector<int> fa(n + 10), siz(n + 10, 1);
10
    vector<int> cnt(n + 10, 1);
11
    vector<int> l(n + 10), r(n + 10), c(n + 10);
12
    iota(fa.begin(), fa.end(), 0);
13
    rep (i, 1, n) l[i] = r[i] = c[i] = i;
14

15
    auto find = [&](this auto&& find, int x) -> int {
16
        return fa[x] == x ? x : fa[x] = find(fa[x]);
17
    };
18
    auto merge = [&](int x, int y) {
19
        if (siz[x] < siz[y]) swap(x, y);
20
        siz[x] += siz[y];
21
        l[x] = min(l[x], l[y]);
22
        r[x] = max(r[x], r[y]);
23
        fa[y] = x;
24
    };
25

26
    while (q--) {
27
        int opt; cin >> opt;
28
        if (opt == 1) {
29
            int x, c_; cin >> x >> c_;
30
            int f = find(x);
31
            cnt[c[f]] -= r[f] - l[f] + 1;
32
            c[f] = c_;
33
            cnt[c_] += r[f] - l[f] + 1;
34
            if (l[f] != 1) {
35
                int f_ = find(l[f] - 1);
36
                if (c[f_] == c_) merge(f, f_);
37
            }
38
            if (r[f] != n) {
39
                int f_ = find(r[f] + 1);
40
                if (c[f_] == c_) merge(f, f_);
41
            }
42
        }
43
        if (opt == 2) {
44
            int c_; cin >> c_;
45
            cout << cnt[c_] << char(10);
46
        }
47
    }
48
}
49

50
signed main() {
51
    cin.tie(nullptr)->sync_with_stdio(false);
52

53
    int T; T = 1;
54
    while (T--) solve();
55
    return 0;
56
}