牛客挑战赛45 C-友人

友人

分析

• 先掏出式子
  
  可以发现，如果确定了 的值，那么z的合法范围就可以求出来，并且 ,完全可以 枚举。接下来考虑右边的括号。首先我们已经有了z的范围[1,max]，如果k第i位为1，那么z的第i位在满足 的条件下也得为1，这样原式相当于就会减小 ,如果k这一位为0，z这一位也应为0，因为如果为1，根据异或的性质，前面的异或结果会增加 ，而后面的会减少 ，什么也没变，但是我z却变大了，不就亏了吗。

代码

/*
(写点什么吧...)
*/
#include<bits/stdc++.h>

#define R register
#define ll long long
#define inf INT_MAX

using namespace std;

const int N=1e5+10;

ll n,st,d,k,ma;
ll a[N],b[N];

int main()
{
    scanf("%lld%lld%lld%lld%lld",&n,&st,&d,&k,&ma);
    for (ll i=1;i<=n;i++)
        a[i]=st+(i-1ll)*d,b[i]=b[i-1]+a[i];

    ll ans=(1ll<<62);
    for (ll i=1;i<=n;i++)
    {//枚举r-l+1
        ll l=0,r=a[n-i+1],z=-1;
        while(l<=r)
        {
            ll mid=(l+r)/2;
            ll now=b[n-i]+i*mid;
            if(now<=ma) z=mid,l=mid+1;
            else r=mid-1;
        }//找到z的最大值

        if(z<0) continue;

        ll las=0;
        for (ll j=40;j>=0;j--)
            if((k>>j)&1)
            {
                ll ok=(1ll<<j)+las;
                if(ok<=z) las=ok;
            }

        ans=min(ans,i*((las^k)+k-las));
    }

    if(b[n]<=ma) ans=0;
    printf("%lld\n",ans);

    return 0;
}