P8177 「EZEC-11」等差数列

· · 题解

题目大意

给定一个长为 n，首项为 a，公差为 d 的等差数列 x。

每次操作可选取 x_i,x_j\ (i\ne j) 当满足 x_i+x_j\bmod2=0 且 \frac{x_i+x_j}{2} 不在原数列中可以将 \frac{x_i+x_j}{2} 加入原数列。

新加入的数也可以被选择。

求最多能进行的操作数。

思路分析

我们把 x_i 都看成是一个 t 数组的下标。

现在假设有等差数列 \{3,6,9\}。标出对应下标。

发现 3 和 6 之间相差 3 格，所以无法选取 3 和 6 进行一次操作。

所以当公差为奇数的时候，相邻两个数之间是无法进行操作的。

同时发现 3 与 9 为偶数，但 \frac{3+9}{2}=6，已经在数列中。所以无法操作。

扩展到任意等差数列：

\frac{x_i+x_j}{2}=x_{\frac{i+j}{2}} \ (|i-j|\bmod 2=0)

所以我们是无法选取在 x 中下标相差为偶数的元素进行操作的。

再来看一组数据：x=\{2,6,10\}。

首先，我们一段一段看。即分为 \{2,6\} 与 \{6,10\}。

$\{6,10\}$ 可以进行操作。得到 $8$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/cwphoukr.png) 等差数列公差减少了一半，变成了 $n=5,a=2,d=2$ 的等差数列了。 可以继续进行操作。 还是一段一段看。 $\{2,4\}$ 可以进行操作。得到 $3$。 $\{4,6\}$ 可以进行操作。得到 $5$。 $\{6,8\}$ 可以进行操作。得到 $7$。 $\{8,10\}$ 可以进行操作。得到 $9$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/zbi467mj.png) 这下就不能进行操作了。 我们可以发现，等差数列的变化规律： 1. $n=3,a=2,d=4
  1. n=5,a=2,d=2
  2. n=9,a=2,d=1

易发现 n_i=n_{i-1}\times 2 - 1,a_{i} = a_{i-1}。

而 d 仅当为偶数时可以进行操作。奇数时停止。

其实就是求 d 转换为二进制后从低位开始第一个 1 到之前所有 0 组成的新数。通俗一点，就是最大的整除 d 的 2 的整数次幂。代码：

k = 1;
while (d % 2 == 0) {
    d /= 2;
    k *= 2;
}
k--;

当然，学过树状数组的童鞋可能会知道 lowbit 这个东东，所以就可以 O(1) 求解啦！

k = (d & (-d)) - 1;

当然这个位运算的背后原理比较复杂，这里简单提一下，有兴趣的同学可以上网了解一下。

这里的 k 是每一段可以进行的次数，一共有 n - 1 段，所以答案显而易见：

ans=((d\ \& \ (-d)) - 1) \times (n-1)

完整代码

#include <bits/stdc++.h>
#define int long long

using namespace std;

int c;
int n, a, d;

inline int read()
{
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
    if(flag) return X;
    return ~(X-1);
}
inline void write(int X)
{
    if(X<0) {X=~(X-1); putchar('-');}
    if(X>9) write(X/10);
    putchar(X%10+'0');
}

signed main() {
    c = read();
    while (c--) {
        n = read(), a = read(), d = read();
        write(((d & (-d)) - 1) * (n - 1));
        puts("");
    }
    return 0;
}

为了抢一个最优解，附上了快读。不过最后还是没抢到