当前位置:网站首页>【集训DAY4】异或【字典树】
【集训DAY4】异或【字典树】
2022-08-09 22:35:00 【VL——MOESR】
思路:
用一个trie,如果当前是位k是0,那就把1的答案加上,然后往0走。如果为1,那就往1走。
c o d e code code
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 2e7 + 10;
int n, k;
long long ans;
int s[MAXN];
int tir[MAXN][2], tot = 1, v[MAXN];
void add(int x) {
int u = 0;
for(int i = 30; i >= 0; i --) {
int g = (x >> i) & 1;
if(!tir[u][g])
tir[u][g] = ++ tot;
u = tir[u][g];
v[u] ++;
}
}
int query_(int x) {
int u = 0, ans1 = 0, sum = 0;
for(int i = 30; i >= 0; i --) {
int g = (x >> i) & 1;
if(sum + (1 << i) >= k) {
ans1 += v[tir[u][g ^ 1]];
u = tir[u][g];
}
else u = tir[u][g ^ 1], sum += (1 << i);
if(!u) break;
}
return ans1;
}
int main() {
scanf("%d%d", &n, &k);
add(0);
for(int i = 1; i <= n; i ++) {
int x;
scanf("%d", &x);
s[i] = s[i - 1] ^ x;
ans += query_(s[i]);
add(s[i]);
}
printf("%lld", ans);
return 0;
}
边栏推荐
- 关于服务治理
- What are the basic steps to develop a quantitative trading strategy?
- Leetcode 530. 二叉搜索树的最小绝对差
- 干货!迈向鲁棒的测试时间适应
- 新增一地公布2022下半年软考报考时间
- 集合运算样例
- k8s部署mysql
- 【JZOF】82二叉树中和为某一值的路径(一)
- Live Preview | ICML 2022 11 first-author scholars share online neural network, graph learning and other cutting-edge research
- 【哲理】读书的意义
猜你喜欢
随机推荐
Live Preview | ICML 2022 11 first-author scholars share online neural network, graph learning and other cutting-edge research
测试2年,当时身边一起入行的朋友已经月薪20k了,自己还没过万,到底差在了哪里?
首席信息官如何将可持续性和技术结合起来
33. Fabric通道、组织、节点、权限间关系
LiveData : Transformations.map和 Transformations.switchMap用法
iNFTnews | 迪士尼如何布局Web3
【诗歌】枕上诗书
金仓数据库 KingbaseGIS 使用手册(6.5. 几何对象编辑函数)
友元类和友元函数
多商户商城系统功能拆解24讲-平台端分销会员
【云原生】一文讲透Kubevela addon如何添加腾讯Crane
全球不用交税的国家,为什么不交
How to know the computer boot record?
如何知道电脑开机记录?
Click: 518. Change Exchange II
2022/8/9 考试总结
Qt 之 QDateEdit 和 QTimeEdit
【mysql】查询今天9点
为什么刀具数据库无法打开?
用函数统计最长单词的字母数量