题解：CF51D Geometrical problem

· · 题解

CF51D Geometrical problem 题解

注：本蒟蒻的思路十分诡异，貌似与很多题解都不一致，请搭配糯米食用

一、题目大意

给你一个长度为 n 的整数序列 a_1, a_2, \dots, a_n。

这里的等比数列定义很宽：存在实数 b 和 c，使得第 i 项满足 a_i = c \cdot b^{i-1}。
因此序列里可以出现 0，但 0 后面如果跟着非零数，那就一定不合法，除非把这个 0 删掉。

二、核心想法

一个长度为 L 的序列是等比数列，等价于它的 所有相邻两项的比值都相等。
但直接算 a_{i+1} / a_i 有个坑：分母不能是 0。所以我们不能只存一个比值，而是要把相邻对分类。

我们把每一对 (a_i, a_{i+1}) 分成三种情况：

统计的时候用两个哈希表：

如果序列里所有的相邻对都属于 同一个类别，并且（对于情况 1 和情况 3）数值也一样，那这个序列就是等比数列。

三、怎么判断原序列

先把所有 n-1 个相邻对统计好，然后检查是否存在某一类，它的出现次数刚好等于 n-1。

具体来说：

只要满足任意一条，原序列就是等比，直接输出 0。

四、怎么判断删一个元素

如果原序列不行，我们就枚举删掉哪个元素。

暴力做法是每次删完重新统计，复杂度 O(n^2)，n 最大 10^5，肯定超时。
所以我们要用 动态维护 的办法：先把所有相邻对统计好，删的时候只改受影响的几对。

1. 删掉首尾元素

删掉第一个元素后，剩下的是 a_2, a_3, \dots, a_n，相邻对是原来的第 2 对到第 n-1 对，一共 n-2 对。
我们只需要检查这些对是不是同类，也就是看 val 或 div0 里有没有某个计数等于 n-2。

删掉最后一个元素同理。

2. 删掉中间元素（2 \le i \le n-1）

假设删掉 a_i，那么：

我们做两个操作：

执行 del(i) 后，哈希表里剩下的是除这两个旧对以外的所有对，数量正好是 n-3。
这时候我们看新对 (a_{i-1}, a_{i+1}) 属于哪一类，再判断剩下的旧对是不是全部和它同类同值。

判断条件是这样的：

只要满足其中一条，就说明删掉 a_i 后剩下的序列是等比数列，答案设为 1。

枚举完所有位置后，如果都没有成功，答案就是初始的 2。

五、关于 0 和 (0,x) 的说明

注意到，代码把 (0,x) 这种“非法对”也当作一种类型来比较了。
严格来说，只要序列里出现一个 (0,x)（x \neq 0），它就不可能是等比数列。

但在我们的判断流程中，如果删掉一个元素后，剩下的所有相邻对都恰好是 (0,x)，那说明剩下的序列长度是 2（因为只有一个相邻对）。而长度为 2 的序列，我们在开头已经特判过了——除了 [0,x] 这种情况输出 1，其余输出 0。
对于更长的序列，删除后不可能只剩一个对，所以不会出现“所有对都是 (0,x)”的误判。
因此这种计数方法在实际数据中是不会出错的，它只是为了方便统一处理而已。

另外，用 double 存比值可能会有精度误差，但这题数值范围小（|a_i| \le 10^4），比值分母也很小，实际测试中 map 的比较是安全的。

六、时间复杂度

预处理统计相邻对是 O(n \log n)。
枚举每个删除位置时，每次 del 和 add 都只做常数次哈希表操作，也是 O(\log n)。
所以总复杂度 O(n \log n)，空间 O(n)，完全能过。

七、完整代码

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

int n;
vector<double> a;

map<double, int> val;   // 比值计数，val[0] 包含 (x,0) 和 (0,0)
map<int, int> div0;     // 统计 (0, x) 中 x 的出现次数

void del(int i) {
    // 移除 (a[i-1], a[i])
    if (a[i] == 0 && a[i-1] == 0) val[0]--;
    else if (a[i-1] == 0) div0[a[i]]--;
    else val[1.0 * a[i] / a[i-1]]--;

    // 移除 (a[i], a[i+1])
    if (a[i+1] == 0 && a[i] == 0) val[0]--;
    else if (a[i] == 0) div0[a[i]]--;
    else val[1.0 * a[i+1] / a[i]]--;
}

void add(int i) {
    if (a[i] == 0 && a[i-1] == 0) val[0]++;
    else if (a[i-1] == 0) div0[a[i]]++;
    else val[1.0 * a[i] / a[i-1]]++;

    if (a[i+1] == 0 && a[i] == 0) val[0]++;
    else if (a[i] == 0) div0[a[i]]++;
    else val[1.0 * a[i+1] / a[i]]++;
}

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

    cin >> n;
    a.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    if (n == 1) {
        cout << 0 << '\n';
        return 0;
    }

    if (n == 2) {
        if (a[1] == 0 && a[2] != 0) cout << 1 << '\n';
        else cout << 0 << '\n';
        return 0;
    }

    // 预处理所有相邻对
    for (int i = 2; i <= n; i++) {
        if (a[i] == 0 && a[i-1] == 0) val[0]++;
        else if (a[i-1] == 0) div0[a[i]]++;
        else val[1.0 * a[i] / a[i-1]]++;
    }

    // 检查原序列
    for (int i = 2; i <= n; i++) {
        if ((a[i] == 0 && a[i-1] == 0 && val[0] == n - 1) ||
            (a[i-1] != 0 && val[1.0 * a[i] / a[i-1]] == n - 1) ||
            (a[i-1] == 0 && div0[a[i]] == n - 1)) {
            cout << 0 << '\n';
            return 0;
        }
    }

    int ans = 2;

    // 判断删除第一个或最后一个元素
    if (n >= 3) {
        if ((a[2] == 0 && a[3] == 0 && val[0] == n - 2) ||
            (a[2] == 0 && div0[a[3]] == n - 2) ||
            (a[2] != 0 && val[1.0 * a[3] / a[2]] == n - 2) ||
            (a[n-2] == 0 && a[n-1] == 0 && val[0] == n - 2) ||
            (a[n-2] == 0 && div0[a[n-1]] == n - 2) ||
            (a[n-2] != 0 && val[1.0 * a[n-1] / a[n-2]] == n - 2)) {
            cout << 1 << '\n';
            return 0;
        }
    }

    // 枚举删除中间位置
    for (int i = 2; i <= n - 1; i++) {
        del(i);

        if ((a[i-1] == 0 && a[i+1] == 0 && val[0] == n - 3) ||
            (a[i-1] == 0 && div0[a[i+1]] == n - 3) ||
            (a[i-1] != 0 && val[1.0 * a[i+1] / a[i-1]] == n - 3)) {
            ans = 1;
            break;
        }

        add(i);
    }

    cout << ans << '\n';
    return 0;
}

八、总结

本蒟蒻的思路很诡异，若想学习正解，很多题解都比本篇优秀
另：积极接受hack