两句话

用户名：uq_42709742140

访问量：2027

签　名：

等　　级
排　　名	3005
经　　验	1992
参赛次数	0
文章发表	36
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

2604: 蓝桥杯2021年真题-砝码称重（unordered_set）
浏览：119

2659: 蓝桥杯2022年真题-统计子矩阵（前缀和二维变一维）
浏览：51

2666: 蓝桥杯2022年真题-爬树的甲壳虫（逆元及递推公式）
浏览：90

你可能喜欢

3147: 蓝桥杯2023年第十四届省赛真题-异或和之和（C++）

　　作者: 两句话　　　　发表时间：2024-03-24 00:10:25 浏览：268　|　评论：2　

原题链接：蓝桥杯2023年第十四届省赛真题-异或和之和

**阅读理解：**
一开始以为题目所说的[l,r]异或和是指范围内的数两两异或再求和，但是其实是范围内的所有数求异或(和)，最后把所有范围的结果加起来求和。
**联想到异或和的前缀和数组：**
1 ~ i 内的所有数求异或和，即：s[i] = s[i - 1] ^ a[i]，若要求i ~ j 间的所有数求异或，则**只需要求s[i-1]^s[j]**，就将1 ~ i-1 范围内的异或“去掉了”，因为该范围内的数在s[i-1]和s[j]中份别包含了一次，共两次，且x ^ x = 0，对后续没有影响，即sum += s[j] ^ s[i - 1]。因此**第一步先求异或和的前缀和数组**。
#暴力求解（60%）：
本题中60%数据量较小，如果直接暴力求解也可以拿一大半的分数，所以初步暴力法直接求解，代码如下：
```cpp
#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int n;
int a[N] , s[N];

int main()
{
    cin>>n;
    for(int i = 1;i <= n;i ++)
       cin>>a[i];
	   
    for(int i = 1;i <= n;i ++)	//求异或前缀和数组
       s[i] = s[i - 1] ^ a[i];

long long sum = 0;
    for(int i = 1;i <= n;i ++)
        for(int j = i;j <= n;j ++)
            sum += s[j] ^ s[i - 1];

cout<<sum<<endl;
    return 0;
}

```
#优化时间：
**技巧：异或计算中好像经常出现按位考虑计算（考虑0/1的个数）**

**为了降低时间复杂度，需要对代码进一步优化：**
所有i ~ j 的异或和之和求的是所有s[i - 1] ^ s[j]的和，但是如果让i和j分别遍历1 ~ n 时间复杂度就是O(n×n),肯定会超时，所以选择将数字用二进制位表示，遍历结果ans的每一位进行求解。

**统计0/1的个数：**
异或结果要么为0要么为1，不存在进位，所以ans第k位上的值是多少只与s[i-1]到s[j]中所有数的第k位放在一起，统计第k位里面0和1的个数。

**以样例为例：**
s[0] = 0 = 0 0 0 0
s[1] = 1 = 0 0 0 1
s[2] = 3 = 0 0 1 1
s[3] = 0 = 0 0 0 0
s[4] = 4 = 0 1 0 0
s[5] = 1 = 0 0 0 1
等号右边右起第0列，也就是第k=0位上，共有3个1和3个0 ，任意一个1和任意一个0异或得到1；
因为题目要求的是 “求其**每个子段**的异或和” ，所以每个s[i]和s[j]都有可能组合在一起;
则结果的第k位 = 3 × 3 × 2^k；（3 × 3种组合出1的方式 ，第k位为1时，结果要乘以2^k）

**大佬的具体证明链接：**https://blog.csdn.net/Game14641/article/details/131499627
#最终代码：
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long LL;

const int N = 1e5 + 10;
LL a[N], s[N] , cnt[N][2];  //在第N位上i（0/1）的个数
int n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] ^ a[i];

LL ans = 0;

for(int j = 20;j >= 0;j --)
    {
        for(int i = 0;i <= n;i ++)
        {
            if (s[i] >> j & 1) cnt[j][1] ++; //s[i]的第j位是1
            else cnt[j][0] ++;
        }
    }
    
    for(int i = 0;i < 21;i ++)
        ans += cnt[i][0] * cnt[i][1] * (1 << i);

cout << ans << endl;

return 0;
}
```

0.0分

7 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

努力学编程

牛逼

2024-04-05 18:30:25

青白

思路清晰，大佬牛逼

2024-04-04 12:46:35

两句话

TA的其他文章

你可能喜欢

统计字符（C语言描述运用ctype.h）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

3147: 蓝桥杯2023年第十四届省赛真题-异或和之和（C++）

评论区

精彩推荐

A+B for Input-Output Practice (V) （C语言代码）

哥德巴赫曾猜测（C语言代码）

【蟠桃记】（C语言代码）

DNA （C语言代码）

Tom数（C语言代码）

1050题解（结构体数组与结构体指针的使用）

C语言训练-亲密数（C语言描述,反正怎么都能对）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

两句话

TA的其他文章

你可能喜欢

统计字符 （C语言描述运用ctype.h）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

3147: 蓝桥杯2023年第十四届省赛真题-异或和之和（C++）

评论区

精彩推荐

A+B for Input-Output Practice (V) （C语言代码）

哥德巴赫曾猜测 （C语言代码）

【蟠桃记】 （C语言代码）

DNA （C语言代码）

Tom数 （C语言代码）

1050题解（结构体数组与结构体指针的使用）

C语言训练-亲密数 （C语言描述,反正怎么都能对）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

统计字符（C语言描述运用ctype.h）

　　评论区

哥德巴赫曾猜测（C语言代码）

【蟠桃记】（C语言代码）

Tom数（C语言代码）

C语言训练-亲密数（C语言描述,反正怎么都能对）