竞赛讨论区 > 【每日一题】1月8日题目精讲

【每日一题】1月8日题目精讲

头像
王清楚
编辑于 2021-01-08 11:06:01 APP内打开
赞 0 | 收藏 0 | 回复5 | 浏览468

题号 NC111446
名称 Beautiful Subarrays
来源 CF665E
戳我进入往期每日一题汇总贴~
往期每日一题二期题单

图片说明

如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿,投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励,可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

所以我们可以先求一遍异或前缀和,然后再通过枚举右端点,去查找有多少个左端点符合要求。

假设我们当前枚举到这个位置,前个数的异或前缀和是,我们要查找异或值大于等于的,

这里我们可以去找一个,满足,这个时候大于等于的数就是满足要求的数了,

这个操作我们可以通过一颗树来实现。

分四种情况:

  • a 的当前位二进制数是0,k的当前位二进制数也是0,如果我们选择一个数的当前位是1,

    与a异或之后会变大,的位对答案有贡献,所以我们加上答案,然后到当前位上是0的地方去继续寻找。

  • a的当前位二进制数是0, k的当前位二进制数是1,我们要使查找值不变小,一定要到当前位是1上去找,这个时候的位对答案是没有贡献。

  • a的当前位二进制数是1, k的当前位二进制数是0,如果我们选择,异或结果变大,的位对答案有贡献,所以加上答案,

    走到当前位是1的地方去继续寻找答案。

  • a的当前位二进制数是1, k的当前位二进制也是1,这个时候要保证异或结果不变小,只能到当前位是0的地方去寻找。

最后再特判一下刚好相等的情况就OK了。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 4e7 + 10;

int trie[N][2], tot, num[N];

void insert(int x) {
  int rt = 0;
  for(int i = 30; i >= 0; i--) {
    int now = x >> i & 1;
    if(!trie[rt][now]) {
      trie[rt][now] = ++tot;
    }
    rt = trie[rt][now];
    num[rt]++;
  }
}

int find(int a, int b) {
  int ans = 0, rt = 0;
  for(int i = 30; i >= 0; i--) {
    int u = a >> i & 1, v = b >> i & 1;
    if(!u) {
      if(v) {
        if(!trie[rt][1]) return ans;
        rt = trie[rt][1];
      }
      else {
        ans += num[trie[rt][1]];
        if(!trie[rt][0]) return ans;
        rt = trie[rt][0];
      }
    }
    else {
      if(!v) {
        ans += num[trie[rt][0]];
        if(!trie[rt][1]) return ans;
        rt = trie[rt][1];
      }
      else {
        if(!trie[rt][0]) return ans;
        rt = trie[rt][0];
      }
    }
  }
  return ans + num[rt];
}

const int N1 = 1e6 + 10;

int a[N1], n, k;

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  scanf("%d %d", &n, &k);
  for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    a[i] ^= a[i - 1];
  }
  insert(0);
  ll ans = 0;
  for(int i = 1; i <= n; i++) {
    int temp = find(a[i], k);
    ans += temp;
    insert(a[i]);
  }
  printf("%lld\n", ans);
  return 0;
}

欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目1月14日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

5条回帖

回帖
加载中...
话题 回帖

本文相关内容

近期热帖

等你来战

查看全部

热门推荐