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

616 阅读 0 评论 1 点赞

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

##暴力求解（40%）：
```cpp
#include<iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
LL a[N] , s[N] , ans = 0 , sum = 0;
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],cout<<s[i]<<endl;;
    
    LL maxx , minn;
    maxx = minn = s[0] ^ s[1];
    
    for(int i = 1;i <= n;i ++)
    {
        
        for(int j = i;j <= n;j ++)
        {
            sum = s[i-1] ^ s[j];
            minn = min(minn , sum);
            maxx = max(maxx , sum);
            cout<<sum<<' ';
        }
        cout<<endl;
    }
    
    ans = maxx - minn;
    cout<<ans<<endl;
        
    
    return 0;
}
```
##时间优化
**利用trie树的特性寻找异或的最大最小值：**

**trie树知识点：**https://www.acwing.com/blog/content/15077/

**一位大佬的代码思路讲解：**https://www.bilibili.com/video/BV1ty421z77K/?spm_id_from=333.788&vd_source=5f7e4c928f2ae7a33f99f74c695f9806
##最终代码：
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std ;
const int N = 1e6 + 10 ;

int  n , a[N] ; 
int son[2][N] , idx ; 
int mx[N] , mi[N] ;

void add(int x)
{
    int p = 0 ; 
    for(int i = 20 ; i >= 0 ; i --)
    {
        int u = (x>>i) & 1; //判断x的第i位上是1/0
        if(!son[u][p]) son[u][p] = ++idx;   //若节点不存在，则按照当前位置上的数是多少来构造树
        p = son[u][p];  //指向构造好的节点准备构造下一位
    }
}

int query_mx(int x)
{//异或值最大则需要尽可能多【不相同】的位数
    int p = 0 , res = 0;
    for(int i = 20;i >= 0;i --)
    {
        int u = (x >> i) & 1;
        if(son[!u][p])  res |= (1 << i);
        else u = !u;
        
        p = son[!u][p];
    }
    return res;
}

int query_mi(int x)
{//异或值最小则需要尽可能多【相同】的位数
    int p = 0 , res = 0;
    for(int i = 20;i >= 0;i --)
    {
        int u = (x >> i) & 1;
        if(!son[u][p])  //若与当前位相同的节点不存在，则最小异或
        {
            u = !u;
            res |= (1 << i);
        }
        p = son[u][p];
    }
    return res;
}

int main()
{
    cin>>n;
    for(int i = 1;i <= n;i ++)  cin>>a[i];
    
    mx[0] = 0 , mi[0] = 1e9;
    int sum = 0;
    add(sum);
    
    for(int i = 1;i <= n;i ++)
    {//寻找i左边的异或和最大值和最小值
        sum ^= a[i];	//前缀和
        mx[i] = max(mx[i-1] , query_mx(sum));	//动态规划，i左边的最大值=i-1左边的最大值（不包括i）和以i为右端点（包括i）的最大值
        mi[i] = min(mi[i-1] , query_mi(sum));
        add(sum);	//构造树
    }
    
    memset(son , 0 , sizeof son) ; 
    idx = 0 ; sum = 0 ;

int ans = 0 , mx2 = 0 , mi2 = 2e9; 
    add(sum) ; 
    for(int i = n ; i ; i --)
    {//寻找i右边的异或和最大值和最小值（倒序）
        sum ^= a[i] ; 
        mx2 = max(mx2 , query_mx(sum)) ; //同上
        mi2 = min(mi2 , query_mi(sum)) ; 
		//取（ans ， 右最大-左最小 ， 左最大-右最小）的最大值
        ans = max({ans , mx[i - 1] - mi2 , mx2 - mi[i - 1]}) ; 
        add(sum) ; 
    }
    
    cout<<ans<<endl;
    return 0;
}
```

0.0分

1 人评分

本文分类：题解列表
浏览次数：616 次浏览
发布日期：2024-03-24 14:23:01
本文链接：https://blog.dotcpp.com/a/103774

上一篇 > 2236: 蓝桥杯算法训练-大小写转换
下一篇 > 辗转相除法求最小公倍数

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

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

评论列表共有 0 条评论

发表评论取消回复

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

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复