《挑戰程式設計競賽》閱讀筆記四

第五章

ALDS1_4_A Linear Search

//這是 我自己寫的 線性搜尋 還是很簡單的
#include <iostream>
using namespace std;

int main() {

    int S[];
    int T[];

    int n;
    int q;
    cin>>n;
    for(int i=;i<n;i++){
        cin>>S[i];
    }
    cin>>q;
    for(int i=;i<q;i++){
        cin>>T[i];
    }

    int count=;
    for(int i=;i<q;i++){
        for(int j=;j<n;j++){
            if(S[j]==T[i]){
                count++;
                break;
            }
        }
    }
    cout<<count<<endl;
    return ;
}
           

//書上代碼 采用 标記尾部的辦法 減少了 一次比較
#include <iostream>
using namespace std;

int searchQ(int A[],int n,int key){
    int i=;
    A[n] = key;
    while(A[i]!=key) i++;
    return i!=n;
}

int main() {

    int n,A[+],q,key,sum=;

    cin>>n;
    for(int i=;i<n;i++) cin>>A[i];

    cin>>q;
    for(int i=;i<q;i++){
        cin>>key;
        sum+=searchQ(A,n,key);
    } 
    cout<<sum<<endl;
    return ;
}
           

ALDS1_4_B Binary Search

#include <iostream>
using namespace std;

int BsearchQ(int A[],int n,int key){
    int l = ;
    int r = n;
    while(l<r){
        int mid=(l+r)/;
        if(A[mid]==key){
            return ;
        }else if(A[mid]<key){
            l=mid+;        
        }else {
            r=mid;
        }

    }
    return ;
}

int main() {
    //在送出測試中 這條代碼将速度 提高了 2/3 
    ios::sync_with_stdio(false); cin.tie();
    int n,A[+],q,key,sum=;

    cin>>n;
    for(int i=;i<n;i++) cin>>A[i];

    cin>>q;
    for(int i=;i<q;i++){
        cin>>key;
        sum+=BsearchQ(A,n,key);
    } 
    cout<<sum<<endl;
    return ;
}
           

ALDS1_4_C Dictionary

//哈希……
#include <stdio.h>
#include <string.h>

#define M 1046527
#define NIL (-1)
#define L 14

char H[M][L];

int getChar(char ch){
    if(ch=='A') return ;
    if(ch=='C') return ;
    if(ch=='G') return ;
    if(ch=='T') return ;
    else return ;
}

long long getKey(char str[]){
    long long sum=,p=;
    for(int i=;i<strlen(str);i++){
        sum+=p*(getChar(str[i]));
        p*=;
    }
    return sum;
}

int h1(int key){
    return key%M;
}
int h2(int key){
    return +(key%(M-));
} 

int find(char str[]){
    long long key,h;
    key = getKey(str);
    for(int i=;;i++){
        h=(h1(key)+i*h2(key))%M;
        if(strcmp(H[h],str)==) return ;
        else if(strlen(H[h])==) return ;
    }
    return ;
}

int insert(char str[]){
    long long key,h;
    key = getKey(str);
    for(int i=;;i++){
        h=(h1(key)+i*h2(key))%M;
        if(strcmp(H[h],str)==) return ;
        else if(strlen(H[h])==){
            strcpy(H[h],str);
            return ;
        }
    }
    return ;
}

int main(){
    int n,h;
    char str[L],com[];
    for(int i=;i<M;i++) H[i][]=; 
    scanf("%d",&n);
    for(int i=;i<n;i++){
        scanf("%s %s",com,str);
        if(com[]=='i'){
            insert(str);
        }else{
            if(find(str)){
                printf("yes\n");
            }else{
                printf("no\n");
            }
        }
    }
    return ;
}
           

ALDS1_4_D Allocation

#include <iostream>
using namespace std;
#define MAX 100000

int n,k;
long long T[MAX];

int check(long long P){
    int i=;
    for(int j=;j<k;j++){
        long long s=;
        while(s+T[i]<=P){
            s+=T[i];
            i++;
            if(i==n)return n;
        }
    }
    return i;
} 

int solve(){
    long long left = ;
    long long right = *;
    long long mid;
    while(right-left>){
        mid=(left+right)/;
        int v=check(mid);
        if(v>=n)right=mid;
        else left=mid;
    }
    return right;
}

int main() {
    cin>>n>>k;
    for(int i=;i<n;i++) cin>>T[i];
    long long ans=solve();
    cout<<ans<<endl;
    return ;
}