E. Beautiful Subarrays(Trie维护前缀异或和)-程序员宅基地
思路:看题,不难知道要做前缀和.枚举 r r r,我们需要一种数据结构,得知前缀异或和中有多少 l < r , p r e r ⊕ p r e l − 1 > = k l<r,pre_r\oplus pre_{l-1}>=k l<r,prer⊕prel−1>=k.
前缀异或和,这是一个01Trie树的经典运用.异或和相关的问题可以用Trie01树维护,具体思想就是把一个数字的二进制形式看成01的字符串,每个数字就转化成一个长度为30~60的01字符串.
在这题中,我们从高向低建树,当 k k k的第 i i i位是0时, p r e r ⊕ p r e l − 1 pre_r\oplus pre_{l-1} prer⊕prel−1第 i i i位两个位置都可以取,取0就是继续往Trie树向下走,取1就是立马结算贡献.
当k第i位是1时,显然 p r e r ⊕ p r e l − 1 pre_r\oplus pre_{l-1} prer⊕prel−1只能取1。
式子中 p r e r ⊕ p r e l − 1 pre_r\oplus pre_{l-1} prer⊕prel−1, p r e r pre_r prer事实上是一个定值,根据需要的,取 p r e l − 1 pre_{l-1} prel−1即可,而 p r e l − 1 pre_{l-1} prel−1取值决定了怎么继续向Trie向下走.
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector<int> G[maxn];
//前向星
// for(int i=head[u];i!=-1;i=nxt[i]) v = to[i]
//int nxt[maxn],head[maxn],to[maxn];// head[u],cnt 初始值是-1
//int tot = -1;
//void add(int u,int v){
// nxt[++tot] = head[u];
// head[u] = tot;
// to[tot] = v;
//}
int tr[maxn*30][2];int cnt[maxn*30];int idx = 1;
void insert(int x){
int p = 1;
for(int i=30;i>=0;i--){
int c = (x>>i&1);
if(!tr[p][c]) tr[p][c] = ++idx;
p = tr[p][c];
cnt[p]++;
}
}
int query(int x,int k){
int p = 1;// x is pre_r
int res = 0;
for(int i=30;i>=0;i--){
int c = (x>>i&1);
if(k>>i&1) p = tr[p][c^1];//k是1,pre_r ^ pre_l=1,那么此时c取pre_r相反数字,且不能统计答案,因为还没有确定后续状态
else res+=cnt[tr[p][c^1]],p =tr[p][c];
//k是0,pre_r ^ pre_l可取0可取1,取0继续往下走,取1马上统计出pre_r^pre_l > 1的答案
}
//等于pre_r ^ pre_l == k的情况
res +=cnt[p];
return res;
}
int a[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,k;
cin>>n>>k;
a[0] = 0;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) a[i]^=a[i-1];
ll ans = 0;
for(int i=1;i<=n;i++){
insert(a[i-1]);
ans+=query(a[i],k);
}
cout<<ans;
}
/*
1 1
1
*/
智能推荐
PHP-生成缩略图和添加水印图-学习笔记-程序员宅基地
文章浏览阅读82次。1.开始 在网站上传图片过程，经常用到缩略图功能。这里我自己写了一个图片处理的Image类，能生成缩略图，并且可以添加水印图。2.如何生成缩略图 生成缩略图，关键的是如何计算缩放比率。 这里,我根据图片等比缩放，宽高的几种常见变化，得出一个算缩放比率算法是，使用新图（即缩略图）的宽高，分别除以原图的宽高，看哪个值大，就取它作为缩放比率：...
dyld: Library not loaded: @rpath/libswiftCore.dylib ... Reason: image not found 解决-程序员宅基地
文章浏览阅读2.7k次。在室友Xcode继承一些framework时，爆出了如下错误：dyld: Library not loaded: @rpath/libswiftCore.dylib Referenced from: /private/var/containers/Bundle/Application/1761A6FE-9D6B-45F7-9F9F-922C94BF54A3/demo.app/Framewor..._library not loaded: @rpath/libswiftcore.dylib
linux gvim 快捷键tab,Linux中Vim的常用命令及快捷键-程序员宅基地
文章浏览阅读356次。光标控制命令h或^h向左移一个字符j或^j或^n向下移一行k或^p向上移一行l或空格向右移一个字符G移到文件的最后一行nG移到文件的第n行w..._gvim itab
umi4 项目使用umi-plugin-keep-alive缓存页面(react-activation)-程序员宅基地
文章浏览阅读1k次，点赞12次，收藏10次。按 name 卸载缓存状态下的 节点，name 可选类型为 String 或 RegExp，注意，仅卸载命中 的第一层内容，不会卸载 中嵌套的、未命中的。按 name 刷新缓存状态下的 节点，name 可选类型为 String 或 RegExp，注意，仅刷新命中 的第一层内容，不会刷新 中嵌套的、未命中的。按 name 卸载缓存状态下的 节点，name 可选类型为 String 或 RegExp，将卸载命中 的所有内容，包括 中嵌套的所有。true: 卸载时缓存。获取所有缓存中的节点。_umi-plugin-keep-alive
memory compiler使用流程-程序员宅基地
文章浏览阅读3k次，点赞2次，收藏25次。用了几天的memory compiler，搞清楚了它的使用流程。因为这个软件是不开源的，而且手册又很长，没有快速阅读指南，所以就花了挺多时间学习手册细节，想把其中比较主要的流程记录下来，供大家学习参考。它是一个用来综合一些IP核的软件，它里面各种各样的memory compiler，可以根据自己的选择选中一个，设置好参数之后就能生成想要的参数的memory。 因为每个memory compiler可能工艺不一样，端口数不一样，所以里面有手册告诉你这些细节的。（手册很多，每个手册几百页上下）1、首先就是要安装_memory compiler
Android 读取csv格式数据文件-程序员宅基地
文章浏览阅读5.6k次，点赞5次，收藏16次。前言什么是csv文件呢？百度百科上说 CSV是逗号分隔值文件格式，也有说是电子表格的，既然是电子表格，那么就可以用Excel打开，那为什么要在Android中来读取这个.csv格式的文件呢？因为现在主流数据格式是采用的JSON,但是另一种就是.csv格式的数据，这种数据通常由数据库直接提供，进行读取。下面来看看简单的使用吧正文首先还是先来创建一个项目，名为ReadCSV准备.csv格式的文件，点击和风APILocationList下载ZIP，保存到本地，然后解压，这个时候在你的项目文件中新建_android 读取csv
随便推点
手把手教你安装VSCode（附带图解步骤）_vscode安装包-程序员宅基地
文章浏览阅读3.3w次，点赞38次，收藏158次。前端开发是创建Web页面或app等前端界面呈现给用户的过程，通过HTML，CSS及JavaScript以及衍生出来的各种技术、框架、解决方案，来实现互联网产品的用户界面交互[1]。它从网页制作演变而来，名称上有很明显的时代特征。在互联网的演化进程中，网页制作是Web1.0时代的产物，，用户使用网站的行为也以浏览为主。随着互联网技术的发展和HTML5、CSS3的应用，现代网页更加美观，交互效果显著，功能更加强大。[2]..._vscode安装包
Linux下jar包的运行、查看、终止_linux查看jar包是否运行-程序员宅基地
Linux下使用java -jar命令运行jar包，可通过ctrl + c或关闭窗口停止程序。可以使用pid文件记录jar包的运行进程，方便终止。通过编写启停脚本，可以方便地终止jar包的运行。
英语基本语法_英语基础语法-程序员宅基地
文章浏览阅读1.4w次，点赞8次，收藏40次。1. 名词 名词可以分为专有名词（Proper Nouns）和普通名词 (Common Nouns），专有名词是某个（些）人，地方，机构等专有的名称，如Beijing，China等。普通名词是一类人或东西或是一个抽象概念的名词，如： book，sadness等。普通名词又可分为下面四类： 1）个体名词（Individual Nouns）：表示某类人或东西中的个体，如：gun。 2）集体..._英语基础语法
busybox构建根文件系统_busybox mount-程序员宅基地
文章浏览阅读1.3k次，点赞2次，收藏14次。rootfs有两种格式：nfs方式启动的文件夹形式的rootfs和用来烧录的镜像形式的rootfs。一、busybox移植1、busybox下载busybox是一..._busybox mount
sass-loader版本过高_sass loader-程序员宅基地
文章浏览阅读8.6k次，点赞11次，收藏20次。今天在学习狂神的vue实战上手的时候运行项目就死了，配置了半天终于好了第一个错误：Module build failed: TypeError: loaderContext.getResolve is not a functionsass-loader版本太高 解决:（1和2选一个）修改配置文件，重新安装//1.修改sass-loader的版本为^7.3.1//2.重新安装配置环境npm install卸载当前，重新下载// 卸载当前版本npm uninstall sass_sass loader
C程序设计第五版(谭浩强)-第四章习题_1、什么是算术运算?什么是关系运算?什么是逻辑运算?-程序员宅基地
文章浏览阅读1.7k次，点赞5次，收藏12次。1、什么是算术运算？什么是关系运算？什么是逻辑运算？算术运算：即“四则运算”，是加法、减法、乘法和除法四种运算的统称；关系运算：所谓“关系运算”就是“比较运算”，将两个数值进行比较，判断其比较的结果是否符合给定的条件；逻辑运算：逻辑运算又称布尔运算，有与、或、非三种基本逻辑运算；2、C语言中如何表示“真”和“假”？系统如何判断一个量的“真”和“假”？C语言编译系统在表示逻辑运算结..._1、什么是算术运算?什么是关系运算?什么是逻辑运算?