Wannafly挑战赛4 A解方程【二分/set/hash求解方程】-白红宇

Wannafly挑战赛4 A解方程【二分/set/hash求解方程】

阅读量：6625 次

发布时间：2019-06-25

本文共 2355 字，大约阅读时间需要 7 分钟。

https://www.nowcoder.com/acm/contest/35/A

题目描述

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

输入描述:

第一行两个整数n，x 第二行n个整数a[i]表示可以用的数 1 <= n <= 1000, -1000 <= a[i], x <= 1000

输出描述:

YES表示可以 NO表示不可以

示例1

输入

2 11 -2

输出

YES

【分析】：x是已知的。其实就是二分枚举答案。或者hash or set

【代码】：

#include
           
            using namespace std;int a[1005];int main() {    set
            
              s;    int n, x, f=0;    cin >> n >> x;    int *a = new int[n];    for (int i = 0; i < n; ++i) {        cin >> a[i];        s.insert(a[i]);    }    //sort(a,a+n);    if(s.count(0)) f=1;    for(int i=0;i

set解法

#include
           
            using namespace std;map
            
              mp;int a[1005];int main() {    int n, x, f=0;    cin >> n >> x;    int *a = new int[n];    for (int i = 0; i < n; ++i) {        cin >> a[i];        mp[a[i]]++;    }    //sort(a,a+n);    for(int i=0;i

map

#include
           
            using namespace std;int vis[10005];int a[1005];int main() {    int n, x, f=0;    cin >> n >> x;    int *a = new int[n];    for (int i = 0; i < n; ++i) {        cin >> a[i];        vis[a[i]+1000]=1;    }    //sort(a,a+n);    for(int i=0;i
            
             =-1000&&ans<=1000&&vis[ans+1000]){                f=1;                break;            }        }    }    if(f) printf("YES\n");    else printf("NO\n");}

hash最少时间

#include
           
            using namespace std;int vis[10005];int a[1005];int main() {    int n, x, f=0;    cin >> n >> x;    int *a = new int[n];    for (int i = 0; i < n; ++i) {        cin >> a[i];    }    sort(a,a+n);    for(int i=0;i

sort + lower_bound

#include
           
            using namespace std;int a[10000];int main(){    int n,x;    cin>>n>>x;    for (int i=0;i

sort2

#include
           
            using namespace std;typedef long long ll;ll a[1010];int main(){    int n,x,l,r,mid;    scanf("%d%d",&n,&x);    for(int i=1;i<=n;i++)        scanf("%lld",&a[i]);    sort(a+1,a+1+n);     bool f=0;    for(int i=1;i<=n&&!f;i++){        for(int j=1;j<=n&&!f;j++){            ll ans = -(a[i]*x*x+a[j]*x);            l = 1,r = n,mid;            while(l<=r){                mid = l+r>>1;                if(ans==a[mid]){f=1;break;}                else if(a[mid]

手写二分