• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

位运算好题

开发技术 开发技术 1周前 (05-04) 10次浏览

位运算太有趣辣!

 

Luogu P7442 「EZEC-7」维护序列

你需要维护一个序列。

这个序列开始时有 2n 个数,下标从 0 开始。第 i 个数初始值为 i,需要支持以下三种操作:

  • 0.定义 a 为所有下标为偶数的数组成的子序列,b 为所有下标为奇数的数组成的子序列,将 a,b 连接,构成新的序列。
  • 1.定义 a 为所有下标为奇数的数组成的子序列,b 为所有下标为偶数的数组成的子序列,将 a,b 连接,构成新的序列。
  • 2.查询下标为 x 的数。

总共将进行 m 次操作。

1n32,1m106

(虽然是橙题,但还是想了很久)

一看数据规模就是O(1)找规律啦,但是无脑暴力列表好像是看不出任何结果的(不信可以试试)

我们首先看看操作的本质,设序列中原来位于x的数,进行操作后,到了位置y(从0编号)(注意,这里与题目的查询操作相反)

则y等于    x 在奇数/偶数中的排名 加上 0 或 n(奇数/偶数取决于x本身 , 0还是n取决于操作是0还是1)(n即为序列长度的一半) 

  那么列出柿子 :y = (x>>1) + n * (x&1^op)    op表示操作种类,x>>1表示在奇数/偶数中的排名

显然出现了位运算的意思!

感性观察一下,因为0<=x<=(1<<n)-1, 看成 x 在二进制表示下有 n 位,高位不足补 0,

那么对于二进制表示的 x ,上式表示将 x 右移一位,并把消掉的那一位(并上1再异或上op)后补到最左边

每次操作,仅与当前 x 的最低位有关, 且只会影响最高位,那么op的影响是以位计算

由于异或的可结合性,同一位进行多次操作后,等效于将作用在这一位上的op全部异或起来,再与该位进行运算

并且,对于任意的 x,op的影响是等效的

 

接下来准备实现了!

  ①我们维护一个变量cnt,表示到当前进行的操作次数,以决定原数要右移多少位到达当前的待操作数

    具体地,令 cnt%=n ,将 x 右侧的 cnt 位移至左侧,再将 x 右移 cnt 位

  ②维护一个操作变量 val ,存储每一位上的操作的异或和,并在操作后同时进行移位

最后 x^val 即得到这些操作后 x 的位置

但是,题目要求位置为 pos 的数是什么(完蛋,看错题了)

不急,我们设 x 经过操作后得到 pos ,并设①的函数为f(x);

  则要求 x,满足 f(x) ^ val = pos

  由异或运算性质 x = f -1(pos^val)

  因为 f(x) 是位移函数,所以  f -1(x) 很好求,反过来位移就行了

小细节:1<<32 会爆 ull !注意特判!

code:

uLL n,m,val,cnt,a; 
int main(){
    n=read();m=read();
    for(rint i=1;i<=m;i++){
       uLL op=read(),x=read();
       if(op==1){
          val^=(x<<cnt);
          if((++cnt)==n)cnt=0;
       }
       else{
          uLL k=x&((1<<(n-cnt))-1);
          if((n-cnt)==32)k=x&(((1<<32)-1));
          x=(k<<cnt)+(x>>(n-cnt));
          write(x^val);
       }
    }
}

 

留坑,以后还会写别的题

 


程序员灯塔
转载请注明原文链接:位运算好题
喜欢 (0)