[IOJ] 19. 啦啦啦

題目連結:http://ioj.infor.org/problems/19
因為$xor$有神奇(?的性質$a \oplus b = c \Longrightarrow a \oplus c = b$,所以就$O(n)$掃過去建好表,再$O(n)$掃一遍加起來,值得注意的是因為$a \oplus 0 = a$,所以若$x=0$,那要再減掉所有數的個數(自己不能算)
#include <stdio.h>

void gn(int &_){
  _=0;char c=getchar();
  while(c<'0'||c>'9')c=getchar();
  while(c>='0'&&c<='9')_=_*10+c-'0',c=getchar();
}

int MiccWan[100000 + 10];
int wayneTu[1000000 + 10] = {0};

int main(){
  int t,x;
  long long edisonhello=0;
  gn(t);gn(x);
  for(int i=0;i<t;i++){
    gn(MiccWan[i]);
    wayneTu[MiccWan[i]^x]++;
  }
  for(int i=0;i<t;i++){
    edisonhello+=wayneTu[MiccWan[i]];
  }
  if(x==0)
    edisonhello-=t;
  printf("%lld",edisonhello>>1);
  return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology