蓝桥杯2022年第十三届省赛真题-选数异或

solution1（55/100

只保留最后一次的位置，其实有点问题，能骗一点分数

#include<iostream>
#include<map>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int main(){
    int n, m, x, l, r, t, flag;
    map<int, int> mp;
    scanf("%d%d%d", &n, &m, &x);
    for(int i = 1; i <= n; i++){
        scanf("%d", a + i);
        t = a[i] ^ x;
        mp[t] = i;
    }
    while(m--){
        flag = 1;
        scanf("%d%d", &l, &r);
        for(int i = l; i <= r; i++){
            if(mp[a[i]] && mp[a[i]] <= r && mp[a[i]] >= l){
                printf("yes\n");
                flag = 0;
                break;
            }
        }
        if(flag) printf("no\n");
    }
    return 0;
}

solution2（动态规划）

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 10;
int main(){
    int n, m, x, t, num, p[maxn] = {0}, dp[maxn] = {0}, l, r;
    scanf("%d%d%d", &n, &m, &x);
    for(int i = 1; i <= n; i++){
        scanf("%d", &t);
        p[t] = i;
        num = t ^ x;
        dp[i] = max(dp[i -1], p[num]);//每个点的最左配对点 
    }
    while(m--){
        scanf("%d%d", &l, &r);
        if(dp[r] >= l) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}