【每日一题】Xorto

Xorto

http://www.nowcoder.com/questionTerminal/87b8d98e741b457da1df1537a64719eb

首先只有两个相同的数异或结果才可能为0即两个非重叠区间异或和应该相同
而求一个区间[l,r]的异或和可以用前缀异或和求得即sum[r]^sum[l-1]
然后枚举一个区间[x,y],规定这个区间[x,y]为右区间,固定右区间的左键为i,那么区间右键可以为i+1,i+2......,n,那么只要左区间的异或和等于右区间且左区间的右键小于x就可以了,每次循环更新以i-1位右键的所有异或和出现次数,因此计算[x,y]为右区间时的有几个左区间满足就是[x,y]这个区间的异或和之前出现的次数

#include <cstdio> 
#include <map>
using namespace std;
const int N = 1e3+10;
map<int,int> mp; 
typedef long long ll;
int n,sum[N];
ll ans;
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
        scanf("%d",sum+i);
        sum[i] ^= sum[i-1];
    }
    for(int i = 1;i <= n;i++){
        for(int j = i;j <= n;j++){
            ans+=mp[sum[i-1]^sum[j]];
        }
        for(int j = 0;j < i;j++){
            mp[sum[i]^sum[j]]++;
        }
    }
    printf("%lld\n",ans);
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 12:10
点赞 评论 收藏
分享
05-16 11:16
已编辑
东华理工大学 Java
牛客73769814...:盲猜几十人小公司,庙小妖风大,咋不叫她去4️⃣呢😁
牛客创作赏金赛
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-09 11:30
找工作7个月,投了7000封,3段世界五百强实习,才有一个offer,牛油们肯定比我强吧
码农索隆:不对不对不对,实习经历这么厉害,简历也没少投,问题出在哪呢
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务