【篮球杯】选数异或

今天药忘吃喽~ 2024-03-26 17:44 70阅读 0赞

**篮球杯，hard**

**考场上我肯定只能写暴力**

[4645. 选数异或 - AcWing题库][4645. _ - AcWing]

题意：

![c46404522a866035c76030bd487e9590.png][]

思路：

注意到有两个指针a,b，我们考虑枚举其中一个指针，然后去考虑全局哈希来得出另一个指针

但是无法直接得出另一个指针

考虑去check离r最近的指针p，使得区间\[p,r\]中存在一对数对使a^b=x

即a\[p\]^a\[r\]=x

那怎么去维护这个指针

注意到异或的性质：

a^b=x

那么b^x=a

即，我们枚举b的时候，a就已经确定了

那么，既然a确定了，我们要求的是离r最近的一个确定的数

那么开一个map last\[x\]，表示离x最近的数是多少

这样大致就做完了

Code：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <queue>
    #include <set>
    #define int long long
    using namespace std;
    using i64 = long long;
    const int mxn=1e5+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    
    unordered_map<int,int> last;
    int n,m,x,l,r;
    int a[mxn],dp[mxn];
    void solve(){
        cin>>n>>m>>x;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++){
            dp[i]=max(dp[i-1],last[x^a[i]]);
            last[a[i]]=i;
        }
        while(m--){
            cin>>l>>r;
            if(dp[r]>=l) cout<<"yes"<<'\n';
            else cout<<"no"<<'\n';
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[4645. _ - AcWing]: https://www.acwing.com/problem/content/4648/
[c46404522a866035c76030bd487e9590.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/c32c56803e5b4498a3f46f0360058fb4.png

发表评论取消回复

表情：

评论列表（有 0 条评论，70人围观）

还没有评论，来说两句吧...

相关阅读

相关 JAVA使用异或交换两个数

//交换两数 //两个相同的数异或之后结果会等于0，即 n ^ n = 0。并且任何数与 0 异或等于它本身，即 n ^ 0 = n int n

桃扇骨/ 2024年04月03日 12:17/ 0 赞/ 62 阅读

相关【篮球杯】选数异或

篮球杯，hard 考场上我肯定只能写暴力 [4645. 选数异或 - AcWing题库][4645. _ - AcWing] 题意： ![c46404522a86603

今天药忘吃喽~/ 2024年03月26日 17:44/ 0 赞/ 71 阅读

相关【篮球杯】二分青蛙过河

日常二分不会check，很寄啊，感觉这道题好难，考场肯定做不出来的题意： ![4039fb6f6249f47d8d613a645f720dde.png][] 思路：

妖狐艹你老母/ 2024年03月26日 16:19/ 0 赞/ 98 阅读

相关篮球杯双指针专题

总的来说，双指针分为while(1)类型和尺取法类型可以解决各种问题,前提是满足单调性（如子序列问题） [活动 - AcWing][- AcWing] ![b213d6

绝地灬酷狼/ 2024年03月26日 14:38/ 0 赞/ 89 阅读

相关篮球杯DP 数组切分

![3d02e6c22d80a8c14ded13015df9585d.png][] 思路：数组划分型DP 基本形式就是：先去枚举右端点r，再去枚举左端点l 当区间

客官°小女子只卖身不卖艺/ 2024年03月26日 14:37/ 0 赞/ 96 阅读

相关【篮球杯日期处理】跑步锻炼

最讨厌最不会的就是日期为什么人类要把日期定义的这么复杂QwQ [跑步锻炼 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn] 题意： ![95

骑猪看日落/ 2024年03月25日 13:28/ 0 赞/ 93 阅读

相关篮球杯 Day2

一些我不会的简单题集锦感觉篮球杯很容易错啊考场应该就是，先去想正解思路，想出来了就写想不出来就想怎么暴力，然后按小的数据范围写暴力考虑暴力的时候，先去考虑枚举的

我不是女神ヾ/ 2024年03月25日 10:57/ 0 赞/ 80 阅读

相关【篮球杯 DP+数论】包子凑数

hard [AcWing 1226. 包子凑数 - AcWing][AcWing 1226. _ - AcWing] 题意： ![0f94025a58d2221aedda

小鱼儿/ 2024年03月25日 06:16/ 0 赞/ 49 阅读

相关异或运算符

/ ^的特点：a 异或 b 两次得到的还是 a。 / class OperatorDemo{ public static void main(S

桃扇骨/ 2022年05月22日 06:41/ 0 赞/ 230 阅读

相关 C语言之数组数字异或

接着上次我们讨论的在一组数字中找出一个只出现一次的数，这次我们加大难度，在一组数字中找出两个只出现一次出现一次的数字。题目具体内容如下：一个数组中只有两个数字是出现一次

落日映苍穹つ/ 2022年03月21日 08:46/ 0 赞/ 222 阅读