Martian148's blog
martian148
2024-11-14
目录

CCPC2023 桂林站

# CCPC2023 桂林站

第九届中国大学生程序设计竞赛 桂林站（CCPC 2023 Guilin Site） (opens new window)

# C - Master of Both IV （线性基，铜牌题）

# Question

给一个可重集，求有多少子集满足每个元素都可以被异或和整除

# Solution

设子集为 SS，设 lcm(S)=f,xor(s)=g\text{lcm}(S)=f, \text{xor}(s)=g

有 g<2max⁡{a}，max⁡{a}∣gg<2\max\{a\}，\max\{a\}|g

所以有 g=0,g=max⁡{a}g=0,g=\max\{a\}

g=0g=0 的情况就是集合中有多少个子集异或和为 00，这是一个经典的问题，就是线性基 2n−rank2^{n-rank}

g=max⁡{a}g=\max\{a\} 时，我们需要把 gg 的因子且在集合中的加入线性基，因为 max⁡{a}⊕g=0\max\{a\}\oplus g=0 也就转化成了第一种情况

总时间复杂度为 O(nlog⁡2n)O(n\log^2 n)

# Code

#include <bits/stdc++.h>

constexpr int TP = 30;
constexpr int TT = 998244353;
using ll = long long;

struct AS {
    std::vector<int> p;
    AS() : p(TP, 0) {}
    void insert(int x, int &cnt) {
        for (int i = TP - 1; i >= 0; i--) if (x >> i & 1) {
            if (p[i]) x ^= p[i];
            else {p[i] = x; return ;}
        }
        cnt += 1;
    }

    bool check (int x) {
        for (int i = TP - 1; i >= 0; i--) {
            if (x >> i & 1) x ^= p[i];
        }
        return x == 0;
    }
};

void solve() {
    int n; std::cin >> n;
    std::vector<int> a(n + 1, 0), f(n + 1, 0);
    f[0] = 1;
    for (int i = 1; i <= n; i++) f[i] = 2 * f[i - 1] % TT;

    for (int i = 1; i <= n; i++) std::cin >> a[i];
    int M = *std::max_element(a.begin(), a.end());
    std::vector<int> b(M + 1, 0);
    std::vector<std::vector<int>> g(M + 1);
    for (int i = 1; i <= n; i++) b[a[i]] += 1;
    for (int i = 1; i <= M; i++)
        for (int j = 0; j <= M; j += i)
            g[j].push_back(i);

    int ans = 0;
    for (int i = 0; i <= M; i++) {
        AS as;
        int now = 0;
        for (auto d : g[i]) {
            if (b[d] == 0) continue;
            now += b[d] - 1;
            as.insert(d, now);
        }
        if (as.check(i))
            ans = (ans + f[now]) % TT;
    }

    std::cout << ans - 1 << '\n';
}

int main() {
    // freopen ("C.in", "r", stdin);
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);
    int T; std::cin >> T;
    while (T--) solve();
    return 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

# G - Hard Brackets Problem

# Solution

队友写的签到

# Code

#include<bits/stdc++.h>
using namespace std;
int Tex;
string s;
void AC(){
    cin >> s;
    int top = 0;
    for(int i = 0; i < s.size(); i ++){
        if(s[i] == '(') top ++;
        else if(top) top --;
    }
    if(top) cout << "impossible" << "\n";
    else cout << s << "\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin >> Tex;
    while(Tex --) AC();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# K - Randias permutation task

# Question

给出 mm 个长度为 nn 的排列，选出若干个（非零）按顺序复合，问得到的排列有多少种，n×m≤180n\times m\le 180

# Solution

考虑到 ansans 的最大值是 min⁡{2m,n!}≤362880\min\{2^m,n!\}\le362880，所以我们可以模拟这个过程

定义集合 {S}\{S\} 为已经组成的排列，枚举到第 ii 个排列，我们把 SS 中每个排列和 ii 进行符合运算，得到集合 S′S' 然后把 S′S' 和 SS 合并，来模拟 ii 的选和不选

# Code

#include <bits/stdc++.h>

std::vector<int> calc (std::vector<int> &a, std::vector<int> &b) {
    int n = a.size();
    std::vector<int> ret(n);
    for (int i = 0; i < n; i++) ret[i] = a[b[i]];
    return ret;
}

int main() {
    freopen ("K.in", "r", stdin);

    int n, m; std::cin >> n >> m;
    std::vector<std::vector<int>> p(m, std::vector<int>(n, 0));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            std::cin >> p[i][j]; p[i][j] -= 1;
        }
    std::set<std::vector<int>> st, st_;
    for (auto B : p) {

        st_.clear();
        for (auto A : st) {
            auto C = calc(A, B);
            st_.insert(C);
        }
        for (auto A : st_) {
            st.insert(A);
        }
        st.insert(B);
    }
    
    std::cout << st.size() << std::endl;
    return 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

# I - Barkley II

# Question

给出一个序列，选择一个区间使得区间有多少个不同数 - 区间 mexmex 最大

# Solution

我们枚举 mex = x，然后得到了没有 x 的极长区间，我们能离线统计这个区间内有多少个不同的数，最优解就是答案

假设 mex = y < x，那么此时得到的答案肯定劣于答案，所以我们只需要认为区间内没有这个数即是这个区间的 mex 即可，最后的答案不会收到影响

# Code

#include <bits/stdc++.h>

const int INF = 0x3f3f3f3f;

struct query {
    int l, r, mex;
    bool operator < (const query &rhs) const {
        return r < rhs.r;
    }
};

void solve() {
    int n, M; std::cin >> n >> M;
    std::vector<int> a(n + 1, 0);

    for (int i = 1; i <= n; i++) std::cin >> a[i];

    M = *max_element(a.begin() + 1, a.end()) + 1;
    std::vector<std::vector<int>> p(M + 1);
    for (int i = 1; i <= M; i++)
        p[i].push_back(0);
    for (int i = 1; i <= n; i++)
        p[a[i]].push_back(i);
    for (int i = 1; i <= M; i++)
        p[i].push_back(n + 1);

    std::vector<query> q;
    for (int i = 1; i <= M; i++) {
        for (int j = 0; j + 1 < p[i].size(); j++) {
            if (p[i][j + 1] - p[i][j] <= 1) continue;
            q.push_back({p[i][j] + 1, p[i][j + 1] - 1, i});
        }
    }

    std::vector<int> c(n + 2, 0), pre(M + 1, 0);

    auto add_x  = [&] (int x, int val) -> void {
        for (; x <= n; x += x & -x)
            c[x] += val;
    };

    auto query_x = [&] (int x) -> int {
        int res = 0;
        for (; x; x -= x & -x)
            res += c[x];
        return res;
    };

    std::sort(q.begin(), q.end());

    int j = 0, ans = -INF;
    for (int i = 1; i <= n; i++) {
        if (pre[a[i]]) add_x(pre[a[i]], -1);
        add_x(i, 1);
        pre[a[i]] = i;
        while (j < q.size() && q[j].r == i) {
            int now = query_x(q[j].r) - query_x(q[j].l - 1);
            ans = std::max(ans, now - q[j].mex);
            j += 1;
        }
    }

    std::cout << ans << '\n';
}

int main() {
    freopen ("I.in", "r", stdin);
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(NULL); std::cout.tie(NULL);

    int T; std::cin >> T;
    while (T--) solve();
    return 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
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

# J - The Phantom Menace

# Question

给出两个字符串数组，都是有 nn 个长度为 mm 的串，需要找出一种排列方式，使得两个字符串数组按顺序拼接之后循环重构

nm≤106nm\le 10^6

# Solution

枚举循环同构的偏移量 xx，

  • 第一个数组中第一个串长度为 xx 的后缀和第二个数组中一个串长度为 xx 的前缀匹配

  • 第一个数组中第二个串长度为 m−xm-x 的前缀和第二个数组中第一个串长度为 m−xm-x 的后缀匹配

  • ⋯\cdots

所以我们把相同的前后缀看成点，字符串看成边，找欧拉回路即可

# M - Flipping Cards

# Question

给 nn 张正反面有数字的牌，翻转不超过一个区间使中位数最大

# Solution

典中典，看到中位数想到二分答案 ww ，然后求 [bi≥w]−[ai≥w][b_i\ge w]-[a_i\ge w] 的最大字段和

# Code

#include<bits/stdc++.h>

using ll = long long;
constexpr int INF = 0x3f3f3f3f;


int main() {
    freopen ("M.in", "r", stdin);

    int n; std::cin >> n;
    std::vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i] >> b[i];

    auto check = [&] (int mid) -> bool {
        std::vector<int> sa(n + 1, 0), sb(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            sa[i] = sa[i - 1] + (a[i] >= mid ? 1 : -1);
            sb[i] = sb[i - 1] + (b[i] >= mid ? 1 : -1);
        }
        int ans = -INF, pre = 0;
        for (int i = 1; i <= n; i++) {
            if (sa[pre] - sb[pre] < sa[i] - sb[i])
                pre = i;
            ans = std::max(sa[pre] + sb[i] - sb[pre] + sa[n] - sa[i], ans);
        }
        return ans > 0;
    };

    int l = 1, r = 1e9 + 1;
    while (l + 1 < r) {
        int mid = (r - l >> 1) + l;
        if (check(mid)) l = mid;
        else r = mid;
    }
    std::cout << l << "\n";
    return 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
上次更新: 2024/11/04, 07:55:26
CCPC2023 哈尔滨站
CCPC2023 秦皇岛站 题解

← CCPC2023 秦皇岛站 题解→

最近更新
01
逻辑学
12-13
02
中华传统文化
12-12
03
欧拉回路
11-14
更多文章>
Theme by Vdoing | Copyright © 2024-2024 Martian148 | MIT License