【每日一题】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";
} 
投递京东等公司10个岗位
