16级第二周寒假作业E题
2024-10-18 03:37:48
Home_W的位运算4
TimeLimit:2000MS MemoryLimit:128MB
64-bit integer IO format:%I64d
Problem Description
给定一个序列 a1,a2……an
求有多少个对l,r(l<=r),满足 al ^ a(l+1) ^ a(l+2) ^…… ^ ar = s,其中^代表按位异或
Input
只有一组数据
第一行是一个整数n
接下来一行有n个整数,分别代表 a1,a2……an
再接下整数q代表查询次数
接来下来有q行,每行是一个整数代表s
其中0<n,s,ai<=10^6
q<=10
Output
对于每个s,输出有多少对l,r满足题目要求
SampleInput
4
2 2 4 1
7
1
2
3
4
5
6
7
SampleOutput
1
2
0
2
2
1
1 思路:由n的范围来确定了暴力是不能解决问题的,所以我们要预处理优化,将s[0]=0,因为0^x=x;
s[1]=s[0]^a1;
s[2]=s[1]^a2;
............
有了预处理以后,我们还要知道一点 al ^ a(l+1) ^ a(l+2) ^…… ^ ar = s则s[r]^s[l]=s;
且s[l]^s=s[r],在这个基础上我们就可以用O(n)遍历每一个s[i],且得到有多少个s[i]^s在预处理的数组里出现过;
也就是我们只要求出对每一个s[i]有几个s[r]满足s[r]^s[l]=s;
下面献上我low逼的代码
时间:748MS | 长度:275 |
scanf("%I64d", &n);
for(i=; i<=n; i++)
{
scanf("%I64d", &s[i]);
s[i]=s[i]^s[i-];///预处理的关键步骤1
z[s[i]]++;///预处理的关键步骤2,且值得注意的是z[0]=1要在循环之前赋值一遍
}
预处理
scanf("%I64d", &s);
for(i=; i<=n; i++)
sum+=z[s[i]^s];
printf("%I64d\n", sum/);///因为s[l]^s=s[r],s[r]^s=s[l];所以用/2可以解决问题;
求和操作
最新文章
- Java列表
- 让div支持placeholder属性/模拟输入框的placeholder属性
- 08-FPGA状态机设计实例——小梅哥FPGA设计思想与验证方法视频教程配套文档
- [Cocos2D-x For WP8]ParallaxNode视差
- wkwebview a target=";_blank"; 打不开链接的解决方案
- TJI读书笔记10-复用类
- Android中的三种XML解析方式
- 微信公众平台开发(84) 小i机器人
- 零零碎碎写的shell脚本(三):一键自动归档压缩脚本
- 在DirectX 中进行2D渲染
- 关于c++中的引用
- python模块之json序列化
- leetcode--014 Gas station
- Windows 2008服务器环境PHP连接SQL Server数据库的配置及连接方法
- OpenCASCADE BRepMesh - 2D Delaunay Triangulation
- bzoj 4538: [Hnoi2016]网络
- 常被问到的十个 Java 面试题
- .net 后台判断是否要替换
- PHP+ajax实现二级联动
- classfication中使用图像金字塔和sliding windows提高准确率
热门文章
- TP中if标签
- Thread的run()与start()的区别
- BZOJ 2109 航空管制(拓扑排序+贪心)
- java执行cmd命令并获取输出结果
- Django 2.0 学习(16):Django ORM 数据库操作(下)
- 【BZOJ4568】幸运数字(线性基,树链剖分,ST表)
- 【BZOJ2460】元素(贪心,线性基)
- POJ.3468 A Simple Problem with Integers(线段树 区间更新 区间查询)
- 【bzoj2006】【NOI2015】超级钢琴
- Subseq