XORSUM#11837
Daxil ol

XORSUM (Həll təhlili)

Problem Müəllifi:

Hasan Saleh (MathModel)

Hazırlayan:

Hasan Saleh (MathModel)

Redaktə edən:

Hasan Saleh (MathModel)

Dövrün dövrü olduğunu nəzərə alın, yəni ardıcıllıq aşağıdakı formada olur

[a,b,a \oplus b,a,b,a \oplus b,....]

Dövr uzunluğunu əldə etməklə demək olar ki, bütün işi edə bilərik. Dövr uzunluğu intervaldakı tamamlanmış -tam ədəd seqmentlərinin sayıdır. İntervalın uzunluğu r-l+1 olduğuna görə, \displaystyle \text{cycles}=\left \lfloor \frac{r-l+1}{3} \right \rfloor

Dövrün başlanğıc indeksini və son indeksini əldə edirik, dövrün ardıcıllıqda ilk ilə başladığını və son a \oplus b ilə bitdiyini nəzərə alaraq, qalan elementlərin cəmini (maksimum ) toplayırıq, dövr cəmi isə (r-l+1-(r-l+1) \bmod 3) \times (a+b+a \oplus b)-dir.

Ümumi mürəkkəblik .

Kod 1

#include<bits/stdc++.h>
using namespace std;
#define ll long long

void solve(){
    ll a,b,l,r;cin>>a>>b>>l>>r;
    vector<ll>v={a,b,(a^b)};
    ll x=0;ll y=0;
    ll ans=0;
     r--;l--;
    int cnt=0;
    for(int i=l;i<l+3;i++){
        if(i%3!=0){
            ans+=v[i%3];cnt++;
        }else{
            x=i;
            break;
        }
    }
    for(int i=r;i>r-3;i--){
        if((i+3)%3!=2){
            ans+=v[(i+3)%3];cnt++;
        }else{
            y=i;
            break;
        }
    }
    cout<<ans+((r-l+1-cnt)/3)*(v[0]+v[1]+v[2])<<"\n";
}
int main(){
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
C++

Kod 2 (Qısa)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
    ll a,b,l,r;cin>>a>>b>>l>>r;
    vector<ll>v={a,b,(a^b)};
    ll ans=(v[0]+v[1]+v[2])*((r-l+1)/3);
    ll rem=(r-l+1)%3;
    ll base=(l-1)%3;
    for(int i=0;i<rem;i++){
        ans+=v[(base+i)%3];
    }
    cout<<ans<<"\n";
}
int main(){
    int t;cin>>t;
    while(t--){
        solve(); 
    }
    return 0;
}
C++