Lotuses's Blog

2022-10-23 总结

  • ~10.62K 字
  1. 1. 总结
    1. 1.1. Codeforces Round 829 (div.2)
      1. 1.1.1. A. Technical Support
      2. 1.1.2. B. Kevin and Permutation
      3. 1.1.3. C1. Make Nonzero Sum (easy version)
      4. 1.1.4. C2. Make Nonzero Sum (hard version)
      5. 1.1.5. D. Factorial Divisibility

总结

2022/10/20~2022/10/23

书接上回，

Codeforces 阳间比赛只打了一场。

比赛的情况还不错。AC A~D

在此总结一下做法。

Codeforces Round 829 (div.2)

A. Technical Support

大概是说，要求每个 Q 之后都要有一个对应的 A。

一个 A 不能被两个 Q 所对应。

看是否能够满足这个条件。

那么可以从后往前扫，如果出现 totQ（Q 与 A 之差）< 0 的情况就会爆炸。

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
// Copyright 2022 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

#define gc getchar()
template<typename T>
void read(T &r) { // NOLINT
    r = 0; static char ch, last; // NOLINT
    ch = gc, last = 'z';
    while (ch < '0' || ch > '9') last = ch, ch = gc;
    while (ch >= '0' && ch <= '9') r = (r << 1) + (r << 3) + (ch ^ 48), ch = gc;
    r = (last == '-') ? -r : r;
}

template<typename T, typename...Ts>
void read(T &arg, Ts&...arg_left) { // NOLINT
    read(arg);
    read(arg_left...);
}

char ch[114514];

int main() {
    int T;
    read(T);
    while (T--) {
        int n, t = 0;
        read(n);
        scanf("%s", ch);
        for (int i = n - 1; i >= 0; i--) {
            if (ch[i] == 'Q') {
                t--;
                if (t < 0) break;
            } else {
                t++;
            }
        }
        if (t < 0) {
            puts("No");
        } else {
            puts("Yes");
        }
    }
    return 0;
}

B. Kevin and Permutation

大概是说，有一个序列 ，要最大化 。那么观察样例 1 即可发现可以通过 来构造出 的方案。

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
// Copyright 2022 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

#define gc getchar()
template<typename T>
void read(T &r) { // NOLINT
    r = 0; static char ch, last; // NOLINT
    ch = gc, last = 'z';
    while (ch < '0' || ch > '9') last = ch, ch = gc;
    while (ch >= '0' && ch <= '9') r = (r << 1) + (r << 3) + (ch ^ 48), ch = gc;
    r = (last == '-') ? -r : r;
}

template<typename T, typename...Ts>
void read(T &arg, Ts&...arg_left) { // NOLINT
    read(arg);
    read(arg_left...);
}

int main() {
    int T;
    read(T);
    while (T--) {
        int n;
        read(n);
        int l = n / 2, r = n;
        if (n % 2)
            l++;
        for (int i = 0; i < n / 2; i++) {
            printf("%d %d ", l, r);
            l--, r--;
        }
        if (n % 2) {
            printf("%d\n", 1);
        }
    }
    return 0;
}

C1. Make Nonzero Sum (easy version)

大概意思，就是有一列数 ，包含 两种值，要选出任意个区间使得这些区间 不重复不遗漏有顺序 的覆盖整个数列，使得对于每个区间的得分之和为 。定义区间 的得分为 即题面所说的 “the alternating sum of all elements of the -th segment”（即交替和——字面理解）。

考虑只有 和 两种值，那么无论如何改变 的符号，如果 ，最终加和必然是奇数，不满足所有区间得分和为 的条件。所以当 时必然无解。

那么考虑 时，如果让每一个区间和为 ，那么必然能让 （话说题面有隐晦地提到：“Note that each does not have to be equal to zero（注意每一个 可以不为 ）, this property is about sum of over all segments of partition.”）。

所以只要让每一组相邻的数构成一个字串来处理，

当 时，可以让区间包括这两个数，可以使一个数的符号变过来，然后相抵消。

当 时，可以单独把这两个数分成两个区间单独相加（因为这样不改变符号），然后相抵消。

到最后就能全部抵消完。。

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
// Copyright 2022 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

#define gc getchar()
template<typename T>
void read(T &r) { // NOLINT
    r = 0; static char ch, last; // NOLINT
    ch = gc, last = 'z';
    while (ch < '0' || ch > '9') last = ch, ch = gc;
    while (ch >= '0' && ch <= '9') r = (r << 1) + (r << 3) + (ch ^ 48), ch = gc;
    r = (last == '-') ? -r : r;
}

template<typename T, typename...Ts>
void read(T &arg, Ts&...arg_left) { // NOLINT
    read(arg);
    read(arg_left...);
}

int a[200005];
std::vector<std::pair<int, int> > ans;

int main() {
    int T;
    read(T);
    while (T--) {
        int n;
        read(n);
        for (int i = 0; i < n; i++) {
            read(a[i]);
        }

        if (n % 2) {
            puts("-1");
            continue;
        }


        ans.clear();
        for (int i = 0; i < n / 2; i++) {
            if (a[i * 2] == a[i * 2 + 1]) {
                ans.push_back(std::make_pair(i * 2 + 1, i * 2 + 2));
            } else {
                ans.push_back(std::make_pair(i * 2 + 1, i * 2 + 1));
                ans.push_back(std::make_pair(i * 2 + 2, i * 2 + 2));
            }
        }
        printf("%d\n", ans.size());
        for (auto q : ans) {
            printf("%d %d\n", q.first, q.second);
        }
    }
    return 0;
}

C2. Make Nonzero Sum (hard version)

与 C1 不同的是，这里的 可能出现 。如果采取刚才的策略， 将有可能打乱节奏，使得 与 （ 下一个不为 的数）在区间的同奇偶位上。比如说 101 的情况，按照上面的策略将会使得两个 直接相加，打乱节奏。

但是注意到 作为一个空数，他可以起到过渡作用。

首先有一个结论，非 数个数为奇数必为 -1。（理由同理）

那么现在就考虑让所有非 数个数为偶数的情况都有解。

想到可以与上一道题类似的做法，两两相抵消。但是有部分过程会稍有区别。

若 ，这种情况比较简单。对于上一道题来说，这两个数可以分别取，然后相互抵消。但是中间可能参杂 ，由于 不会影响到结果，所以可以把所有 放在一起统一抵消（或者你想单独给他们分组也行）。那么再分别取即可。

若 ，对于上一道题来说，这两个要放在同一子序列中相互抵消。但是有个问题。如果中间参杂了 ，可能会影响到互相抵消。那么可以想到一种构造方法：101 -> 1|01 这样分组分配，让最后一个 与后面的非 数相抵消，那么必然有解。再比如 1000001 -> 100000|01，前面 为正不变符号，后面 在第二个数字上，变号，那么就可以相互抵消了。

那么，

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
98
99
// Copyright 2022 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

#define gc getchar()
template<typename T>
void read(T &r) { // NOLINT
    r = 0; static char ch, last; // NOLINT
    ch = gc, last = 'z';
    while (ch < '0' || ch > '9') last = ch, ch = gc;
    while (ch >= '0' && ch <= '9') r = (r << 1) + (r << 3) + (ch ^ 48), ch = gc;
    r = (last == '-') ? -r : r;
}

template<typename T, typename...Ts>
void read(T &arg, Ts&...arg_left) { // NOLINT
    read(arg);
    read(arg_left...);
}

int a[200005],
    ac[200005],
    id[200005];
std::vector<std::pair<int, int> > ans;

int main() {
    int T;
    read(T);
    while (T--) {
        int n, cnt = 0;
        read(n);
        for (int i = 0; i < n; i++) {
            read(a[i]);
            cnt += a[i] == 0;
        }

        if ((n - cnt) % 2) {
            puts("-1");
            continue;
        }

        int lcnt = n - cnt;
        for (int i = n - 1; i >= 0; i--) {
            if (a[i] != 0) {
                lcnt--;
                id[lcnt] = i;
                ac[lcnt] = a[i];
            }
        }

        if (cnt == n) {
            puts("1");
            printf("%d %d\n", 1, n);
            continue;
        }

        n -= cnt;
        ans.clear();
        if (1 <= id[0]) {
            ans.push_back(std::make_pair(1, id[0]));
        }
        for (int i = 0; i < n / 2; i++) {
            if (ac[i * 2] == ac[i * 2 + 1]) {
                if (id[i * 2] + 1 == id[i * 2 + 1]) {
                    ans.push_back(std::make_pair(id[i * 2] + 1, id[i * 2 + 1] + 1));
                } else {
                    ans.push_back(std::make_pair(id[i * 2] + 1, id[i * 2 + 1] - 1));
                    ans.push_back(std::make_pair(id[i * 2 + 1], id[i * 2 + 1] + 1));
                }
            } else {
                if (id[i * 2] + 1 == id[i * 2 + 1]) {
                    ans.push_back(std::make_pair(id[i * 2] + 1, id[i * 2] + 1));
                    ans.push_back(std::make_pair(id[i * 2 + 1] + 1, id[i * 2 + 1] + 1));
                } else {
                    ans.push_back(std::make_pair(id[i * 2] + 1, id[i * 2] + 1));
                    ans.push_back(std::make_pair(id[i * 2] + 2, id[i * 2 + 1]));
                    ans.push_back(std::make_pair(id[i * 2 + 1] + 1, id[i * 2 + 1] + 1));
                }
            }
            if (i != n / 2 - 1) {
                if (id[i * 2 + 1] + 2 <= id[i * 2 + 2]) {
                    ans.push_back(std::make_pair(id[i * 2 + 1] + 2, id[i * 2 + 2]));
                }
            } else {
                if (id[i * 2 + 1] + 2 <= n + cnt) {
                    ans.push_back(std::make_pair(id[i * 2 + 1] + 2, n + cnt));
                }
            }
        }
        printf("%d\n", ans.size());
        for (auto q : ans) {
            printf("%d %d\n", q.first, q.second);
        }
    }
    return 0;
}

// 2022/10/23 16:36 : I think i make a wrong thought! （后期：来自赛场上的不自信）

D. Factorial Divisibility

如题所名，这道题分析阶乘的整除性质。

有数列 ，要判断 是否是 的因数。

那么可以想到一个很明显的结论：对于 的数可以不用考虑，因为本身就有了 的因数。

然后根据玄学的思考，其他的 可以相互合并获得 。比如说 其中的规律是 。所以通过一次次的合并可以合并到 就不用再合并了。

在合并的过程中如果出现剩余的情况，那么说明该组数据不能整除：因为剩下的 ，必然不是倍数关系。无论如何必须都要全部组合在一起才能说明是 ok 的。

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
// Copyright 2022 Lotuses
#include <cstdio>
#include <cstring>
#include <vector>

#define gc getchar()
template<typename T>
void read(T &r) { // NOLINT
    r = 0; static char ch, last; // NOLINT
    ch = gc, last = 'z';
    while (ch < '0' || ch > '9') last = ch, ch = gc;
    while (ch >= '0' && ch <= '9') r = (r << 1) + (r << 3) + (ch ^ 48), ch = gc;
    r = (last == '-') ? -r : r;
}

template<typename T, typename...Ts>
void read(T &arg, Ts&...arg_left) { // NOLINT
    read(arg);
    read(arg_left...);
}

int a[500005];

int main() {
    int n, x, k;
    read(n, x);

    for (int i = 0; i < n; i++) {
        read(k);
        a[k]++;
    }

    for (int i = 1; i < x; i++) {
        if (a[i] % (i + 1) != 0) {
            puts("No");
            return 0;
        } else {
            a[i + 1] += a[i] / (i + 1);
        }
    }

    puts("Yes");
    return 0;
}

以上是 Codeforces 的分析。

吐槽 Luogu S 模拟赛。

由于早于 Codeforces 1.5h，我思考了第一题并成功的想出了逆序对的做法——即要求为 ，的两颗导弹就会碰撞。

但是做到 15:00 就没有打了。T1 也没实现（否定了自己）。有些小遗憾，这次模拟赛如果打满暴力将可以冲进前 50。但是没关系， Codeforces 有进步！

这里是 T1 的部分实现代码

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
int p[1000001];
int bf[1000001];
int ans[1000001];
int id[1000001];
int idb[1000001];

void merge_sort(int l, int r) {
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);

    int i = l, j = mid + 1, len = 0;
    while (i <= mid && j <= r) {
        if (p[i] <= p[j])
            bf[len++] = p[i++];
        else
            ans[id[j]] += (mid - i + 1), idb[len] = id[j], bf[len++] = p[j++];
    }
    while (i <= mid)
        idb[len] = id[i], bf[len++] = p[i++];
    while (j <= r)
        idb[len] = id[j], bf[len++] = p[j++];

    for (int k = l; k <= r; k++)
        p[k] = bf[k - l], id[k] = idb[k - l];
}

signed main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        id[i] = i;
    }
    merge_sort(1, n);
    for (int i = 1; i <= n; i++)
        cout << ans[i] << ' ';
    return 0;
}

已经实现了记录是哪一个位置上的导弹提供的贡献。但是遗憾没有继续做下去。

先逃——

由于疫情，停课了，三天啊

三天啊

而且中段考有可能后移导致我也得参加，这样我亏死啦

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可