题解 | #送分了QAQ#

题目描述

给出n个整数和x，请问这n个整数中是否存在三个数a，b，c使得$a{x}^2+bx+c=0ax^2+bx+c=0$，数字可以重复使用。

思路

因为 $1\le n\le 10001\; \backslash leq\; n\; \backslash leq\; 1000$，枚举每一个a，b，c就会超时，因为$a{x}^2+bx+c=0ax^2+bx+c=0$，所以$c=-(a{x}^2+bx)c\; =\; -(ax^2+bx)$，这样就可以枚举a，b在一个序列中找是否存在一个数等于c，这样就可二分了。

时间复杂度$O(n^{2}logn)O(n^2logn)$

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, x;
int q[N];

int main()
{
    cin >> n >> x;
    for (int i = 0; i < n; i ++ ) cin >> q[i];
    
    bool flag = true;
    sort(q, q + n);
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < n; j ++ )
        {
            int a = q[i], b = q[j];
            int c = -(a * x * x + b * x);
            int l = 0, r = n - 1;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (q[mid] >= c) r = mid;
                else l = mid + 1;
            }
            if (q[r] == c)
            {
                flag = false;
                puts("YES");
            }
            if (!flag) break;
        }
        if (!flag) break;
    }
    
    if (flag) puts("NO");
    
    return 0;
}