题解：CF1616C Representative Edges

xiaoyi_zeng · 2026-03-08 21:18:43 · 题解

CF1616C

前言

CF 你认真的吗，1500 的题是绿的，1600 的题是黄的？

一开始没看见改成实数，倒闭了一会儿。

其实我没有注意到等差数列然后算了半天突然发现的。

思路

注意到就是一个等差数列求和公式。

每个子序列都是等差数列其实等价于原数列是等差数列。

考虑最多能不变几项。直接考虑固定第 i，j 位不动（其中 i < j），分别为 a_i 和 a_j。那么公差为 \frac{a_j-a_i}{j-i}。

接下来只需要枚举 k 使得 i < j < k 且 \frac{a_k-a_i}{k-i}=\frac{a_j-a_i}{j-i}，即公差固定。

代码

这里判断等于我直接把分数的板子复制过来了，导致代码有点长，见谅。

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

const int N = 75;

int n, a[N];

struct frac{
    int x, y; // x / y

    void yf(){ int g = __gcd(x, y); x /= g, y /= g; }

    frac(){ x = 1, y = 1; }
    frac(int _x, int _y){ x = _x, y = _y, yf(); }
    frac(int _x){ x = _x, y = 1; }
    frac operator = (frac t){ x = t.x, y = t.y; return *this; }

    bool operator == (frac t){ return 1ll * x * t.y == 1ll * y * t.x; }

    frac operator + (frac t){
        frac res = *this; t.yf(); int l = res.y / __gcd(res.y, t.y) * t.y;
        res.x = res.x * res.y / l + t.x * t.y / l, res.y = l, res.yf(); return res;
    }
    frac operator += (frac t){
        t.yf(); int l = y / __gcd(y, t.y) * t.y;
        x = x * y / l + t.x * t.y / l, y = l, yf(); return *this;
    }
    frac operator + (int t){ frac res = *this; res.x += t * res.y; return res; }
    frac operator += (int t){ x += t * y; return *this; }

    frac operator - (frac t){
        frac res = *this; t.yf(); int l = res.y / __gcd(res.y, t.y) * t.y;
        res.x = res.x * res.y / l - t.x * t.y / l, res.y = l, res.yf(); return res;
    }
    frac operator -= (frac t){
        t.yf(); int l = y / __gcd(y, t.y) * t.y;
        x = x * y / l - t.x * t.y / l, y = l, yf(); return *this;
    }
    frac operator - (int t){ frac res = *this; res.x -= t * res.y; return res; }
    frac operator -= (int t){ x -= t * y; return *this; }

    frac operator * (frac t){ frac res = *this; t.yf(); res.x *= t.x, res.y *= t.y, res.yf(); return res; }
    frac operator *= (frac t){ t.yf(), x *= t.x, y *= t.y, yf(); return *this; }
    frac operator * (int t){ frac res = *this; res.x *= t, res.yf(); return res; }
    frac operator *= (int t){ x *= t, yf(); return *this; }

    frac operator / (frac t){ frac res = *this; t.yf(); res.x *= t.y, res.y *= t.x, res.yf(); return res; }
    frac operator /= (frac t){ t.yf(), x *= t.y, y *= t.x, yf(); return *this; }
    frac operator / (int t){ frac res = *this; res.y *= t, res.yf(); return res; }
    frac operator /= (int t){ y *= t, yf(); return *this; }
};

int main(){
    int T; cin >> T; while (T -- ){
        cin >> n; for (int i = 1; i <= n; i ++ ) cin >> a[i];

        int mx = 0;
        for (int i = 1; i <= n; i ++ ){
            for (int j = i + 1; j <= n; j ++ ){
                frac d(a[j] - a[i], j - i); int cnt = 2;
                for (int k = j + 1; k <= n; k ++ ){
                    frac c(a[k] - a[i], k - i);
                    if (d == c) cnt ++;
                }
                mx = max(mx, cnt);
            }
        }

        cout << min(n - mx, n - 1) << "\n";
    }
}

后记

点个赞再走吧。