Codeforces Round 665 Div2

发表于2020-10-01更新于2023-09-15字数统计2.8k阅读时长30分

比赛链接

A Distance and Axis

Solution

列出式子把绝对值拆开分类讨论即可。

Code

Distance and Axis
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 2e5 + 5, MOD = 1e9 + 7;

int tc, n, m;
array<int, MAXN> a;

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> tc;
    while (tc--) {
        int n, k;
        cin >> n >> k;
        if ((n + k) % 2 == 0 && n >= k) cout << 0 << "\n";
        else if (n < k) {
            cout << k - n << "\n";
        } else {
            cout << 1 << "\n";
        }
    }
    return 0;
}

B Ternary Sequence

考虑 aa 序列，aa 的 2 优先和 bb 的 1 匹配，若有剩余再和 bb 的 2 匹配。然后 2 和 0， 0 和 2 匹配。最后只能 2 和 1 匹配。

Ternary Sequence
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
#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
constexpr int MAXN = 2e5 + 5, MOD = 1e9 + 7;
 
int tc, n, m, x[2], y[2], z[2];
 
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> tc;
    while (tc--) {
        int ans = 0;
        cin >> x[0] >> y[0] >> z[0];
        cin >> x[1] >> y[1] >> z[1];
        int tmp = min(z[0], y[1]); //2 1
        ans += 2LL * tmp;
 
        z[0] -= tmp, y[1] -= tmp; // 2 2
        tmp = min(z[0], z[1]);
        z[0] -= tmp, z[1] -= tmp;
 
        tmp = min(z[0], x[1]); //2 0
        z[0] -= tmp, x[1] -= tmp;
 
        tmp = min(z[1], x[0]); //0 2
        z[1] -= tmp, x[0] -= tmp;
 
        tmp = min(z[0], y[1]);
        ans -= 2LL * tmp;
 
        tmp = min(z[1], y[0]);
        ans -= 2LL * tmp;
    
        cout << ans << "\n";
    }
    return 0;
}

C Mere Array

Solution

设最小值为 mimi，则一定可以通过 mimi 让 mimi 的倍数排成有序的。把 mimi 的倍数先取出排序，再放回原序列，再判断整个序列是否升序。

Code

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

using namespace std;

constexpr int MAXN = 2e5 + 5, MOD = 1e9 + 7;

int tc, n, m;
array<int, MAXN> a, to;

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> tc;
    while (tc--) {
        cin >> n;
        int mi = 0x3f3f3f3f;
        vector<int> tmp;
        for (int i = 1; i <= n; i++) cin >> a[i], mi = min(mi, a[i]);
        if (n == 1) cout << "YES\n";
        else {
            for (int i = 1; i <= n; i++)
                if (a[i] % mi == 0) tmp.push_back(a[i]), a[i] = 0;
            sort(tmp.begin(), tmp.end());

            int id = 0;
            for (int i = 1; i <= n; i++)
                if (a[i] == 0) a[i] = tmp[id++];

            bool judge = true;
            for (int i = 1; i <= n; i++)
                if (a[i] < a[i - 1]) judge = false;

            judge ? cout << "YES\n" : cout << "NO\n";
        }
    }
    return 0;
}

D Maximum Distributed Tree

Solution

首先对于一条边，它会被计算两端的子树大小的乘积次。要让答案最大，那么被计算次数最多的边的边权应为最大的约数，依此类推。注意如果质因数个数超过 n−1n - 1，则将最大的几个质因子乘起来，分配给被计算最多的边。

Code

Maximum Distributed Tree
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
#include <bits/stdc++.h>
#define int long long

using namespace std;

constexpr int MAXN = 1e5 + 5, MOD = 1e9 + 7;

int tc, n, m;
vector<int> G[MAXN], cnt;
array<int, MAXN> w, sz;

void dfs(int cur, int fa) {
    sz[cur] = 1;
    for (auto& to : G[cur]) {
        if (to == fa) continue;
        dfs(to, cur);
        sz[cur] += sz[to];
    }
    cnt.push_back(sz[cur] * (n - sz[cur]));
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> tc;
    while (tc--) {
        cin >> n;
        for (int i = 1; i <= n; i++) G[i].clear();
        cnt.clear();
        for (int i = 1, u, v; i < n; i++) {
            cin >> u >> v;
            G[u].push_back(v), G[v].push_back(u);
        }
        cin >> m;
        for (int i = 1; i <= m; i++) cin >> w[i];
        for (int i = m + 1; i <= n - 1; i++) w[i] = 1;
        sort(w.begin() + 1, w.begin() + max(n, m + 1)), reverse(w.begin() + 1, w.begin() + max(m + 1, n));
        dfs(1, 0);
        sort(cnt.begin(), cnt.end()), reverse(cnt.begin(), cnt.end());
        int ans = 0;
        if (n - 1 >= m) {
            for (int i = 0; i < n - 1; i++)
                (ans += cnt[i] % MOD * w[i + 1] % MOD) %= MOD;
        }
        else {
            for (int i = 1; i < n - 1; i++) {
                (ans += cnt[i] % MOD * w[m - n + 2 + i] % MOD) %= MOD;
            }
            int tmp = 1;
            for (int i = 1; i <= m - n + 2; i++)
                (tmp *= w[i]) %= MOD;
            (ans += tmp * cnt[0] % MOD) %= MOD;
        }
        cout << ans << "\n";
    }
    return 0;
}

E Divide Square

Solution

有两种情况会使答案加一：贯穿整个矩形的直线，或两条直线相交。

求直线交点：可以将水平线段按左端点排序，左端点相同按右端点排序。并将竖直线段的 xx 坐标也加入，若 xx 坐标与水平线段左端点相同，优先考虑水平线段。

统计交点数：可以通过树状数组对 yy 进行区间 [yl,yr][y_l, y_r] 查询，加入或删除水平线则对水平线的 yy 单点修改。

加入或删除水平线可通过队列实现，如果右端点小于当前竖直线的 xx，则出队，并通过树状数组对 yy 进行单点修改。

注意：树状数组不是 0 based 的，需将坐标都加 1。

Code

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

using namespace std;
using LL = long long;

constexpr int MAXN = 1e6 + 6, MOD = 1e9 + 7, MAXZ = 1e5 + 5;

int n, m, tmp[MAXZ], y[MAXZ], l1[MAXZ], r1[MAXZ], x[MAXZ], l2[MAXZ], r2[MAXZ];
LL ans(1);

struct BIT {
    int lowbit(int x) { return x & (-x); }

    void add(int x, LL val) {
        while (x < MAXN) c[x] += val, x += lowbit(x);
    }

    LL query(int x, int res = 0) {
        while (x) res += c[x], x -= lowbit(x);
        return res;
    }
    array<LL, MAXN> c;
} bit[3];
/*range [l, r] add val*/
inline void add(int l, int r, LL val) {
    bit[1].add(l, val), bit[1].add(r + 1, -val);
    bit[2].add(l, val * l), bit[2].add(r + 1, -val * (r + 1));
}
/*range [l, r] sum query*/
inline LL query(int l, int r, LL res = 0) {
    res = bit[0].query(r) + bit[1].query(r) * (r + 1) - bit[2].query(r);
    res -= bit[0].query(l - 1) + bit[1].query(l - 1) * l - bit[2].query(l - 1);
    return res;
}

struct Node {
    Node() = default;
    Node(int _type, int _l, int _r, int _x) :
        type(_type), l(_l), r(_r), x(_x) {}

    friend inline bool operator<(const Node& lhs, const Node& rhs) {
        if (lhs.l == rhs.l) {
            if (lhs.type == rhs.type) return lhs.r < rhs.r;
            return lhs.type < rhs.type; 
        }
        return lhs.l < rhs.l;
    }

    int type, l, r, x; //type == 0 horizontal ==1 vertical
};
vector<Node> vec;

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> y[i] >> l1[i] >> r1[i];
        y[i]++, l1[i]++, r1[i]++;
        if (l1[i] == 1 && r1[i] == 1000001) ans++;
        vec.emplace_back(0, l1[i], r1[i], y[i]);
    }
    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> l2[i] >> r2[i];
        x[i]++, l2[i]++, r2[i]++;
        if (l2[i] == 1 && r2[i] == 1000001) ans++;
        vec.emplace_back(1, x[i], l2[i], r2[i]);
    }
    sort(vec.begin(), vec.end());
    queue<int> q;
    for (int i = 0; i < vec.size(); i++) {
        if (vec[i].type == 0) {
            add(vec[i].x, vec[i].x, 1);
            q.push(i);
        } else {
            while (!q.empty() && vec[q.front()].r < vec[i].l) {
                add(vec[q.front()].x, vec[q.front()].x, -1);
                q.pop();
            }
            ans += query(vec[i].r, vec[i].x);
        }
    }
    cout << ans << "\n";
    return 0;
}

F Reverse and Swap

Solution

考虑线段树维护，设线段树从上往下是第 0 层，第 1 层，第 2 层，…，第 n 层。那么 swap(k)swap(k) 操作就是给第 n−k+1n - k + 1 层所有节点打上交换标记，reverse(k)reverse(k) 操作就是给第 n−kn - k 到 nn 层的所有节点打上标记。

一种做法是用 tag[]tag[] 记录每一层的交换标记，然后每个节点也有一个 tagtag 标记，如果节点的 tagtag 和节点对应层的 tag[depth]tag[depth] 不同，则交换其左右儿子，并修改 tag。
注：当区间翻转的是一个整区间时才能用线段树交换左右儿子，其次结构体中不建议保存节点 l,rl, r 信息（不方便交换左右儿子，因为左右儿子的 l,rl, r 都要变），可以直接作为函数参数。

另一种做法是根据层标记确定往左二子还是右儿子走，同时计算变化后的区间。

Code

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

using namespace std;

constexpr int MAXN = 3e5 + 5, MOD = 1e9 + 7;

template<typename T>
inline void read(T& x, T f = 1, char ch = getchar()) {
    x = 0;
    while (!isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

int bit, n, q, a[MAXN], tag[19], tot;

struct SegTree {
    SegTree* lson, *rson;
    int tag, depth;
    long long sum;
} *root, tree[MAXN << 1];

inline void update(SegTree* root) {
    root->sum = root->lson->sum + root->rson->sum;
}

inline void build(SegTree*& root, int L, int R, int depth) {
    root = &tree[tot++], root->depth = depth;
    if (L == R) { root->sum = a[L]; return; }
    int mid = (L + R) >> 1;
    build(root->lson, L, mid, depth + 1);
    build(root->rson, mid + 1, R, depth + 1);
    update(root);
}

inline void checkTag(SegTree* root) {
    if (root->tag != tag[root->depth]) {
        root->tag = tag[root->depth];
        swap(root->lson, root->rson);
    }
}

inline void modify(SegTree* root, int pos, int val, int L = 1, int R = n) {
    if (L == pos && R == pos) {
        root->sum = val;
        return;
    }
    checkTag(root);
    int mid = (L + R) >> 1;
    if (pos <= mid) modify(root->lson, pos, val, L, mid);
    else modify(root->rson, pos, val, mid + 1, R);
    update(root);
}

inline long long query(SegTree* root, int l, int r, int L = 1, int R = n) {
    if (l <= L && R <= r) return root->sum;
    checkTag(root);
    int mid = (L + R) >> 1;
    long long res = 0;
    if (l <= mid) res += query(root->lson, l, r, L, mid);
    if (r > mid) res += query(root->rson, l, r, mid + 1, R);
    update(root);
    return res;
}

int main() {
    read(bit), read(q), n = pow(2, bit);
    for (int i = 1; i <= n; i++) read(a[i]);
    build(root, 1, n, 0);
    while (q--) {
        int opt, x, k, l, r;
        read(opt);
        if (opt == 1) read(x), read(k), modify(root, x, k);
        else if (opt == 2) {
            read(k);
            for (int i = bit - k; i <= bit; i++) tag[i] ^= 1;
        } else if (opt == 3) read(k), tag[bit - k - 1] ^= 1;
        else read(l), read(r), printf("%lld\n", query(root, l, r));
    }
    return 0;
}
Reverse and Swap method2
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
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int MAXN = 3E5;
int n, q, a[MAXN], x, k, l, r, tag[19];

template <class T>
void read(T& x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct Node {
    Node* son[2];
    int l, r;
    LL sum;
} * root;

void update(Node* cur) { cur->sum = cur->son[0]->sum + cur->son[1]->sum; }

void build(Node*& cur, int l, int r) {
    cur = new Node;
    cur->l = l, cur->r = r;
    if (l == r) {
        cur->sum = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(cur->son[0], l, mid);
    build(cur->son[1], mid + 1, r);
    update(cur);
}

void replace(Node* cur, int x, int val, int layer) {
    if (cur->l == x && cur->r == x) {
        cur->sum = val;
        return;
    }
    int mid = cur->l + cur->r >> 1;
    int st = tag[layer];
    int len = st ? (cur->r - cur->l + 1) >> 1 : 0;
    if (x <= mid)
        replace(cur->son[st], x + len, val, layer + 1);
    else
        replace(cur->son[!st], x - len, val, layer + 1);
    update(cur);
}

LL sum(Node* cur, int l, int r, int layer) {
    if (cur->l == l && cur->r == r) return cur->sum;
    int mid = cur->l + cur->r >> 1;
    int st = tag[layer];
    int len = st ? (cur->r - cur->l + 1) >> 1 : 0;

    if (r <= mid)
        return sum(cur->son[st], l + len, r + len, layer + 1);
    else if (l > mid)
        return sum(cur->son[!st], l - len, r - len, layer + 1);
    else
        return sum(cur->son[st], l + len, mid + len, layer + 1) +
               sum(cur->son[!st], mid + 1 - len, r - len, layer + 1);
}
int main() {
    read(n), read(q);
    for (int i = 1; i <= 1 << n; i++) read(a[i]);
    build(root, 1, 1 << n);
    while (q--) {
        int type;
        read(type);
        switch (type) {
            case 1:
                read(x), read(k);
                replace(root, x, k, 0);
                break;
            case 2:
                read(k);
                for (int i = n - k; i <= n; i++) tag[i] ^= 1;
                break;
            case 3:
                read(k);
                tag[n - k - 1] ^= 1;
                break;
            case 4:
                read(l), read(r);
                printf("%lld\n", sum(root, l, r, 0));
                break;
            default:
                break;
        }
    }
    return 0;
}