《挑战程序设计竞赛》Note_1

时间复杂度：

1000000 游刃有余
10000000 勉勉强强
100000000 很悬，仅限循环体非常简单的情况
二分查找复杂度是O（logn）,即使n变得很大时，对数时间的算法依然非常迅速
排序O（nlogn）
循环O（n^3logn）

复杂抽签问题：1.1

首先呢，是最初始的状态：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,m,kk[51*51],k[51];
int main()
{
    freopen("data.in.txt","r",stdin);
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>k[i];
    for(int a=0;a<n;a++）
                for(int b=0;b<n;b++)
                          for(int b=0;b<n;b++)
                                  for(int b=0;b<n;b++)
                                            if(k[a]+k[b]+k[c]+k[d]==m)
                                                     f=true;
        if(f)
                cout<<"YES";
        else
                cout<<"NO";
    return 0;
}

然后将最后一个条件换了
如果你真的去用四个for，机器比你还先爆，所以才要改写，不过这思路在做c语言作业时，家长就和我说过，只不过我当时没有想到可以用到acm上。就是将内侧的循环替换成二分搜索算法，时间复杂度就变成
排序O（nlogn）时间
循环O（n^3logn）时间
合起来就是O（n^3logn）时间

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,m,k[51];
bool binary_search(int x){
    int l=0,r=n;
    while(r-l){
        int i=(l+r)/2;
        if(x==k[i]) return true;
        else if(x<k[i]) l=i+1;
        else    r=i;
    }
    return false;
}

int main()
{
    freopen("data.in.txt","r",stdin);
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>k[i];
    bool f=false;
    sort(k,k+n);
    for(int a=0;a<n;a++)
        for(int b=0;b<n;b++)
            for(int c=0;c<n;c++){
                if(binary_search(m-k[a]-k[b]-k[c]))
                    f=true;
            }   
    if(f)
        cout<<"YES";
    else
        cout<<"NO";
    return 0;
}

O（n^2logn）算法

今天还学到了一个新的办法：
排序：O（n^2logn） 这里排了两次序
循环：O（n^2logn）

    #include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    int n,m,kk[51*51],k[51];
    bool binary_search(int x){
        int l=0,r=n*n;
        while(r-l){
            int i=(l+r)/2;
            if(x==kk[i])        return true;
            else if(x>kk[i])    l=i+1;
            else    r=i;
        }
        return false;
    }

    void solve(){
        for(int c=0;c<n;c++)
            for(int d=0;d<n;d++)
                kk[c*n+d]=k[c]+k[d];
        sort(kk,kk+n*n);
        bool f=false;
        for(int a=0;a<n;a++)
            for(int b=0;b<n;b++)
                if(binary_search(m-k[a]-k[b]))
                    f=true;
        if(f)
            cout<<"YES";
        else
            cout<<"NO";
    }

    int main()
    {
        freopen("data.in.txt","r",stdin);
        cin>>n>>m;
        for(int i=0;i<n;i++)
            cin>>k[i];
        bool f=false;
        sort(k,k+n);
        solve();
            return 0;
    }

其实这里面用了n*n是将范围扩大了，防止数组越界。