【每日一题】Xorto

Xorto

http://www.nowcoder.com/questionTerminal/87b8d98e741b457da1df1537a64719eb

Solution

(用表示异或运算)

因为当且仅当时才有,所以题目要求的就是有多少对区间的异或和相等且不重叠。

为右端点小于且异或和为的区间的个数,此时,若区间的异或和为,那么它对答案的贡献为

枚举,首先对所有左端点为的区间计算贡献,然后利用右端点为的区间来更新

总复杂度

Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int a[1005], sum[1 << 17];
vector<int> add[1005], query[1005];

int main() {
  cin.sync_with_stdio(false), cin.tie(nullptr);

  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int l = 1; l <= n; l++) {
    int xorsum = 0;
    for (int r = l; r <= n; r++) {
      xorsum ^= a[r];
      add[r].push_back(xorsum);
      query[l].push_back(xorsum);
    }
  }
  ll res = 0;
  for (int i = 1; i <= n; i++) {
    for (auto v : query[i]) {
      res += sum[v];
    }
    for (auto v : add[i]) {
      ++sum[v];
    }
  }
  cout << res << "\n";
}
全部评论

相关推荐

07-25 11:12
重庆大学 C++
既然这么缺人,为什么挂我呢
希望被offer砸中...:其实不缺人
点赞 评论 收藏
分享
07-21 18:43
门头沟学院 Java
是暑期都招满了吗
ANEOY:今年感觉真是后端地狱级难度了,从暑期就是这样,前端需求非常大
点赞 评论 收藏
分享
码砖:求职岗位要突出,一眼就能看到,教育背景放到最后,学校经历没那么重要,项目要重点突出
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务