首页 > 其他分享 >acwing 4645. 选数异或

acwing 4645. 选数异或

时间:2023-05-06 23:13:36浏览次数:41  
标签:下标 数字 int 选数 4645 异或 数组 last

 输出yes

  no

  yes 

  no

题意分析,给一串数组,再在每次提问时给出一个区间,l,r;

求l,r区间内是否存在两个数,两数异或后值为给出的x;

已知a^b=x-->a^x=b;

思路:1,把每个数异或x,存在另一个数组(b)里,暴力搜索,看区间内b数组内数字是否有等于a数组内数字,TLE

  2.记录下标,比较每个位置数字可异或为的数字(若存在)的下标,建立数组last[a[i]]记录每个数字(a[i])在原数组内的下标。

  g[i]=max(g[i-1],last[a[i]^x])//g[i]=j,存储的是每个位置往左,是否存在它的值异或后的数,若有存它的异或后值的下标,若没有则保存它左边有异或对的下标(靠左边的那个,因为若是右边的就保存在分析右边数字的记录中,所以肯定是左边的)

代码:

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],last[(1<<20)+10],g[N];
int main(){
    int n,m,x,l,r;
    cin>>n>>m>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        g[i]=max(g[i-1],last[a[i]^x]);
        last[a[i]]=i;
    }
    for(int i=1;i<=m;i++){
        cin>>l>>r;
        if(l<=g[r]){
            cout<<"yes"<<endl;
        }else{
            cout<<"no"<<endl;
        }
        
    }
    return 0;
}

 

标签:下标,数字,int,选数,4645,异或,数组,last
From: https://www.cnblogs.com/killjoyskr/p/17378663.html

相关文章

  • 异或的一些性质
    //异或(不进位加法)0110^1100=1010//相同为0,不同为1//A^A=0//(性质1)A^0=A//(性质2)//一序列相加和异或的值的奇偶性相同a+b+c=d;a^b^c=e;<==>d%2==e%2//奇偶性相同(性质3)<==>d>=e//和值一定大于等于异或......
  • CF1325D(异或构造)1700
    原题链接题目大意:给定整数u和v(0\(\leq\)u,v\(\leq\)\(10^{18}\))试构造长度最短的数组,使得数组内所有元素的异或和为u,加和为v。如果有解,输出两行,第一行输出一个整数n,第二行输出n个非负整数,表示数组里的元素。多解输出任意一组即可。如果无解,输出一行一个整数−1。......
  • 异或:计算整数0~5的累计异或的3种方式
      #示例10-11计算整数0~5的累计异或的3种方式importfunctoolsimportoperator#方法1:n=0foriinrange(1,6):n^=iprint(n)#方法2:x1=functools.reduce(lambdaa,b:a^b,range(6))print(x1)#方法3:x2=functools.reduce(operator.xor,ra......
  • odoo wizard界面显示带复选框列表及勾选数据获取
    实践环境Odoo14.0-20221212(CommunityEdition)需求描述如下图(非实际项目界面截图,仅用于介绍本文主题),打开记录详情页(form视图),点击某个按钮(图中的"选取ffers"按钮),弹出一个向导(wizard)界面,并将详情页中内联tree视图("Offers"Tab页)的列表记录展示到向导界面,且要支持复选框,用......
  • hihoCoder Challenge 28 异或问题 思维
    Givenasequencea[1..n],youneedtocalculatehowmanyintegersSsatisfythefollowingconditions:(1).0≤S<260(2).Foreveryiin[1,n-1],(a[i]xorS)≤(a[i+1]xorS)InputOnthefirstlinethereisonlyoneintegernOnthesecondlinethere......
  • [P8766 [蓝桥杯 2021 国 AB] 异或三角]题解
    P8766[蓝桥杯2021国AB]异或三角题目描述分析题目中给出了三个限制首先我们不妨设\(a,b\ltc\),则而由于我们把\(c\)作为了最大值,原题需要有序对\((a,b,c)\)所以\(ans\ast3\)1.\(1\leqa,b,c\leqn\)2.\(a\oplusb\oplusc=0\)3.\(a+b\gtc\)而在枚举过程中,......
  • 异或运算
    基本概念异或运算:想同为0,不同为1同或运算:想同为1,不同为0即无进位相加性质0^N==NN^N==0异或运算满足交换律和结合率即:a^b=b^a(a^b)^c=a^(b^c)题一、如何不同额外变量交换两个数inta=a^bintb=a^binta=a^b题二、一个数组中有一种数出现奇数次//arr中,只有一......
  • 为何vs编译边出来的程序ebp-4存放的不是第一个局部变量?而是security_cookie——本质上
    快速识别 最后那个call就是比较存的随机数和ebp异或的值是否和之前是否一样:    探究security_cookie在程序中的作用 from:https://www.kn0sky.com/?p=66学习环境:Windows1020H2+VisualStudio2019前言在学习看反汇编程序的时候,使用VS2019编译的releas......
  • 1835. 所有数对按位与结果的异或和
    题目描述给了列表异或和的定义现在的列表是arr1和arr2构造出来的,元素对是arr[i]andarr[j]问以上列表的异或和?f1-依次确定答案的每一位基本分析为什么考虑计算答案的每一位?表达式只包含位运算(按位与和按位异或)具体怎么计算?要知道答案的第k为是1还是0->分别计算arr1和arr......
  • UVa 11507 Bender B. Rodríguez Problem (模拟&异或)
    11507-BenderB.RodríguezProblemTimelimit:4.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2502Benderisarobotbuiltby Mom'sFriendlyRobotCompany atits......