[CSP-J 2025] 异或和

OJ: luogu

题目 ID: P14359

标签: 贪心枚举数学

日期: 2026-02-04 09:00

题目解析

代码

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;
}