题解：AT_abc413_d [ABC413D] Make Geometric Sequence

· · 题解

一个有趣的题。

我们先考虑一个所有数的符号相同的数列如何判断。我们将其从小到大排序后，如果是一个等比数列，那么则会有：A_{i-1}=\dfrac{A_i}{r},A_{i+1}=rA_i（r 是公比，1<i<n）。

于是有，

A_{i-1} \times A_{i+1}=A_i^2(1<i<n)

于是我们排序后直接遍历判断即可。

现在我们考虑正负数。显然，如果 B 是一个等比数列的话，那么 B 一定是正负数相间出现的，因此先判断正负数数量是否匹配。接着我们思考如何判断数列，判断数列首先肯定需要将数列排序。

对于一个公比为正数的等比数列，如果我们将公比取相反数，我们会发现最后的结果只是将原数列的偶数项取了相反数，如果要让奇数项取相反数只需要让首项取反即可。

于是我们将 A 按照绝对值从小到大排序，之后就可以套用上面的判断方法了。

但是我们考虑下面一种情况：A=(p,-p,\cdots)。也就是 A 数列中的数绝对值相同但符号不同。这时如果按照我们上面的排序方法有可能会导致正数和负数没有相间，于是我们就会得到错误的结果。因此我们需要一个特判。

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <numeric>
long long g[200005];
int main() {
    int T;
    for (scanf("%d", &T); T--;) {
        int n, fsnum = 0, zsnum = 0; //fsnum->负数的数量,zsnum->正数的数量
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%lld", g + i);
        bool ok = 1;
        for (int i = 0; i < n; ++i) {
            if (g[i] > 0) ++zsnum;
            else ++fsnum;
            if (abs(g[i]) != abs(g[0])) { //判断是否绝对值全部相等
                ok = 0;
                break;
            }
        }
        if (abs(zsnum - fsnum) > 1 && zsnum && fsnum) {puts("No"); continue;}
        if (ok) {puts("Yes"); continue;}
        std::sort(g, g + n, [] (long long a, long long b) -> bool {return abs(a) < abs(b);}), ok = 1;
        for (int i = 1; i < n - 1; ++i) if (g[i-1] * g[i + 1] != g[i] * g[i]) {ok = 0; break;} //枚举判断
        puts(ok ? "Yes" : "No");
    }
}