Count Triplets That Can Form Two Arrays of Equal XOR
2024-09-22 11:12:02
Count Triplets That Can Form Two Arrays of Equal XOR
题意
给定一个数组,求多少个三元对\((i,j,k)\)满足\(S(i,j-1)=S(j,k)\)。
思路
考虑到异或前缀和,很容易想到\(O(n^3)\)的解法,然而远远不够,考虑到\(a=b\)时\(a\oplus b=0\),我们可以找一个区间异或为\(0\)的区间\([i,j]\),在\([i+1,j-1]\)中任找一个数\(k\),都能使\(S(i,k)=S(k+1,j)\),这是因为\(S(i,k)\oplus S(k+1,j)=S(i,j)=0\),故\(S(i,k)=S(k+1,j)\),于是问题又转化成了求有多少个区间异或和为\(0\)的区间,即\(S(i)=S(j)\),很容易想到\(O(n^2)\)的算法。又考虑到\(i\in (i_1,i_2,...,i_m),i<k\),\(S(i,k)=0\),计算每个\(i\)对答案的贡献为\(k-i\),总的就是\(mk-\sum_{j=1}^m i_j\),于是我们考虑用字典存一下前缀和,使用unordered_map,使复杂度降为\(O(n)\)。
AC代码
class Solution {
public:
int countTriplets(vector<int>& arr) {
int len = arr.size(), ans = 0, la = 0;
unordered_map<int, int> cnt, sum;
for (int i = 0; i < len; ++i) {
if (cnt.count(la^arr[i])) {
ans += cnt[la^arr[i]] * i - sum[la^arr[i]];
}
cnt[la]++;
sum[la] += i;
la ^= arr[i];
}
return ans;
}
};
最新文章
- 通过JavaScript改变HTML样式
- 关于JAVA数据储存
- IntelliJ IDEA 12.1.4 解决中文乱码
- Docker源码编译
- Sass用法指南_20151109笔记
- 【Apache运维基础(5)】Apache的Rewrite攻略(2)
- Codeforces Round #347 (Div. 2) B. Rebus
- 转: 解决MSYS2下的中文乱码问题
- Eclipse安装ADT插件
- Razor引擎学习:RenderBody,RenderPage和RenderSection
- 李洪强漫谈iOS开发[C语言-019]-断点调试
- leecode 每日解题思路 127-Factorial Trailing Zeroes
- Merge Two Sorted Lists 解答
- PMP测试实践- 内附PMBOK中字与备考资料
- 3、配置XShell上传文件
- WebLogic使用总结(六)——WebLogic创建虚拟主机和修改启动端口号
- android使用百度地图SDK 去掉百度Logo的小技巧
- mysql ->; 事务&;事务锁_09
- module解析过程
- 会声会影X10x9x8最新教程
热门文章
- AFNI 教程 步骤5:统计和建模
- Pycharm报错:Error running ‘‘: Cannot run program “\python.exe“ (in directory ““)系统找不到指定文件夹?已解决!
- K8S-pod详解
- Ginan-PEA例程下载
- 【记录】Linux Mint Cinnamon Desktop Enviroment使用记录
- python中的数据模型
- laravel常用集合的使用
- ABC136 E - Max GCD 题解
- linux 查询目录文件大小
- oracle WMSYS.WM_CONCAT 函数使用