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[1005];
int main() {
    set<int> 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<n;i++){
        for(int j=i;j<n;j++){
            int ans= -(a[i]*x*x+a[j]*x);
            if(s.count(ans)){
                f=1;
                break;
            }
        }
    }
    if(f) printf("YES\n");
    else printf("NO\n");
}

set解法

#include<bits/stdc++.h>

using namespace std;
map<int,int> 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<n;i++){
        for(int j=i;j<n;j++){
            int ans= -(a[i]*x*x+a[j]*x);
            if(mp[ans])
                return 0*puts("YES");
        }
    }
    printf("NO\n");
}

map

#include<bits/stdc++.h>

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<n;i++){
        for(int j=i;j<n;j++){
            int ans= -(a[i]*x*x+a[j]*x);
            if(ans>=-1000&&ans<=1000&&vis[ans+1000]){
                f=1;
                break;
            }
        }
    }
    if(f) printf("YES\n");
    else printf("NO\n");
}

hash最少时间

#include<bits/stdc++.h>

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<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=1;
                break;
            }
        }
    }
    if(f) printf("YES\n");
    else printf("NO\n");
}

sort + lower_bound

#include<bits/stdc++.h>
using namespace std;
int a[10000];
int main()
{
    int n,x;
    cin>>n>>x;
    for (int i=0;i<n;i++){
        scanf("%d",a+i);
    }
    sort(a,a+n);
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            long long tmp=1LL*a[i]*x*x+1LL*a[j]*x;
            if(*lower_bound(a,a+n,-tmp)==-tmp)return 0*puts("YES");
        }
    }
    puts("NO");
}

sort2

#include<bits/stdc++.h>
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]<ans)l = mid+1;
                else r = mid-1;
            }
        }
    }
 //   cout<<a[mid]<<endl;
    if(f)puts("YES");
    else puts("NO");
    return 0;
}