题目解析
代码
60分
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* date: 2026-02-04 09:00:18
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 2e6+5;
int n,k;
int a[maxn];
void init(){
std::cin >> n;
std::cin >> k;
for(int i = 1;i <= n ;++i ) // i: 1->n
{
std::cin >> a[i];
}
}
int xor_sum(int l,int r){
int ans = 0;
for(int i = l;i <= r ;++i ) // i: l->r
{
ans = ans ^ a[i];
}
return ans;
}
signed main () {
ios::sync_with_stdio(false); cin.tie(0);
init();
int tot = 0;
int start = 1;
// 结尾
for(int i = 1;i <= n ;++i ) // i: 1->n
{
bool flag = 0;
int ans = 0;
for(int j = start;j<=i;j++) {
ans = ans ^ a[j];
if( ans == k) {
flag = 1;
start = i+1;
break;
}
}
if( flag == 1) {
tot++;
}
}
std::cout << tot << "\n";
return 0;
}
90分,使用memset+桶,TLE
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* date: 2026-02-04 09:00:18
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 2e6+5;
int n,k;
int a[maxn];
int b[(1<<20)+1]; //桶
void init(){
std::cin >> n;
std::cin >> k;
for(int i = 1;i <= n ;++i ) // i: 1->n
{
std::cin >> a[i];
}
}
int xor_sum(int l,int r){
int ans = 0;
for(int i = l;i <= r ;++i ) // i: l->r
{
ans = ans ^ a[i];
}
return ans;
}
signed main () {
ios::sync_with_stdio(false); cin.tie(0);
init();
int tot = 0;
int start = 1;
// 结尾
b[0] = 1;
int pre_sum = 0;
for(int i = 1;i <= n ;++i ) // i: 1->n
{
pre_sum = pre_sum ^ a[i];
int s1 = pre_sum ^ k;
if( b[s1] == 1) {
// cout << "ok ---> \n";
// cout << "i: " << i << endl;
pre_sum = 0;
memset(b,0,sizeof(b));
b[0]=1;
tot++;
}
else b[pre_sum] = 1;
}
std::cout << tot << "\n";
return 0;
}
100分, 使用 std::map
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* date: 2026-02-04 09:00:18
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 2e6+5;
int n,k;
int a[maxn];
// int b[maxn]; //桶
std::map<int,int> b;
void init(){
std::cin >> n;
std::cin >> k;
for(int i = 1;i <= n ;++i ) // i: 1->n
{
std::cin >> a[i];
}
}
int xor_sum(int l,int r){
int ans = 0;
for(int i = l;i <= r ;++i ) // i: l->r
{
ans = ans ^ a[i];
}
return ans;
}
signed main () {
ios::sync_with_stdio(false); cin.tie(0);
init();
int tot = 0;
int start = 1;
// 结尾
b[0] = 1;
int pre_sum = 0;
for(int i = 1;i <= n ;++i ) // i: 1->n
{
pre_sum = pre_sum ^ a[i];
int s1 = pre_sum ^ k;
if( b[s1] == 1) {
// cout << "ok ---> \n";
// cout << "i: " << i << endl;
pre_sum = 0;
b.clear();
b[0]=1;
tot++;
}
else b[pre_sum] = 1;
}
std::cout << tot << "\n";
return 0;
}
100分, 带时间戳的桶
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1 << 20; // 2^20 = 1048576
int vis[MAXV]; // 时间戳数组
int cur = 1; // 当前时间戳
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
int pre = 0; // 前缀异或和
int ans = 0; // 答案
vis[0] = cur; // 初始前缀异或和0出现过
for (int i = 1; i <= n; ++i) {
pre ^= a[i];
int target = pre ^ k;
if (vis[target] == cur) { // 之前出现过 target
ans++;
cur++; // 时间戳增加,相当于清空vis
pre = 0;
vis[0] = cur; // 重新开始
} else {
vis[pre] = cur;
}
}
cout << ans << "\n";
return 0;
}