首页 > 试题广场 >

xor

[编程题]xor
  • 热度指数：102 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
给出n个数字 a_1,...,a_n，问最多有多少不重叠的非空区间，使得每个区间内数字的xor都等于0。

即找出最大的k，使得存在k个区间(l[i], r[i])，满足1<=l[i]<=r[i]<=n (1<=i<=k), r[i]<l[i+1](1<=i<k), 且 a[l[i]] xor a[l[i]+1] xor... xor a[r[i]] = 0 (1<=i<=k)


输入描述:
第一行一个整数ｎ； 第二行ｎ个整数　a_1,...,a_n；  对于30%的数据，n<=20；  对于100%的数据，n<=100000, a_i<=100000；


输出描述:
一个整数表示最多的区间个数；
示例1

输入

4
3 0 2 2

输出

2

说明

[0] xor = 0，[2,2] 2 xor 2 = 0，所以总共是2个不重叠的非空区间
算法知识视频讲解
添加回答
花∠※头像 花∠※
#include<iostream>
#include<vector>
#include<map>
usingnamespacestd;
  
//dp[0~n-1]:从0-i范围上的最优划分的个数
intparition(vector<int> arr)
{
    intlen=arr.size();
    if(len<=0) return-1;
    vector<int> dp(len);
    intans=0;
    intx_or=0;
    //key：某个异或和的值   value：这个异或和最晚出现的位置
    map<int,int> record;
    record[0]=-1;
    for(inti=0;i<len;++i)
    {
        x_or^=arr[i]; //求第i块上的异或和
        if(record.find(x_or)!=record.end())
        {
            intpre_index_last=record[x_or];//上一个异或和最晚出现的位置
            dp[i]=dp[pre_index_last]+1;
        }
          
        if(i>0)
        {
            if(dp[i-1]>dp[i])
                dp[i]=dp[i-1];
        }
        record[x_or]=i;
        if(ans<dp[i])
            ans=dp[i];
    }
    returnans;
}
  
intmain()
{
    vector<int> arr;
    inta;
    while(cin>>a)
    {
        arr.push_back(a);
    }
    intresult= parition(arr);
    cout<<result;
    return0;
}
发表于 2019-06-28 09:57:09 回复(0)
张子寒头像 张子寒

比较复杂的一个解法


public class Main{
    publicstaticvoidmain(String[] args) {
        Scanner sc = newScanner(System.in);
        intn = sc.nextInt();
        intarr[] = newint[n];
        for(inti = 0; i < n; i ++){
            arr[i] = sc.nextInt();
        }
         
        ArrayList<Point> list = newArrayList<Point>();
        for(inti = 0; i < n; i++) {
            intres = 0;
            for(intj = i; j < n; j++) {
                res ^= arr[j];
                if( res == 0){
                    Point pointTmp = newPoint(i, j-i);
                    list.add(pointTmp);
                    break;
                }
            }
        }
        if( list.size() == 0){
            System.out.println(0);
            return;
        }
         
        TreeSet<Point> dpSet = newTreeSet<Point>(newComparator<Point>() {   //点的x为区间右侧，y为最大数量，以y排序
            @Override
            publicintcompare(Point o1, Point o2) {
                if( o1.y == o2.y )
                    returno2.x - o1.x;
                returno1.y - o2.y;
            }
        });
         
        for(Point p : list) {
            intsetSize = dpSet.size();
            if( !dpSet.isEmpty() ){
                for(Point dpTmp = dpSet.last(); dpTmp != null; dpTmp = dpSet.lower(dpTmp)){
                    if( p.x > dpTmp.x){
                        Point newDp = newPoint(p.x + p.y, dpTmp.y + 1);
                        dpSet.add(newDp);
                        break;
                    }
                }
            }
            if(setSize == dpSet.size())
                dpSet.add(newPoint(p.x + p.y, 1));
        }
        System.out.println(dpSet.last().y);
    }

编辑于 2018-11-21 22:04:32 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 哈希 滴滴 贪心 系统工程师 2018 Java工程师
上传者：小小
难度：
2条回答 2670浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号