正題

題目鏈接:https://www.luogu.com.cn/problem/CF1054D

---

題目大意

一個長度為$n$的序列，每個數小于$2^k$，可以選擇一些數$xor$上$2^k?1$。要求使得滿足$a_{l}xor{a}_{l+1}xor...xor{a}_r=0$的區間個數最少。

---

解題思路

首先做前綴$xor$，這樣就變成了$a_{l?1}xor{a}_r=0$的數量最少，也就算相同的對數最少。
若$axor(2^k?1)=b$或者$a=b$我們將它們視為同一類，它們可以相互轉換，對于每一類我們一半取大的，一半取小的即可。

時間復雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<map> using namespace std; const int N=2e5+10; int n,k,a[N];long long ans; map<int,int> v; long long p(int x) {return 1ll*x*(x-1)/2;} int main() {scanf("%d%d",&n,&k);int ms=(1<<k)-1;v[0]++;for(int i=1;i<=n;i++){scanf("%d",&a[i]);a[i]^=a[i-1];if(ms-a[i]>a[i])v[a[i]]++;else v[ms-a[i]]++;}map<int,int>::iterator it=v.begin();ans=1ll*n*(n+1)/2;for(;it!=v.end();it++){int x=it->second;ans-=p(x/2)+p(x-x/2);}printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的CF1054D-Changing Array【贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。