「EZEC-11」等差数列

题意

给出一个首项为 a、公差为 d、长度为 n 的等差数列。如果选出的两个数平均值是整数且还不在集合里，就可以把这个平均数加入集合。问最多还能加入多少个新数。

思路

先看一个可以直接验证想法的朴素解：

小数据时可以维护集合，不断枚举两数并加入新的整数中点，直到再也加不动。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, a, d;
        cin >> n >> a >> d;

        set<int> s;
        for (int i = 0; i < n; i++) {
            s.insert(a + i * d);
        }

        bool changed = true;
        while (changed) {
            changed = false;
            vector<int> cur(s.begin(), s.end());
            int m = (int) cur.size();
            for (int i = 0; i < m; i++) {
                for (int j = i + 1; j < m; j++) {
                    int sum = cur[i] + cur[j];
                    if (sum & 1) continue;
                    int mid = sum / 2;
                    if (s.count(mid)) continue;
                    s.insert(mid);
                    changed = true;
                }
            }
        }

        cout << (int) s.size() - n << '\n';
    }

    return 0;
}

关键是把公差拆成：

d = odd \times 2^t

去掉奇数因子后，问题就变成：

0, 2^t, 2 \times 2^t, \dots, (n-1) \times 2^t

不断取整数中点后，每个原始间隔都会被一层层二分，最终补成连续整数。所以最后总共有：

(n-1) \times 2^t + 1

个数，新增数量就是：

(n-1) \times (2^t - 1)

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        long long n, a, d;
        cin >> n >> a >> d;

        long long pw2 = 1;
        while ((d & 1LL) == 0) {
            pw2 <<= 1;
            d >>= 1;
        }

        cout << (n - 1) * (pw2 - 1) << '\n';
    }

    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23import sys

input = sys.stdin.buffer.readline

def solve_case(n,d):
    pw2 = 1
    while d % 2 ==0:
        pw2 *= 2
        d //= 2
    return (n-1) *(pw2-1)

def solve():

    pass


if __name__ == "__main__":
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data[1:])
    res = []
    for n,a,d in zip(it,it,it):
        res.append(solve_case(n,d))
    print(*res,sep="\n")

复杂度

每组数据只需要统计 d 中 2 的幂次，时间复杂度 $O(log d)$ ，空间复杂度 $O(1)$ 。

总结

这题的关键不是模拟闭包，而是发现答案只取决于公差里的 2 的幂次。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

「EZEC-11」等差数列

目录

题意

思路

代码

复杂度

总结

一图流解析