电子商务网站 备案,js博客网站开发计划书,个人网站整站下载,wordpress 随机一句话文章目录题目描述题解#xff1a;代码#xff1a;扩展传送时间限制#xff1a;C/C 2秒#xff0c;其他语言4秒 空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K 64bit IO Format:%lld 题目描述 给定一个长度为n的整数数组#xff0c;问有多少对互不重叠的非空区…
文章目录题目描述题解代码扩展传送时间限制C/C 2秒其他语言4秒 空间限制C/C 32768K其他语言65536K 64bit IO Format:%lld 题目描述 给定一个长度为n的整数数组问有多少对互不重叠的非空区间使得两个区间内的数的异或和为0。 输入描述: 第一行一个数n表示数组长度 第二行n个整数表示数组 1n1000,0数组元素100000。 输出描述: 一行一个整数表示答案。 示例1 输入
3
0 0 0输出
5说明 ([1,1],[2,2]),([1,1],[3,3]),([1,1],[2,3]),([1,2],[3,3]),([2,2],[3,3])
题解
枚举TLE√ 暴力肯定过不了我们可以先考虑只枚举一个区间[x,y]这个区间可以通过前缀异或和得到。pre来存前缀 我们用[x,y]表示右边的区间题目要求左右区间异或和为0也就是问[x,y]左边有多少和它值一样的区间。 我们可以用a[i]来存a[i]表示左边异或和为i区间个数数组a反应的数量i反映的是值。 先将区间[k,i]存进a中再用a[ ]来查看左边有多少区间异或和值与右区间[i1 , j]值相同。 因为a存的是数量所以直接用ansa [ pre[i] ^ [j] ]
代码
#includebits/stdc.h
using namespace std;
const int maxn1e73;
int a[maxn];
int pre[maxn];int x;int n;
long long ans0;
int main()
{cinn;for(int i1;in;i){cinx;pre[i]pre[i-1]^x;}for(int i1;in;i){for(int k0;ki;k) a[pre[i]^pre[k]];//for(int ji1;jn;j) ans a[pre[i]^pre[j]];//}coutans;return 0;
}扩展
关于异或的题我最近做了个 CF282E Sausage Maximization 牛客网题目链接 异或的题解法挺新颖不过不知道为什么牛客网这里不能 提交 原题是cf的cf题目链接 我自己写的题解
