1
2
3
4
5
6
7
8
9
10

void solve() {
    int _;
    cin >> _;
    for (int tss = 0; tss < _; ++tss) {
        int a, b, c;
        cin >> a >> b >> c;
        int m = min(a - 1, b + c);
        cout << m * 2 + 1 << endl;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void solve() {
    int _;
    cin >> _;
    for (int tss = 0; tss < _; ++tss) {
        int n, k;
        cin >> n >> k;
        map<int, vector<int>> res;
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            tmp %= k;
            res[tmp].push_back(i);
        }
        auto zero = res[0];
        for (auto i : zero) cout << i + 1 << ' ';
        for (auto iter = res.rbegin(); iter != res.rend(); ++iter) {
            if (iter->first == 0) continue;
            for (auto i : iter->second) cout << i + 1 << ' ';
        }
        cout << endl;
    }
}

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

void solve() {
    int _;
    cin >> _;
    vector<int> pw1(2e5 + 10);
    vector<int> pw2(2e5 + 10);
    int tmp1 = 1;
    int tmp2 = 1;
    int mod = 998244353;
    for (int i = 1; i < pw1.size(); ++i) {
        pw1[i] = (pw1[i - 1] + tmp1) % mod;
        tmp1 *= 131;
        tmp1 %= mod;
        pw2[i] = (pw2[i - 1] + tmp2) % mod;
        tmp2 *= 1331;
        tmp2 %= mod;
    }
    for (int ts = 0; ts < _; ++ts) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n + 1), b1(n + 1), b2(n + 1);
        string str(n, '0');
        cin >> str;
        tmp1 = 1;
        tmp2 = 1;
        for (int i = 0; i < n; ++i) {
            a[i + 1] = a[i] + str[i] - '0';
            b1[i + 1] = (b1[i] + (str[i] == '1' ? tmp1 : 0)) % mod;
            tmp1 *= 131;
            tmp1 %= mod;
            a[i + 1] = a[i] + str[i] - '0';
            b2[i + 1] = (b2[i] + (str[i] == '1' ? tmp2 : 0)) % mod;
            tmp2 *= 1331;
            tmp2 %= mod;
        }
        set<pair<int, int>> res;
        for (int i = 0; i < k; ++i) {
            int l, r;
            cin >> l >> r;
            int ls, rs;
            {
                int left = b1[l - 1] % mod;
                int right = (b1[n] - b1[r] + mod) % mod;
                int one = a[r] - a[l - 1];
                int zero = r - l + 1 - one;
                int from = l + zero, to = r;
                int mid = (pw1[to] - pw1[from - 1] + mod) % mod;
                ls = (left + right + mid) % mod;
            }
            {
                int left = b2[l - 1] % mod;
                int right = (b2[n] - b2[r] + mod) % mod;
                int one = a[r] - a[l - 1];
                int zero = r - l + 1 - one;
                int from = l + zero, to = r;
                int mid = (pw2[to] - pw2[from - 1] + mod) % mod;
                rs = (left + right + mid) % mod;
            }
            res.insert({ls, rs});
        }
        cout << res.size() << endl;
    }
}

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

void solve() {
    int n;
    cin >> n;
    vector<int> data(n);
    vector<bool> vis(n, false);
    int res = 0;
    for (int i = 0; i < n; ++i) cin >> data[i];
    // 先处理 2 的情况
    for (int i = 0; i < n; ++i) {
        if (vis[i] || data[i] != 2) continue;
        res++;
        vis[i] = true;
        for (int j = i - 1; j >= 0; --j) {
            if (!vis[j]) {
                vis[j] = true;
                if (data[j] == 0) break;
            } else break;
        }
        for (; i < n; ++i) {
            vis[i] = true;
            if (data[i] == 0) break;
        }
    }
    // 再处理 1 的情况
    int last = -1;
    int zero = 0;
    int oneP = 0;
    for (int i = 0; i < n; ++i) {
        if (vis[i]) {
            res += max(oneP, zero);
            zero = 0;
            oneP = 0;
            last = -1;
        } else if (data[i] == 0) {
            zero++;
            last = 0;
        } else if (last != 1) {
            last = 1;
            oneP++;
        }
    }
    res += max(oneP, zero);
    cout << res << endl;
}