博客广场/ zhuyqi

比赛总结

8.5总结

8.5总结(昨天只发了讨论，忘发博客了) 今天的考试内容其实难度没有那么难，但是呢我只拿了200分。考试题目： T1:AGAGA XOOORRR 链接：AGAGA XOOORRR - 题目详情 - QY code 题意：你拥有一个长度为 n 的数组，你可以执行以下操作：选择数组中相邻的两个元素，将它们删除，并在原位置放入这两个数的**按位异或（XOR）

zhuyqi发布于 2026-8-6 17:41:25

动态规划

8.5总结(昨天只发了讨论，忘发博客了)

今天的考试内容其实难度没有那么难，但是呢我只拿了200分。

考试题目：

T1:AGAGA XOOORRR

链接：****AGAGA XOOORRR - 题目详情 - QY code

题意：

你拥有一个长度为 n 的数组，你可以执行以下操作：

选择数组中相邻的两个元素，将它们删除，并在原位置放入这两个数的**按位异或（XOR）**值。
每次操作后，数组的长度会减少 1。

经过任意次上述操作后，数组必须满足以下两个条件：

元素相等：数组中所有剩余的元素值必须完全相同。
长度限制：最终数组中至少保留 2 个元素（即不能把所有元素合并成 1 个）。

思路：

题目要求将数组分成至少两段（对应最终保留至少2个元素），且每一段内部连续元素的异或和都相等。

设最终每段的异或和为x，总段数为 k ( k≥2 )：

整个数组的异或和为x⊕x⊕x⊕...⊕x（共 k 次）。
当 k 为偶数时：总异或和为0 。
当 k 为奇数时：总异或和为 x 。

因此，我们只需要判断数组能否被划分成满足上述条件的段即可。

通过计算前缀异或和 pre[i]=a[1]^a[2]^...^a[i]，分两种情况判断：

情况一：总异或和 `pre[n] == 0`

此时对应 k 为偶数的情况。我们只需要在数组中找到至少一个分割点，使得第一段异或和为 0 。

判断条件：遍历 i∈[1,n−1] ，只要存在 pre[i] == 0，说明前 i 个元素异或和为 0 ，剩下的元素异或和也为 0 。满足条件，输出 YES。

情况二：总异或和 `pre[n] != 0`

此时对应 k 为奇数且 k≥3 的情况（因为 k=1 不满足至少保留2个元素的要求）。此时每段的异或和 x 必须等于 pre[n]。

判断条件：我们需要找到至少两个分割点，将数组分为至少三段，且每段异或和均为 pre[n]。
代码实现技巧：遍历前缀和，用一个标记 ok 记录是否已经找到了第一段（即 pre[j] == pre[n]）。如果已经找到第一段，并且在后续位置又遇到了 pre[j] == 0（注意：因为 pre[n] != 0，前两段异或和为 pre[n] ^ pre[n] = 0，所以第三段开始的累计前缀和会回到 0），则说明成功划分出了至少三段，输出 YES。

3. 复杂度分析

时间复杂度： O(n) ，每个测试用例仅需遍历数组常数次。
空间复杂度： O(n) ，用于存储前缀异或和数组。

代码：

#include <bits/stdc++.h>
using namespace std;
long long a[2010];
long long pre[2010];
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        int n;
        scanf ("%d", &n);
        for (int i = 1; i <= n; i++) scanf ("%lld", &a[i]);
        pre[0] = 0;
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] ^ a[i];
        bool flag = false;
        if (pre[n] == 0) {
            for (int i = 1; i < n; i++) {
                if (pre[i] == 0) {
                    flag = true;
                    break;
                }
            }
        }
        if (!flag) {
            bool ok = false;
            for (int j = 1; j < n; j++) {
                if (pre[j] == pre[n]) ok = true;
                if (pre[j] == 0 && ok) {
                    flag = true;
                    break;
                }
            }
        }
        if (flag) puts ("YES");
        else puts ("NO");
    }
    return 0;
}

T2:Vampiric Powers, anyone?

链接：****Vampiric Powers, anyone? - 题目详情 - QY code

题意：

题目允许我们选择下标 i ，将 $a_i⊕a_{i+1}⊕...⊕a_m$ 追加到数组末尾。这个操作本质上就是取当前数组的一个后缀进行异或。

初始状态下，我们能得到的所有后缀异或和，就是初始数组的所有后缀异或和。
当我们追加了一个新的后缀异或和 x 后，新的数组多了一个元素 x 。此时再取后缀，要么是不包含 x 的原后缀，要么是包含 x 的后缀。
包含 x 的新后缀异或和 = $x⊕$ (某个旧后缀) 。
因此，所有可能生成的新力量，都可以表示为“两个旧后缀异或和的异或”。

设 $S_i$ 表示从 i 到 n 的后缀异或和。我们想知道任意两个后缀异或和 $S_i$ 和 $S_j$ （假设 i≤j ）的异或结果 $S_i⊕S_j$ 是什么：

$S_i⊕S_j=(a_i⊕...⊕a_{j-1}⊕a_j⊕...⊕a_n)⊕(a_j⊕...⊕a_n)$

根据异或运算 x⊕x=0 的性质，后半部分完全抵消，得到：

$S_i⊕S_j=a_i⊕...⊕a_{j-1}$

这正好是数组的一个子数组（连续子段）的异或和！

无论进行多少次操作，所有可能出现的替身使者力量，必定是初始数组的某个连续子数组的异或和！

而任何一个连续子数组 [l,r] 的异或和，都可以表示为两个后缀异或和的异或：

$a_l⊕...⊕a_r=S_l⊕S_r+1$

（特别地，当 r=n 时， $S_n+1=n$ ，即单个后缀本身也是合法的）。

基于上述结论，代码的逻辑就非常清晰了：

计算所有后缀异或和：从后往前遍历数组，计算后缀异或和 suff，并将其存入集合 suf 中。
补充边界情况：将 0 插入集合（对应空后缀 $S_n+1$ ，用于表示以数组末尾结尾的子数组）。
枚举最大值：因为所有可能的值都是集合中任意两个元素的异或，所以直接双重循环遍历集合 suf，计算 x ^ y 的最大值即可。

时间复杂度： $O(n+k^2)$ ，其中 n 是数组长度， k 是不同后缀异或和的数量。因为 $a_i \le 2^8=256$ ，所以不同的异或和最多只有 256 种， $k^2$ 最多为 2562=65536 ，加上遍历数组的 O(n) ，整体非常高效。
空间复杂度： O(k) ，用于存储后缀异或和的集合。

代码：

#include <bits/stdc++.h>
using namespace std;
int a[100010]; 
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        int n;
        scanf ("%d", &n);
        for (int i = 1; i <= n; i++) scanf ("%d", &a[i]);
        int suff = 0;
        unordered_set <int> suf;
        for (int i = n; i >= 1; i--) {
            suff ^= a[i];
            suf.insert (suff);
        }
        suf.insert (0);
        int ans = 0;
        for (auto x : suf) {
            for (auto y : suf) ans = max (ans, x ^ y);
        }
        printf ("%d\n", ans);
    }
    return 0;
}
// 我的思路和老师的思路刚好相反，老师算的是前缀，我算的是后缀

T3:Short Program

链接：****Short Program - 题目详情 - QY code

题意：

你有一个用 CALPAS 语言编写的程序，它接收一个0∼1023 之间的非负整数作为输入。程序中只包含三种位运算指令，且常数范围都在 0∼1023 之间：

& x：按位与
| x：按位或
^ x：按位异或

原程序可能非常长（指令数 n 高达 $5*10^5$ ）。你需要编写一个全新的、极短的 CALPAS 程序，要求：

功能完全等价：对于 0∼1023 范围内的所有输入，新程序和原程序的输出结果必须完全一致。
长度限制：新程序的指令行数最多只能有 5 行（实际上通过数学推导，最多只需要 3行即可）。

思路：

对于任意一个位运算程序，我们只需要知道它在输入为 0 和输入为 全 1（本题中为 1023，即二进制的 1111111111）时的输出，就能推导出它对任何输入的等效运算规则。

设初始输入为 x 。
我们用 v0 记录当初始输入为 0 时，经过所有指令后的最终结果。
我们用 v1 记录当初始输入为 1023 时，经过所有指令后的最终结果。

对于结果的任意一个二进制位，根据 v0 和 v1 在该位的值，只有 4 种可能的情况：

根据上表，我们可以用以下 3 种操作来组合实现所有的等效规则：

& A** (按位与)：用于将某些位强制置 0**。如果某位需要置 0，则 A 的该位为 0，否则为 1。
| B** (按位或)：用于将某些位强制置 1**。如果某位需要置 1，则 B 的该位为 1，否则为 0。
^ C** (按位异或)：用于将某些位强制取反**。如果某位需要取反，则 C 的该位为 1，否则为 0。

构造顺序：先 & A，再 | B，最后 ^ C。

对于需要置 0 的位：A=0, B=0, C=0 ⇒ x & 0 = 0。
对于保持不变的位：A=1, B=0, C=0 ⇒ x & 1 = x。
对于强制置 1 的位：A=1, B=1, C=0 ⇒ x & 1 = x, x | 1 = 1。
对于强制取反的位：A=1, B=0, C=1 ⇒ x & 1 = x, x ^ 1 = ~x。

模拟过程：遍历输入的 n 条指令，分别对 v0 和 v1 执行相同的位运算。
提取常数：遍历 0 到 9 位，根据 f0 (v0 的当前位) 和 f1 (v1 的当前位) 的组合，按照上面的表格设置常数 A,B,C 的对应位。
过滤无效指令：如果 A=1023 （全 1），& A 无意义，不输出；如果 B=0 ，| B 无意义，不输出；如果 C=0 ，^ C 无意义，不输出。

时间复杂度： $O(n+logM)$ ，其中 n 是指令数， M 是常数上限（1024）。只需遍历一遍指令和 10 个二进制位。
空间复杂度： $O(1)$ ，仅需几个变量存储状态。

代码：

#include <bits/stdc++.h>
using namespace std;
int n; 
int a[500010];
int main () {
    scanf ("%d", &n);
    int v0 = 0, v1 = 1023;
    for (int i = 1; i <= n; i++) {
        char op[2];
        int x;
        scanf ("%s%d", op, &x);
        if (op[0] == '&') v0 &= x, v1 &= x;
        if (op[0] == '|') v0 |= x, v1 |= x;
        if (op[0] == '^') v0 ^= x, v1 ^= x;
    }
    int A = 0, B = 0, C = 0;
    for (int bit = 0; bit <= 9; bit++) {
        int f0 = (v0 >> bit) & 1;
        int f1 = (v1 >> bit) & 1;
        int ai = 0, bi = 0, ci = 0;
        if (f0 == 0 && f1 == 1) ai = 1;
        if (f0 == 1 && f1 == 1) bi = 1;
        if (f0 == 1 && f1 == 0) ai = 1, ci = 1;
        if (ai) A |= (1 << bit);
        if (bi) B |= (1 << bit);
        if (ci) C |= (1 << bit);
    } 
    vector <pair <char, int> > ans;
    if (A != 1023) ans.push_back ({'&', A});
    if (B != 0) ans.push_back ({'|', B});
    if (C != 0) ans.push_back ({'^', C});
    printf ("%d\n", ans.size ());
    for (auto p : ans) {
        printf ("%c %d\n", p.first, p.second);
    }
    return 0;
}

T4:Orray

链接：****Orray - 题目详情 - QY code

题意：

给定一个长度为 n 的数组 a ，它的“前缀按位或”数组 b 是这样计算的：

$b_1=a_1$
$b_2=a_1\ OR\ a_2$
$b_3=a_1\ OR\ a_2\ OR\ a_3$
...
$b_i=a_1\ OR\ a_2\ OR\ ...\ OR\ a_i$

简单来说， b 数组的第 i 项，就是原数组前 i 个元素进行按位或（OR）运算的结果。

你可以对原数组 a 进行任意次数的重新排列（即改变元素的先后顺序）。

你需要找到一种排列方式，使得按照上述规则生成的前缀按位或数组 b 的字典序最大。

思路：

因为我们需要让前缀或数组 b 的字典序最大，所以我们要尽可能让前面的元素更大。

第一步：为了让 $b_1$ 最大，我们显然应该选择原数组 a 中的最大值作为第一个元素。
第二步：为了让 $b_2$ 最大，在已经确定 $b_1$ 的前提下，我们需要在剩下的元素中寻找一个数，使得它与 $b_1$ 进行按位或运算后的结果最大。
依此类推：在第 k 步，我们在剩余未选择的元素中，寻找一个能使当前前缀或值 cur | a[i] 最大的元素。

按位或运算有一个重要性质：单调不减。即对于任意非负整数 x,y ，都有 x | y >= x。

这意味着，一旦某个二进制位在前缀或中变成了 1，它就永远保持为 1，不会丢失。因此，我们在每一步做出的“局部最优选择”（让当前的或值尽可能大），不仅不会损害后续的选择，反而为后续的元素提供了更大的基础值。这种局部最优必然导致全局最优。

时间复杂度：表面上看是 $O(n^2)$ ，但由于 if (best == -1) break; 的存在，外层循环最多执行约 30 次（因为 $a_i \le 10^9 < 2^{30}$ ）。因此实际时间复杂度为 O(30×n) ，即 O(n) ，非常高效。
空间复杂度： O(n) ，用于存储输入数组、结果数组和访问标记数组。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool vis[200010];
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        memset (vis, 0, sizeof (vis));
        int n;
        scanf ("%d", &n);
        vector <ll> a (n + 1);
        for (int i = 1; i <= n; i++) scanf ("%lld", &a[i]);
        vector <int> res;
        int cur = 0;
        for (int step = 1; step <= n; step++) {
            int best = -1;
            int bestv = cur;
            for (int i = 1; i <= n; i++) {
                if (!vis[i] && (cur | a[i]) > bestv) {
                    bestv = cur | a[i];
                    best = i; 
                }
            }
            if (best == -1) break; 
            vis[best] = true;
            res.push_back (a[best]);
            cur = bestv;
        }
        for (int i = 1; i <= n; i++) {
            if (!vis[i]) res.push_back (a[i]);
        }
        for (int i = 0; i < res.size (); i++) {
            if (i > 0) printf (" ");
            printf ("%d", res[i]);
        }
        printf ("\n");
    }
    return 0;
}

T5:Good Key, Bad Key

链接：****Good Key, Bad Key - 题目详情 - QY code

题意：

你面前有 n 个箱子，排成一排，第 i 个箱子里有 $a_i$ 枚硬币。
你一开始身无分文（硬币余额为 0），也没有钥匙。
你必须严格按照从第 1 个到第 n 个的顺序依次打开所有箱子。
最终目标是：打开所有箱子后，让你手中的硬币余额尽可能多。

每当你准备打开一个箱子时，必须从以下两把钥匙中选择一把（钥匙是一次性的，用完就没了）：

选择“好钥匙”：
- 代价：你需要花费 k 枚硬币来购买这把钥匙（允许余额为负数，即可以先“透支”）。
- 收益：打开箱子，拿走箱子里当前所有的硬币（硬币数量不会因为好钥匙而减少）。
选择“坏钥匙”：
- 代价：免费，不需要花硬币。
- 副作用：在打开当前箱子之前，会触发一个“全局减半”魔法。不仅当前要打开的箱子硬币减半，后面所有还没打开的箱子里的硬币也都会减半（向下取整）。
- 收益：打开箱子，拿走减半后剩下的硬币。

给定箱子的数量 n 、好钥匙的价格 k ，以及每个箱子的初始硬币数 $a_i$ 。请计算并输出：在最优策略下，打开所有箱子后最多能攒下多少枚硬币。

思路：

如果正向思考，使用坏钥匙会影响后面所有的箱子，状态转移会极其复杂。因此，我们采用从后往前（从第 n 个箱子到第 1 个箱子）的逆向 DP。

状态定义：设 dp[c] 表示：在处理完第 i+1 到第 n 个箱子后，如果在到达第 i 个箱子之前，已经使用了 c 次坏钥匙，那么从第 i+1 到第 n 个箱子中能获得的最大硬币总数。

当我们逆向遍历到第 i 个箱子时，当前箱子的原始硬币数为 a[i]。根据前面的状态 dp[c]，我们有两种选择来打开第 i 个箱子：

选择一：使用好钥匙

当前收益：因为之前已经使用了 c 次坏钥匙，所以第 i 个箱子的硬币已经被减半了 c 次，当前硬币数为 a[i] >> c。扣除好钥匙的成本 k ，净收益为 (a[i] >> c) - k。
状态转移：使用好钥匙不会增加坏钥匙的使用次数，所以下一个状态依然是 c 。
转移方程：good = (a[i] >> c) - k + dp[c]

选择二：使用坏钥匙

当前收益：使用坏钥匙不仅不需要花费，还会让当前箱子的硬币再减半一次。所以当前硬币数为 a[i] >> (c + 1)。
状态转移：使用坏钥匙会使后续的坏钥匙使用次数增加 1 次，所以下一个状态变为 c+1 。
转移方程：bad = (a[i] >> (c + 1)) + dp[c + 1]

最终决策：对于每个状态 c ，取两者的最大值：ndp[c] = max(good, bad)。

题目中 $a_i \le 10^9$ ，而 $2^{30}≈10^9$ 。
这意味着，无论一个箱子里有多少硬币，只要连续使用 30 次以上的坏钥匙，该箱子的硬币数必定会变成 0。
因此，在任何一个位置，累计使用的坏钥匙次数 c 都不可能超过 31 次。我们将 DP 数组的大小设为 32，既保证了正确性，又极大地优化了空间和时间。
初始状态：当处理完最后一个箱子（即i=n+1 时），无论之前用了多少次坏钥匙，后续都没有箱子可以开了，收益全为 0。所以初始的 dp 数组全部为 0。
最终答案：当我们逆向处理完第 1 个箱子后，dp[0] 就代表了：在还没有使用任何坏钥匙的情况下，从第 1 个箱子到第 n 个箱子能获得的最大总收益。这正是题目要求的答案。
时间复杂度： $O(30×n)$ 。对于每个箱子，我们只需要枚举 30 多个状态进行转移。
空间复杂度： $O(30)$ 。只需要两个长度为 32 的数组交替使用。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        int n;
        ll k;
        scanf ("%d%lld", &n, &k);
        vector <ll> a (n + 2);
        for (int i = 1; i <= n; i++) scanf ("%lld", &a[i]);
        vector <ll> dp (32, 0);
        for (int i = n; i >= 1; i--) {
            vector <ll> ndp (32, 0);
            for (int c = 0; c < 31; c++) {
                ll good = (a[i] >> c) - k + dp[c];
                ll bad = (a[i] >> (c + 1)) + dp[c + 1];
                ndp[c] = max (good, bad);
            }
            dp = ndp;
        }
        printf ("%lld\n", dp[0]);
    }
    return 0;
}

T6:Kefa and Dishes

链接：****Kefa and Dishes - 题目详情 - QY code

题意：

餐厅菜单上共有 n 道菜，每道菜有一个基础满意度 $a_i$ 。
你需要从中恰好挑选 m 道菜来吃，并且每道菜最多只能吃一次。
最终目标是：安排这 m 道菜的食用顺序，使得获得的总满意度最大。

总满意度由两部分组成：

基础满意度：每吃一道菜，就会获得该菜自带的基础满意度 $a_i$ 。
额外奖励（连击奖励）：共有 k 条特殊规则。如果你吃完第 x 道菜后，紧接着立刻吃第 y 道菜（中间不吃别的菜），就能额外获得 c 点满意度。

给定菜品数量 n 、需要吃的菜品数 m 、特殊规则数 k ，以及每道菜的基础满意度和所有的特殊规则。请输出在最优的选菜和排序策略下，你能获得的最大总满意度。

思路：

因为我们需要从 n 道菜中选出 m 道，并且顺序会影响最终得分（相邻菜品有额外奖励），这本质上是一个带权的最优路径选择问题。

状态定义：设 dp[mask][u] 表示：当前已经吃过的菜品集合为 mask（用二进制位表示），且最后一道吃的是第 u 道菜时，所能获得的最大满意度。

假设当前状态为 dp[mask][u]，我们尝试在下一道菜吃第 v 道菜（前提是 v 还没有被吃过，即 mask 中不包含 v）：

新的菜品集合变为 nmask = mask | (1 << v)。
新的满意度 = 当前满意度 dp[mask][u] + 第 v 道菜的基础满意度 a[v] + 如果存在规则 u -> v 带来的额外满意度 b[u][v]。
转移方程：dp[nmask][v] = max(dp[nmask][v], dp[mask][u] + a[v] + b[u][v])
初始时，我们可以选择任意一道菜作为第一道菜。此时集合中只有这一道菜，且没有前置菜品，所以没有额外奖励。
初始化：对于所有的 u，dp[1 << u][u] = a[u]。
其他状态初始化为负无穷（-INF），表示不可达。

题目要求恰好选择 m 道菜，因此我们不需要看所有状态。

遍历所有的 mask，使用内置函数 __builtin_popcount(mask) 检查其中 1 的个数是否恰好等于 m 。
如果等于 m ，则遍历所有的 u，取 dp[mask][u] 的最大值作为最终答案。
时间复杂度： $O(2^n*n^2)$ 。状态总数为 $2^n*n$ ，每个状态最多向 n 个其他状态转移。当 n=18 时， $2^{18}*18^2≈8.5×10^7$ ，在 C++ 中是可以接受的。
空间复杂度： $O(2^n*n)$ ，用于存储 DP 数组。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll dp[1 << 18][18];
ll b[18][18];
ll a[18];
int n, m, k;
int main () {
    scanf ("%d%d%d", &n, &m, &k);
    for (int i = 0; i < n; i++) scanf ("%lld", &a[i]);
    memset (b, 0, sizeof (b));
    for (int i = 1; i <= k; i++) {
        int x, y;
        ll c;
        scanf ("%d%d%lld", &x, &y, &c);
        x--; y--;
        b[x][y] = c;
    }
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) dp[mask][u] = -INF;
    }
    for (int u = 0; u < n; u++) dp[1 << u][u] = a[u];
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u)) || dp[mask][u] == -INF) continue;
            for (int v = 0; v < n; v++) {
                if ((mask & (1 << v))) continue;
                int nmask = mask | (1 << v);
                dp[nmask][v] = max (dp[nmask][v], dp[mask][u] + a[v] + b[u][v]);
            }
        }
    }
    ll ans = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        if (__builtin_popcount (mask) != m) continue;
        for (int u = 0; u < n; u++) ans = max (ans, dp[mask][u]);
    }
    printf ("%lld\n", ans);
    return 0;
}

8.5总结(昨天只发了讨论，忘发博客了)

今天的考试内容其实难度没有那么难，但是呢我只拿了200分。

考试题目：

情况一：总异或和 pre[n] == 0

情况二：总异或和 pre[n] != 0

3. 复杂度分析

选择一：使用好钥匙

选择二：使用坏钥匙

评论

还没有账户？

登录

情况一：总异或和 `pre[n] == 0`

情况二：总异或和 `pre[n] != 0`