【每日一題】7月3日精講—毒瘤xor

時間限制：C/C++ 1秒，其他語言2秒 空間限制：C/C++ 32768K，其他語言65536K Special Judge, 64bit IO Format: %lld

文章目錄

• • 題目描述
  • 題解：
  • 代碼：

題目描述

輸入描述:

第一行一個整數(shù)N，表示序列的長度 第二行N個整數(shù)，表示序列內(nèi)的元素 第三行一個整數(shù)q，表示詢問的個數(shù) 接下來q行，每行兩個整數(shù)[L,
R]，表示詢問的區(qū)間

輸出描述:

輸出q行，每行一個整數(shù)表示答案

若有多組可行解，請輸出較小的解

示例1
輸入
復(fù)制

5 4 78 12 1 3 3 2 5 1 4 3 3

輸出

2147483632 2147483635 2147483635

備注:

對于30%的數(shù)據(jù)，n , q ≤ 10 對于60%的數(shù)據(jù)，n , q ≤ 1000 對于100%的數(shù)據(jù)，n, q ≤ 10^5 保證ai < 2^31

題解：

很久沒有遇到異或的題了
先講下異或：1 ^ 1 =0 , 0 ^ 0= 0,1 ^ 0 =1,0 ^ 1 =1
相同為0，不同為1
異或是兩個數(shù)二進(jìn)制狀態(tài)下相同數(shù)位進(jìn)行操作
我們要找一個x使得x ^ a[i]的和最大，那我們就盡量使x與a[i]的相同位數(shù)異或后為1，這樣就最大
a[i]是一個數(shù)組，所以我們就求這個數(shù)組里每個數(shù)的二進(jìn)制狀態(tài)下，每一位0和1的個數(shù)，比如說，數(shù)組有n個數(shù)，其中b個數(shù)二進(jìn)制狀態(tài)下第一位是0，剩下n-b個數(shù)二進(jìn)制狀態(tài)下第一位是1，如果b>n-b,那我們就使X二進(jìn)制的第一位是1，（就是和最多情況的數(shù)呈相反，這樣異或出來才是1）
然后是第二位，依次類推最后我們就得到X的二進(jìn)制狀態(tài)，轉(zhuǎn)化成十進(jìn)制輸出即可
因為有多輪詢問，所以我們可以用前綴和來處理每一位為1的數(shù)

bool w=((a[i]>>j)&1);//判斷第j位是0是1 sum[i][j]=(sum[i-1][j]+w);//前綴和進(jìn)行累加

代碼：

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+4; typedef long long ll; ll a[maxn]; int sum[maxn][40]; int main() {int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){for(int j=0;j<31;j++){bool w=((a[i]>>j)&1);//判斷第j位是0是1 sum[i][j]=(sum[i-1][j]+w);}}int q;cin>>q;int tot=0;while(q--){tot=0;int l,r;cin>>l>>r;for(int j=0;j<31;j++){if(sum[r][j]-sum[l-1][j] < ( (r-l)/2+1) )//當(dāng)這一位0居多時，X選為1 tot+=(1<<j); }cout<<tot<<endl; } }

總結(jié)

以上是生活随笔為你收集整理的【每日一题】7月3日精讲—毒瘤xor的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。