首页 > 试题广场 >

小苯的序列合并

[编程题]小苯的序列合并

热度指数：716 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定长度为 $n$ 的序列 $a$ ，你可以对 $a$ 做如下操作任意次：

$\hspace{23pt}\bullet\$ 选择一个下标 $i\ (1 \leqq i < |a|)$ ，将 $a_i$ 与 $a_{i+1}$ 合并起来，结果为 $a_i\oplus a_{i+1}$ 。（其中 $\oplus$ 表示按位异或运算符， $|a|$ 表示 $a$ 当前的长度。）

$\hspace{15pt}$ 所有操作结束后，小苯希望你最大化最终 $a$ 中所有数字的按位与，即 $\rm AND(\&)$ 值，请你算一下这个最大值是多少吧。

输入描述:

每个测试文件包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行一个正整数 ，表示序列  的长度。
第二行  个非负整数 ，表示序列 。

除此之外，保证同一个测试文件中的  的总和不超过 。

输出描述:

对于每组数据，输出一个整数，表示操作结束后序列  中所有元素按位与的最大值。

示例1

输入

2
6
1 4 5 6 2 9
5
1 1 1 1 1

输出

13
1

算法知识视频讲解

C++

kilomatutinal

这道题好难喵~

猫猫想了好——长时间才想出来喵！

先说结论喵！

无论我们怎么合并数组，最终能得到的最大的按位与值，其实只可能是两种情况的其中一种哦：
1. 整个数组的异或和（就是不合并，直接算所有数字异或的结果喵~）
2. 某个位置分成两段后的“前缀异或”和“后缀异或”的按位与

（就是把数组切成两半，然后分别算异或，再按位与喵~）

是不是觉得很神奇喵？(*ΦωΦ)

下面给你详细解释为什么是这样哒~

解释环节

我们可以把原数组分成好几段，再把这几段全部异或和后，再与运算 喵~

情况1：如果我们只分成一段
喵~那最简单啦！就是整个数组的异或和，代码里已经把这个当作初始值了哦~
情况2：如果我们分成偶数段（比如2段、4段...）
假设最优答案是ans，有k段喵~

因为ans的每个1的位都需要所有段在那个位上都是1。
又因为k是偶数，所以猫猫可以把k个段分为2个部分，每个部分有奇数个段。

因为奇数个1异或还是1喵~所以将两个部分各自进行异或和后，各自结果的1的位肯定拥有ans的每个1的位。

这样的话，前缀和后缀在那个位上都会是1哦！所以两段划分的按位与至少和ans一样好呢！
情况3：如果我们分成奇数段（比如3段、5段...）
这种情况下喵，整个数组的异或和S在所有ans为1的位上都会是1哦！（因为奇数个1异或得1嘛~）
所以S本身就比ans大或者相等啦！也就是说，不切比切更好喵~(๑>ᴗ<๑)

代码在做什么呢？喵~
1. 计算前缀异或：a[i]表示前i个数字的异或和喵~
2. 初始化答案为整个数组的异或和（情况1和3喵~）
3. 枚举所有可能的切分点：看看切在哪里能得到最大的两段按位与喵~
4. 输出最大值：喵呜~完成啦！

时间复杂度才O(n)喵~超级快哒！

主人明白了吗？如果有不懂的地方私信猫猫喵~

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

void solve()
{
    int n;cin >> n;
    vector<ll> a(n+1);
    for(ll i=1;i<=n;i++) cin >> a[i];
    for(ll i=2;i<=n;i++) a[i]^=a[i-1];//前缀异或
    ll ans=a[n];
    for(ll i=0;i<=n;i++) 
        ans=max(ans,a[i]&(a[n]^a[i]));//前缀异或后缀
    cout << ans <<'\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;cin >> t;
    while(t--) solve();
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/

发表于 2026-02-11 01:03:55 回复(4)

Patience019

写题解那几个大佬呢，不要睡啊快出啊

发表于 2026-02-11 01:03:04 回复(1)

提交观点

问题信息

难度：

2条回答 5收藏 103浏览