题目链接：https://ac.nowcoder.com/acm/problem/211996

到主站看：https://blog.csdn.net/weixin_43346722/article/details/109689563

题目

众所周知，一场比赛需要 道签到题。

你得到了一个长度为 ，公差为 的等差数列 。

给定两个常数 ，你可以进行一次如下操作：选择两个数 和一个非负整数 ，满足 。则本次操作为对于 ，令 ，同时其代价为 （其中 表示按位异或操作）。

输出最小的代价使得操作恰好一次后有

输入

输入共一行，共五个整数 ，含义如题目所述

输出

输出共一行，表示最小代价。

样例输入1

5 3 8 8 12

样例输出1

64

样例输入2

10 9 8 30 234

样例输出2

56

样例输入3

5 3 2 15 30

样例输出3

18

数据范围

，保证 在 long long 范围内，且

思路

这道题是一道贪心。

我们来看式子：。

先看左边，其实就是求区间的长度，这个我们可以直接枚举。

然后看右边，对于每一个区间长度，我们可以如果要让它发挥更大的作用，一定是摆在最右边的。（因为最右边的值最大）
那我们要让变了之后的序列总和小于等于 ，那 必然就会有一个取值范围：最小是 ，那最大呢？

那就是 。
（ 表示序列前面 项的和， 则是区间长度）

那我们知道了范围，但是如果一个一个枚举，就又会超时，那咋整呢？

我们可以贪心得出一个结论：要取的数要尽量在二进制高位上跟 一样。
为什么呢？

我们先设 的第 位是 。那如果 这一位选了 ，对于异或就少个 ，然后后面的 又少个一个 ，那就少了 。

接着我们设 的第 位是 。那如果 的这一位选了 ，那异或的部分多了个 ，然后后面的 少个一个 ，就刚好抵消，值不变。
那我们要让 的值不超过范围，又要让费用小，那还不如不选。

那我们就从高位枚举，如果 的这一位是 然后 的这一位变成 之后小于等于范围，就把这一位变成 。

那我们就可以得出对于每一个区间长度最好的 了。

然后把每一个区间长度的出来的费用取最小值，就是答案了。

代码

#include<cstdio>
#include<iostream>

using namespace std;

long long n, d, size, a1, k, y, z, ans, a[100001], sum[100001], realz;

int main() {
    ans = 1e18;

    scanf("%lld %lld %lld %lld %lld", &n, &a1, &d, &k, &y);

    sum[1] = a[1] = a1;
    for (int i = 2; i <= n; i++) a[i] = a[i - 1] + d, sum[i] = sum[i - 1] + a[i];
    //先算出每一个数和前缀和

    while (y < sum[n - size]) size++;
    //要使总和小于等于 y 至少要让区间长度是多少

    for (size; size <= n; size++) {//枚举区间长度
        z = (y - sum[n - size]) / size;

        realz = 0;//贪心选异或值最小的
        for (int i = 60; i >= 0; i--)
            if (((k >> i) & 1) && realz + (1 << i) <= z)
                realz += 1 << i;

        ans = min(ans, size * ((realz ^ k) + k - realz));
    }

    printf("%lld", ans);

    return 0;
}