Codeforce 1420 B. Rock and Lever 解析(思維)

今天我們來看看CF1420B
題目連結

題目
給一個數列$a$，求有多少種$(i,j)$使得$i<j$且$a_i&a_j\ge a_i\oplus a_j$

前言

c

想法

觀察到，由於$1&1=1$，$1\oplus1=0$，所以$a_i&a_j$有的$bit$，$a_i\oplus a_j$都不會有。
而繼續觀察到，如果$a_i,a_j$最左邊的$bit$是一樣的(例如都是第$10$個$bit$)，那麼$a_i&a_j\ge a_i\oplus a_j$。而如果不一樣，那麼$a_i,a_j$中擁有最左邊的$bit$的那個數字，會造成$a_i&a_j<a_i\oplus a_j$(因為$2^i>\sum\limits_{j=0}^{i-1}2^j$)。

所以只需要從數列左邊看到右邊，每次對於元素$a[i]$，看看前面有多少元素的最左$bit$和$a[i]$一樣即可。

程式碼:

const int _n=1e5+10;  
int t,tt,n,a[_n],cnt[40];  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>t;while(t--){  
    memset(cnt,0,sizeof cnt);  
    cin>>n;rep(i,0,n)cin>>a[i];  
    ll ans=0;rep(i,0,n){  
      tt=32-__builtin_clz(a[i]);  
      ans+=cnt[tt];  
      cnt[tt]++;  
    }cout<<ans<<'\n';  
  }  
  return 0;  
}  

標頭、模板請點Submission看
Submission