題目鏈接：點擊查看

題目大意：給出一個長度為 n 的序列，求出滿足下列條件的區(qū)間個數(shù)：

l + 1 <= r - 1 ，即區(qū)間長度大于等于 3

a[ l ] ^ a[ r ] = a[ l + 1 ] + ... + a[ r - 1 ]

題目分析：首先一個結(jié)論是，這樣的區(qū)間并不是很多，所以暴力去查找即可，假設(shè)確定了左端點 l 后，假設(shè)其最高位為 highbit ，那么區(qū)間和的大小只要是小于等于 ( 1 << highbit + 1 ) 的都是有可能滿足條件的區(qū)間，枚舉左端點掃一遍，再枚舉右端點掃一遍，記得去重

下面簡單論證一下時間復(fù)雜度，對于每個點作為右端點來說，其最多被兩個 最高位為 k 的左端點所掃到，因為如果有三個及以上的，最高位為 k 的左端點掃到的話，那么 3 * 2^k > 2^(k+1)，已經(jīng)不滿足上一段的約束條件了，所以該做法的時間復(fù)雜度為 nlog(max(a[ i ]))

代碼：
?

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;LL a[N];set<pair<int,int>>st;int highbit(int x) {int cnt=0;while(x){cnt++;x>>=1;}return cnt+1; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld",a+i);int ans=0;for(int l=1;l<=n;l++){int r=l+1;LL sum=0,limit=(1LL<<highbit(a[l]));while(r+1<=n&&sum<=limit){sum+=a[r++];if((a[l]^a[r])==sum){ans++;st.emplace(l,r);}}}for(int r=n;r>=1;r--){int l=r-1;LL sum=0,limit=(1LL<<highbit(a[r]));while(l-1>=1&&sum<=limit){sum+=a[l--];if((a[l]^a[r])==sum&&!st.count(make_pair(l,r)))ans++;}}printf("%d\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1438E Yurii Can Do Everything(暴力)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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