AP325第一天筆記

AP325第一天筆記

一月 08, 2025

自學筆記

big(O)

  • 10^9是2^31次方bits內，也就是int的大小(int可容納2*10^9)
  • 降低時間複雜度:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    #include <bits/stdc++.h> 
    using namespace std; 
     
    int main() { 
        ios::sync_with_stdio(0); 
        cin.tie(0); 
        // code here 
        return 0; 
    }

第一章

遞迴(recursive)

  • 1-3支點切割:

    線性搜尋解答:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    LL s[50010];
    LL cut(int left,int right){
        if(right-left<=1) return 0;
        LL k=(s[right]-s[left])/2;
        LL beginn=left;
        while(s[beginn]<=s[left]+k){
            beginn++;
        }
        if(s[beginn-1]-s[left]>=s[right]-s[beginn]){
            beginn--;
        }
        LL len=s[right]-s[left];
        return len+cut(left,beginn)+cut(beginn,right);
    }
    int main() {
        ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        int i,n,l;
        cin>>n>>l;
        s[0]=0;
        s[n+1]=l;
        for(i=1;i<=n;i++){
            cin>>s[i];
        }
        cout<<cut(0,n+1);

        return 0;
    }

  • 跳躍式二分搜:

  • 跳躍式二分搜解答:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    LL s[50010];
    LL cut(int left,int right){
        if((right-left)<=1) return 0;
        int m=left;
        LL k=s[left]+(s[right]-s[left])/2;
        for(int jump=(right-left)/2;jump>0;jump/=2){
            while(m+jump<right && s[m+jump]<k){
                m+=jump;
            }
        }
        if(s[m]-s[left]<s[right]-s[m+1]){
            m++;
        }
        return s[right]-s[left]+cut(left,m)+cut(m,right);
    }
    int main() {
        ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        int i,n,l;
        cin>>n>>l;
        s[0]=0;
        s[n+1]=l;
        for(i=1;i<=n;i++){
            cin>>s[i];

        }

        cout<<cut(0,n+1);

        return 0;
    }