四川省大学生程序设计竞赛2026个人题解 • santisify Site

最大权独立集问题#

题目详情

题目描述

给定 $n$ 个点，每个点有一个整数权值 $W_i$ 。

定义两点 $i$ 和 $j$ 之间存在一条无向边，当且仅当 $W_i \oplus W_j$ （其中 $\oplus$ 表示按位异或运算）的二进制表示中， $1$ 的个数为奇数。

请你求出这个图的最大权独立集。即，选择一个点集满足集合内任意两点之间没有边，且集合内点的权值之和最大。定义空集的权值为 $0$ 。你只需要求出这个最大的权值之和。

输入格式

本题有多组数据。

输入一行一个正整数 $t$ （ $1 \le t \le 10^5$ ），表示测试数据组数。

每组数据中：

第一行一个正整数 $n$ （ $1 \le n \le 5 \times 10^5$ ），表示点数。

第二行 $n$ 个正整数 $W_1,W_2,\cdots,W_n$ （ $1 \le W_i \le 10^9$ ），表示点的权值。

保证 $1 \le \sum n \le 5 \times 10^5$ 。

输出格式

每组数据输出一行一个整数，表示最大权独立集的权值之和。

输入输出样例 #1

输入 #1

plaintext

输出 #1

23
18
15

plaintext

解题思路#

题目中给出 $W_i$ 和 $W_j$ 二进制下异或结果的 $1$ 个数为奇数代表之间有一条边.那我们可以假设一下,将数组 $A$ 中的数按照二进制下 $1$ 的个数划分为奇数 $X$ 和偶数 $Y$ 两个集合.

对于一个集合中两个数 $X_i$ ( $x$ 个 $1$ ), $X_j$ ( $y$ 个 $1$ ), 其中两个数二进制下有 $k$ 个 $1$ 是同时出现的,那么这两个数异或后的结果就有 $x+y-2*k$ 个 $1$

通过 $x+y-2*k$ 可以发现无论 $x$ , $y$ 同为奇数或偶数结果都为偶数,可以证明同一个集合内的任意两个数不会有边.

参考代码#

#include <bits/stdc++.h>

#define int long long
#define pii std::pair<int,int>

void solve() {
    int n;
    std::cin >> n;
    int a = 0, b = 0;
    for (int x, i = 0; i < n; ++i) {
        std::cin >> x;
        int ct = __builtin_popcount(x); //__builtin_popcount(x) 为计算x在二进制下1的个数
        if (ct & 1) a += x;
        else b += x;
    }
    std::cout << std::max(a, b) << std::endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int T = 1;
    std::cin >> T;
    while (T --) solve();
    return 0;
}

cpp

那一天的回文字符串#

题目详情

题目描述

一天，面码和仁太遇到了一个由小写英文字母组成的字符串 $s$ 。

为了打发时间，他们发明了一个游戏：面码可以任意重排字符串中所有奇数下标位置上的字符，仁太可以任意重排字符串中所有偶数下标位置上的字符。

他们想知道，经过这样的重排后，是否可以把字符串变成一个回文串。请你帮助他们！

回文串指从前往后读和从后往前读都相同的字符串。例如， $\mathtt{aa}$ 、 $\mathtt{aba}$ 和 $\mathtt{abccba}$ 是回文串，而 $\mathtt{sccpc}$ 、 $\mathtt{reality}$ 和 $\mathtt{ab}$ 不是回文串。

输入格式

第一行包含一个整数 $t$ （ $1 \le t \le 100$ ），表示测试数据的组数。

对于每组测试数据，唯一一行包含一个由小写英文字母组成的字符串 $s$ （ $1 \le |s| \le 100$ ）。

输出格式

对于每组测试数据，如果可以将 $s$ 变成回文串，输出一行 “YES”，否则输出一行 “NO”。

你可以以任意大小写形式输出答案。例如，“yEs”、“yes”、“Yes” 和 “YES” 都会被视为正确回答。

输入输出样例 #1

输入 #1

5
abba
abcd
aabb
abcba
abcde

plaintext

输出 #1

YES
NO
YES
YES
NO

plaintext

说明/提示

在第一组测试数据中，给定字符串本身已经是一个回文串。

在第三组测试数据中，可以重排奇数下标位置，使得下标 $1$ 处为 $\mathtt{a}$ ，下标 $3$ 处为 $\mathtt{b}$ ；同时重排偶数下标位置，使得下标 $2$ 处为 $\mathtt{b}$ ，下标 $4$ 处为 $\mathtt{a}$ 。这样可以得到回文串 $\mathtt{abba}$ 。

解题思路#

字符串中只能同奇偶性的下标的字母可交换,那么我们就需要根据字符串长度做分类讨论:

1.对于偶数长度的字符串,只有偶数下标与奇数下标的字母完全相等才能组成回文字符串.

2.对于奇数长度的字符串,只有不成对出现的个数 $ct \le 1$ 才能组成回文字符串.

参考代码#

#include <bits/stdc++.h>

#define int long long
#define pii std::pair<int,int>

void solve() {
    std::string s;
    std::cin >> s;
    std::vector<int> a(30, 0), b(30, 0);
    for (int i = 0; i < s.size(); i ++) {
        if (i & 1) b[s[i] - 'a'] ++;
        else a[s[i] - 'a'] ++;
    }
    bool res = false;
    if (s.size() & 1) {
        int t1 = 0, t2 = 0;
        for (int i = 0; i < 26; i ++) {
            t1 += (a[i] & 1);
            t2 += (b[i] & 1);
        }
        res = (t1 + t2 <= 1);
    } else {
        res = (a == b);
    }
    std::cout << (res ? "YES" : "NO") << std::endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int T = 1;
    std::cin >> T;
    while (T --) solve();
    return 0;
}

cpp

禁忌教典的消失咒文#

题目详情

题目描述

阿尔扎诺帝国魔术学院中，格伦老师难得认真地研究起了一本古老的禁忌教典。教典中记载了一种特殊的法术序列。序列由 $n$ 道咒文组成，第 $i$ 道咒文的魔力值为 $a_i$ 。

一开始，希丝缇娜以为只要把所有咒文的魔力简单相加，就能得到整个法术的强度。但格伦老师很快发现，这种咒文并不是这样运作的。第一道咒文会正向释放魔力，第二道咒文会反向抵消魔力，第三道咒文又会正向释放魔力，第四道咒文再次反向抵消魔力，之后依次交替。形式化地，对于一个法术序列 $b_1,b_2,...,b_m$ ，定义它的能量值为 $E(b)=\sum_{i=1}^{m}(-1)^{i+1}b_i$ 。空序列的能量值定义为 $0$ 。

在继续解析教典时，露米娅发现其中有一段连续咒文受到了异常魔力污染。如果直接吟唱，整个法术很可能会失控。于是格伦老师决定：必须恰好选择一段非空连续咒文，将它们从序列中抹去。也就是说，需要选择一个区间 $[l,r]$ ，删除 $a_l,a_{l+1},...,a_r$ 。被删除的咒文消失后，剩余咒文会按照原来的相对顺序自动连接成一个新的法术序列 $a_1,...,a_{l-1},a_{r+1},...,a_n$ 。

格伦老师希望最终得到的法术序列能量值恰好等于 $k$ 。请你帮助希丝缇娜和露米娅计算，有多少种不同的删除区间 $[l,r]$ 可以满足这个要求。

输入格式

第一行包含一个整数 $t$ ( $1 \le t \le 10^5$ )，表示测试数据组数。

对于每组测试数据，第一行包含两个整数 $n,k$ ( $1 \le n \le 10^6$ ， $-10^9 \le k \le 10^9$ )，表示咒文数量和目标能量值。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ( $-10^9 \le a_i \le 10^9$ )，表示每道咒文的魔力值。

保证所有测试数据的 $n$ 之和不超过 $10^6$ 。

输出格式

对于每组测试数据，输出一个整数，表示满足要求的删除区间数量。

输入输出样例 #1

输入 #1

plaintext

输出 #1

2
2
3

plaintext

解题思路#

这道题的核心在于将原序列的交替符号特性吸收到前缀和中，然后通过分析删除区间长度奇偶性对剩余序列能量值的影响，把问题转化为对前缀和的等式计数。

记前缀和 $S_i = \sum_{j=1}^i A_j$ 。

删除区间 $[l, r]$ ，剩余部分由 $[1, l-1]$ 和 $[r+1, n]$ 拼接而成。前半部分能量为 $S_{l-1}$ 。后半部分的元素在原序列中位置前移了 $\text{len} = r-l+1$ 位。由于符号与位置的奇偶相关，移动 $\text{len}$ 位会导致后半部分每个元素的符号整体乘上 $(-1)^{\text{len}}$ 。因此后半部分能量为 $(-1)^{\text{len}} (S_n - S_r)$ 。剩余序列总能量： $E = S_{l-1} + (-1)^{r-l+1}(S_n - S_r)$ 要求 $E = k$ 。

若区间长度为偶数（ $r-l+1$ 为偶，即 $r$ 与 $l-1$ 同奇偶）： $E = S_{l-1} + S_n - S_r = k \quad \Rightarrow \quad S_r = S_{l-1} + S_n - k$
若区间长度为奇数（ $r-l+1$ 为奇，即 $r$ 与 $l-1$ 不同奇偶）： $E = S_{l-1} - (S_n - S_r) = k \quad \Rightarrow \quad S_r = k + S_n - S_{l-1}$

设 $x = l-1$ ，则 $0 \le x < r \le n$ 。对于确定的右端点 $r$ ，需要找满足等式的 $x$ 。利用 $x$ 与 $r$ 的奇偶关系，等式化为：

同奇偶时： $S_x = S_r - S_n + k$ （记为 $v_1$ ）
不同奇偶时： $S_x = S_n - S_r + k$ （记为 $v_2$ ）
不同奇偶时： $S_x = S_n - S_r + k$ （记为 $v_2$ ）

我们可以遍历右端点 $r = 1 \dots n$ ，用两个哈希表分别维护已遍历的、下标为偶数的 $S_x$ 和下标为奇数的 $S_x$ 的出现次数。对于当前 $r$ ：

若 $r$ 为奇数：同奇偶的 $x$ 必为奇数，查奇数表找 $v_1$ ；不同奇偶的 $x$ 为偶数，查偶数表找 $v_2$ 。
若 $r$ 为偶数：同奇偶的 $x$ 为偶数，查偶数表找 $v_1$ ；不同奇偶的 $x$ 为奇数，查奇数表找 $v_2$ 。

查询后，再将 $S_r$ 按 $r$ 的奇偶性存入对应的哈希表（这样保证只匹配 $x < r$ ）。最后累加结果。

初始时 $x=0$ （对应 $l=1$ ）是偶数且 $S_0=0$ ，因此将 ct0[0] 初始化为 1。

参考代码#

#include <bits/stdc++.h>

#define int long long
#define pii std::pair<int,int>

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

    std::unordered_map<int, int> ct0, ct1;
    int ans = 0;
    ct0[0] ++;
    for (int i = 1; i <= n; i ++) {
        int v1 = k + a[i] - a[n];
        int v2 = k - a[i] + a[n];
        if (i & 1) {
            ans += ct0[v2] + ct1[v1];
        } else {
            ans += ct0[v1] + ct1[v2];
        }
        if (i & 1) ct1[a[i]] ++;
        else ct0[a[i]] ++;
    }
    std::cout << ans << std::endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int T = 1;
    std::cin >> T;
    while (T --) solve();
    return 0;
}

cpp

永恒的奥古斯都#

题目详情

题目描述

有一棵 $n$ 个点的树 $T$ ，树的根节点为 $1$ 。初始时点 $i$ 有颜色 $c_i$ （ $0 \le c_i \le 1$ ）。

小 L 进行了若干次（可以为 $0$ ）操作，每次操作她会选择一个满足 $c_u =0$ 的节点 $u$ ，对 $u$ 子树内的所有点 $v$ 执行 $c_v \gets 1 - c_v$ 。所有操作结束后得到树 $T'$ ，其中点 $i$ 的颜色变为了 $c'_i$ 。

现在给你最后得到的树 $T'$ 和每个点的颜色 $c'_i$ ，你需要求出有多少种不同的可能初始状态 $T$ 。答案对 $998244353$ 取模。

在此题中，我们认为两棵树 $T_1,T_2$ 不同，当且仅当存在点 $1 \le u \le n$ ，满足其在 $T_1$ 中的颜色为 $c_{1,u}$ ，在 $T_2$ 中的颜色为 $c_{2,u}$ ，且 $c_{1,u} \neq c_{2,u}$ 。

输入格式

输入第一行一个正整数 $n$ （ $1 \le n \le 2 \times 10^5$ ），表示 $T'$ 的点数。

第二行 $n$ 个整数 $c'_1,c'_2,\cdots,c'_n$ （ $0 \le c'_i \le 1$ ），表示最终状态下每个点的颜色。

接下来 $n-1$ 行，每行两个正整数 $u,v$ （ $1 \le u,v \le n$ ， $u \neq v$ ），表示 $T'$ 中存在一条边 $(u,v)$ 。保证所有边构成一棵树。

输出格式

输出一行一个整数，表示可能的初始状态 $T$ 的个数对 $998244353$ 取模后的值。

输入输出样例 #1

输入 #1

plaintext

输出 #1

plaintext

输入输出样例 #2

输入 #2

plaintext

输出 #2

plaintext

解题思路#

题目要求：给定最终树 T' 每个点的颜色 $c'_i$ （0/1）和树的结构，问有多少种可能的初始颜色状态 $c_i$ ，使得可以通过若干次“选择颜色为 0 的节点并翻转其子树”的操作变成 c'。

设变量 $x_u ∈ {0, 1}$ 表示节点 u 是否被操作（奇偶性）。最终颜色与初始颜色、操作的关系为： $c'_u = c_u \oplus x_v$ ( v 是 u 的祖先) 已知 c'，计数初始 c 等价于计数合法的操作变量 x（两者一一对应）。合法指存在一个操作顺序，使得每次操作时该节点当前颜色为 0。

可以自底向上进行 DP，维护以 u 为根的子树在两种情形下的合法初始状态数：

dp0[u]：u 不操作 ( $x_u = 0$ ) 时子树内的方案数（实际上对于根，它包含了所有合法情况的答案）。
dp1[u]：u 操作 ( $x_u = 1$ ) 时子树内的方案数。

核心结论：若 u 被操作，则其子树内所有初始颜色都可以通过合法操作达到目标，方案数达到最大，即 $dp1[u] = 2^{\text{size}(u)}$ 其中 size(u) 是以 u 为根的子树大小。该值与 c' 无关，可以通过归纳证明。

对 u 的子节点 v，设 $v1 = \prod dp0[v]$ ， $v2 = \prod dp1[v]$ （代码中的记号）。

dp1[u]：无论 c'_u 为何，dp1[u] = 2 * v2。递归展开即 $2^{size(u)}$ 。
dp0[u]：根据 c'_u 分情况：
若 $c'_u = 0$ ：u 必须不操作（否则最终颜色会变成 1），故 dp0[u] = v1。
若 $c'_u = 1$ ：u 可以不操作或操作。

不操作时贡献 v1；操作时贡献 v2（即 $2^{size(u)-1}$ ）。

因此 dp0[u] = v1 + v2。

根节点 1 没有父节点限制，所有合法方案均已包含在 dp0[1] 中，直接输出即可。

参考代码#

#include <bits/stdc++.h>

#define int long long
#define pii std::pair<int,int>

const int MOD = 998244353;

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> c(n + 1, 0);
    std::vector g(n + 1, std::vector<int>());
    for (int i = 1; i <= n; i ++) std::cin >> c[i];

    for (int i = 1, u, v; i < n; i ++) {
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    std::vector<int> fa(n + 1, 0), vis(n + 1, 0), b;
    std::stack<int> stk;
    stk.push(1);
    fa[1] = 0;
    while (!stk.empty()) {
        auto u = stk.top();
        if (!vis[u]) {
            vis[u] = 1;
            for (auto v: g[u]) {
                if (v != fa[u]) {
                    fa[v] = u;
                    stk.push(v);
                }
            }
        } else {
            stk.pop();
            b.push_back(u);
        }
    }

    std::vector<int> dp0(n + 1, 0), dp1(n + 1, 0);
    for (auto u: b) {
        int v1 = 1, v2 = 1;
        for (auto v: g[u]) {
            if (v == fa[u]) continue;
            v1 = dp0[v] * v1 % MOD, v2 = dp1[v] * v2 % MOD;
        }

        dp0[u] = (v1 + c[u] * v2) % MOD;
        dp1[u] = (2 * v2) % MOD;
    }

    std::cout << dp0[1] % MOD << std::endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int T = 1;
    // std::cin >> T;
    while (T --) solve();
    return 0;
}

cpp