首页 > 其他分享 >abc098d<双指针,异或>

abc098d<双指针,异或>

时间:2024-01-14 17:11:37浏览次数:36  
标签:int abc098d 二进制位 异或 区间 include solv

题目

D - Xor Sum 2
给出n个元素的数组a,求满足条件的子区间个数:数组a子区间元素和与异或和相等。

思路

  • 和与异或和相同,即没有任何进位,也就是区间中对于范围内每个二进制位,最多出现一次;
  • 使用双指针,统计每个二进制位最多出现一次的区间个数即可;

总结

  • 异或:不进位加法;

代码

点击查看代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using LL = long long;

const int N = 2e5 + 10;
int a[N];

void solv()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    LL ans = 0;
    for (int l = 1, r = 0, t = 0; l <= n; l ++)
    {
        while (r + 1 <= n && ((t & a[r + 1]) == 0))
        {
            r ++;
            t |= a[r];
        }
        t ^= a[l];
        ans += r - l + 1;
    }
    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solv();
    return 0;
}

标签:int,abc098d,二进制位,异或,区间,include,solv
From: https://www.cnblogs.com/o2iginal/p/17963918

相关文章

  • [ABC098D] Xor Sum 2 题解
    题解传送门题目大意给出一个序列\(A\),求\(A_l\oplusA_{l+1}\oplus\dots\oplusA_r=A_l+A_{l+1}+\dots+A_r\)(\(\oplus\)即为\(xor\)异或)解析众所周知,异或是位运算中的一种不进位加法,即为如果两个\(bit\)相等返回\(0\),反之返回\(1\)。为什么说是不......