2023CCPC 国赛（桂林）题解

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

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

Question

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

Solution

设子集为 $S$ ，设 $lcm (S) = f, xor (s) = g$

有 $g < 2 max {a} ， max {a} | g$

所以有 $g = 0, g = max {a}$

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

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

总时间复杂度为 $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;
}

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;
}

K - Randias permutation task

Question

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

Solution

考虑到 $a n s$ 的最大值是 $min {2^{m}, n!} \leq 362880$ ，所以我们可以模拟这个过程

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

Code

#include <bits/stdc++.h>

std::vector<int> calc 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;
}

I - Barkley II

Question

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

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;
}

J - The Phantom Menace

Question

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

$n m \leq 10^{6}$

Solution

枚举循环同构的偏移量 $x$ ，

第一个数组中第一个串长度为 $x$ 的后缀和第二个数组中一个串长度为 $x$ 的前缀匹配
第一个数组中第二个串长度为 $m - x$ 的前缀和第二个数组中第一个串长度为 $m - x$ 的后缀匹配
$\dots$

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

M - Flipping Cards

Question

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

Solution

典中典，看到中位数想到二分答案 $w$ ，然后求 $[b_{i} \geq w] - [a_{i} \geq 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;
}