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

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 1

1 -2

输出

YES

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

【代码】：

#include<bits/stdc++.h>

using namespace std;

int a[];

int main() {

    set<int> s;

    int n, x, f=;

    cin >> n >> x;

    int *a = new int[n];

    for (int i = ; i < n; ++i) {

        cin >> a[i];

        s.insert(a[i]);

    }

    //sort(a,a+n);

    if(s.count()) f=;

    for(int i=;i<n;i++){

        for(int j=i;j<n;j++){

            int ans= -(a[i]*x*x+a[j]*x);

            if(s.count(ans)){

                f=;

                break;

            }

        }

    }

    if(f) printf("YES\n");

    else printf("NO\n");

}

set解法

#include<bits/stdc++.h>

using namespace std;

map<int,int> mp;

int a[];

int main() {

    int n, x, f=;

    cin >> n >> x;

    int *a = new int[n];

    for (int i = ; i < n; ++i) {

        cin >> a[i];

        mp[a[i]]++;

    }

    //sort(a,a+n);

    for(int i=;i<n;i++){

        for(int j=i;j<n;j++){

            int ans= -(a[i]*x*x+a[j]*x);

            if(mp[ans])

                return *puts("YES");

        }

    }

    printf("NO\n");

}

map

#include<bits/stdc++.h>

using namespace std;

int vis[];

int a[];

int main() {

    int n, x, f=;

    cin >> n >> x;

    int *a = new int[n];

    for (int i = ; i < n; ++i) {

        cin >> a[i];

        vis[a[i]+]=;

    }

    //sort(a,a+n);

    for(int i=;i<n;i++){

        for(int j=i;j<n;j++){

            int ans= -(a[i]*x*x+a[j]*x);

            if(ans>=-&&ans<=&&vis[ans+]){

                f=;

                break;

            }

        }

    }

    if(f) printf("YES\n");

    else printf("NO\n");

}

hash最少时间

#include<bits/stdc++.h>

using namespace std;

int vis[];

int a[];

int main() {

    int n, x, f=;

    cin >> n >> x;

    int *a = new int[n];

    for (int i = ; i < n; ++i) {

        cin >> a[i];

    }

    sort(a,a+n);

    for(int i=;i<n;i++){

        for(int j=i;j<n;j++){

            int ans= -(a[i]*x*x+a[j]*x);

            int res = lower_bound(a,a+n,ans)-a;

            if(res==n) continue;

            if(a[res]==ans){

                f=;

                break;

            }

        }

    }

    if(f) printf("YES\n");

    else printf("NO\n");

}

sort + lower_bound

#include<bits/stdc++.h>

using namespace std;

int a[];

int main()

{

    int n,x;

    cin>>n>>x;

    for (int i=;i<n;i++){

        scanf("%d",a+i);

    }

    sort(a,a+n);

    for (int i=;i<n;i++){

        for (int j=;j<n;j++){

            long long tmp=1LL*a[i]*x*x+1LL*a[j]*x;

            if(*lower_bound(a,a+n,-tmp)==-tmp)return *puts("YES");

        }

    }

    puts("NO");

}

sort2

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a[];

int main()

{

    int n,x,l,r,mid;

    scanf("%d%d",&n,&x);

    for(int i=;i<=n;i++)

        scanf("%lld",&a[i]);

    sort(a+,a++n);

    bool f=;

    for(int i=;i<=n&&!f;i++){

        for(int j=;j<=n&&!f;j++){

            ll ans = -(a[i]*x*x+a[j]*x);

            l = ,r = n,mid;

            while(l<=r){

                mid = l+r>>;

                if(ans==a[mid]){f=;break;}

                else if(a[mid]<ans)l = mid+;

                else r = mid-;

            }

        }

    }

 //   cout<<a[mid]<<endl;

    if(f)puts("YES");

    else puts("NO");

    return ;

}

手写二分