正題

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

---

題目大意

給出$n$個(gè)數(shù)字$a_i$求
$$\underset{i=1}{\overset{n}{?}}\underset{j=i+1}{\overset{n}{?}}(a_i+a_j)$$

$1\le n\le 4\times 10^5,1\le a_i\le 10^7$

---

解題思路

分位考慮的話，先把每個(gè)位置更高位的給去掉，此時(shí)兩個(gè)數(shù)字和這位為$1$的情況當(dāng)且僅當(dāng)他們的和在$[2^k,2^{k+1})$或者$[2^{k+1}+2^k,2^{k+2})$這兩個(gè)區(qū)間。

雙指針掃兩次就好了。

時(shí)間復(fù)雜度$O(n\log a_i)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=4e5+10; ll n,a[N],b[N],sum; signed main() {scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld",&b[i]);for(ll k=0;k<25;k++){ll l=1,r=0,ans=0;for(ll i=1;i<=n;i++)a[i]=b[i]&((1ll<<k+1)-1);sort(a+1,a+1+n); for(ll i=n;i>=1;i--){ll L=(1ll<<k)-a[i],R=(1ll<<k+1)-a[i];while(r<n&&a[r+1]<R)r++;while(l<=n&&a[l]<L)l++;if(l>=i)break;ans+=min(r,i-1)-l+1; }l=1,r=0;for(ll i=n;i>=1;i--){ll L=(1ll<<k+1)+(1ll<<k)-a[i],R=(1ll<<k+2)-a[i];while(r<n&&a[r+1]<R)r++;while(l<=n&&a[l]<L)l++;if(l>=i)break;ans+=min(r,i-1)-l+1; }sum+=(ans&1)*(1ll<<k);}printf("%lld\n",sum);return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF1322B-Present【双指针】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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