ap325第一章

ap325第一章

二月 17, 2025

自學筆記

big(O)

  • 10^9是2^31次方bits內，也就是int的大小(int可容納2*10^9)
  • 大寫轉小寫(ASCII code)
    1
    2
    3
    4
    5
    6
    char ch='A';
        for(int i=0;i<32;i++){ //兩者差32
            ch++;

        }
        cout<<ch;
  • 進行位元運算時
    1
    2
    3
    4
    5
    for(int i=0;i<n;i++){
     if(1<<i&k){ //k放的要是十進制，而不是像是二進制的值
      ans++;    //ex:放10而不是1010
    }
    }
  • 10進制轉2進制:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    #include <bits/stdc++.h>

    using namespace std;

    int main()
    {
        int n;
        cin>>n;
        vector<int> v;
        while(n){
            v.push_back(n%2);
            n/=2;
        }
        while(!v.empty()){ //轉換出來會是倒過來的下面是證明
            cout<<v.back();
            v.pop_back();
        }
        return 0;
    }
  • 降低時間複雜度:
    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; 
    }

kmp字串演算法

可以讓字串比對從O(mn)簡化為O(m+n)
next序列為尋找相同前後綴長度，next序列的定義過程是其中最難的部分，關鍵:前後綴迭代
例題:
https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/

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
34
35
36
37
class Solution {
public:
    int nextt[10010];
    void find_nextt(string patt){
        nextt[0];
        int prefix=0;
        for(int i=1;i<patt.size();i++){
            while(prefix>0&&patt[prefix]!=patt[i]){
                prefix=nextt[prefix-1];
            }
            if(patt[prefix]==patt[i]){
                prefix++;
            }
            nextt[i]=prefix;
        }
    }
    int strStr(string haystack, string needle) {
        find_nextt(needle);
        int i=0;
        int j=0;
        while(i<haystack.size()){
            if(haystack[i]==needle[j]){
                i++;
                j++;
            }else if(j>0){
                j=nextt[j-1];
            }else{
                i++;
            }
            if(j==needle.size()){
                return i-j;
            }
        }
        return -1;
    }

};

以下這題:
s = “abcabcabcabc” 对应 next 数组为：000 123 456 789，s.length() = 12 = 9(next 数组最后一位) + 3(重构子串长度)，3 是 s长度的因数，所以 s 能被子串重构
https://leetcode.com/problems/repeated-substring-pattern/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
   
    
    bool repeatedSubstringPattern(string s) {
        int nextt[10010]={};
        int prefix=0;
        nextt[0]=0;
        for(int i=1;i<s.size();i++){
            while(prefix>0&&s[i]!=s[prefix]){
                prefix=nextt[prefix-1];
            }
            if(s[i]==s[prefix]){
                prefix++;
            }
            nextt[i]=prefix;
        }
        if (nextt[s.size() - 1] == 0) return false;
        return (s.size()%(s.size()-nextt[s.size()-1]))==0;
        
    }
};

第一章

遞迴(recursive)

  • 遞迴中使用容器或是陣列要格外小心，因為寫錯的話可能會因為沒有正確回溯而失敗
    ex: 

    1
    2
    void rec(string s, vector<bool> &used) //上面這個所有rec會共用同一個容器，記憶體會比較小，但操作容易出錯
    void rec(string s, vector<bool> used)  //下面這個每一次rec都會創造一個used記憶體較大，但除錯較簡單

    ex:

    1
    void rec(string s, int t[]) //會共用容器，因為c++中傳遞陣列參數，陣列參數會退化為指標

  • 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;
    }

遞迴

  • 支點切割

https://zerojudge.tw/ShowProblem?problemid=f638
寫了兩個小時還是錯的決定先休息，放這裡之後寫，寫了兩個小時發現我沒看完題目
放一個正解網址https://sites.google.com/view/zsgititit/home/jin-jiec-cheng-shi-she-ji/apcs201802%E7%AC%AC3%E9%A1%8C%E6%94%AF%E9%BB%9E%E5%88%87%E5%89%B2

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
LL s[500100]={};
int T=0;
/*
5 1
1 2 3 4 100
*/
LL cut(int left,int right,int boundd){
    if((right-left)<=1 ||(boundd)>=T){
        return 0;
    }

    int k=left+1;
    LL low=LLONG_MAX;
    //int low=abs((s[left]-s[left-1])-(s[right]-s[left+1]));//差值
    //cout<<low<<" low \n";
    for(int i=left+1;i<=right-1;i++){
        if(abs((s[i-1]-s[left-1])-(s[right]-s[i]))<low){
            k=i;
            low=abs((s[i-1]-s[left-1])-(s[right]-s[i]));
            //cout<<low<<" low "<<k<<" k \n";
        }

    }
    boundd++;
    return s[k]-s[k-1]+cut(left,k-1,boundd)+cut(k+1,right,boundd);

}


int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    cin>>T;
    LL g;
    s[0]=0;
    for(int i=1;i<=n;i++){
        cin>>g;
        s[i]=g+s[i-1];
    }
    /*for(int i=0;i<=n;i++){
        cout<<s[i]<<' ';
    }
    cout<<'\n';*/
    cout<<cut(1,n,0);
    return 0;
}

1-6最接近區間和

  • 假設陣列A[1..n]中存放著某些整數，另外給了一個整數K，請計算哪一個連續區
    段的和最接近K而不超過K。
    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
    34
    35
    36
    #include <iostream>

    using namespace std;
    int K;

    int main()
    {
        int n;
        cin>>n>>K;
        int s[n];
        for(int i=0;i<n;i++){
            cin>>s[i];
        }
        int sum=0;
        int bestleft=0;
        int bestright;
        int bestans=1000;
        int right;
        int left=0;
        for(int i=0;i<n;i++){
            sum+=s[i];
            right=i;
            while(sum>K){
                sum-=s[left];
                left++;
            }
            if(abs(K-sum)<=abs(K-bestans)){
                bestans=sum;
                bestleft=left;
                bestright=right;
            }
        }
        cout<<bestleft<<' '<<bestright;
        return 0;
    }

1-7子集合乘積

https://judge.tcirc.tw/problem/d006

  • 寫出這個答案的老師真的好厲害
    以下為暴力解，所以當測試資料過大時會TLE:
    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
    #include <iostream>

    using namespace std;

    int main()
    {
        int n;
        int P=10009; 
        int A[26]; //集合最大只有25個元素，因為0<n<26
        cin>>n;
        int sum=0;
        for(int i=0;i<n;i++){
            cin>>A[i];
        } 
        for(int i=1;i<(1<<n);i++){  // 1<<n的範圍就是2^n，所以這裡以binary i的數字1代表元素在內
            long long prod=1;       
            for(int j=0;j<n;j++){
                if(i & (1<<j)){         //如果binary i的第j位為一，則列進prod內
                    prod=(prod*A[j])%P; //先mod跟最後再mod根據公式結果一樣
                }
            }
            if(prod==1){
                sum++;
            }
        }
        cout<<sum;
        return 0;
    }

以下為遞迴解，時間複雜度較小，如果是迴圈解複雜度為O(2^n)遞迴解的話O(n*2^n)

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
#include <iostream>

using namespace std;
int P=10009;
int A[26];
int ans=0;
int prod=1;
int n;
void rec(int i,int prod){
    if(i>=n){
        if(prod==1) ans++;
        return;
    }
    rec(i+1,(prod*A[i])%P);
    rec(i+1,prod);
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    rec(0,1);
    cout<<ans-1;
    return 0;
}

1-8子集合的和

https://judge.tcirc.tw/problem/d007

  • 跟上面那題的解題思路大差不遠
    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
    34
    35
    36
    #include <iostream>

    using namespace std;
    typedef long long LL;
    LL P;
    int A[26];
    int n;
    LL bestans=0;
    void rec(int i,LL sum){
        //cout<<i<<" i "<<bestans<<'\n';

        if(sum>P){
            return;
        }
        if(i>=n){
            if(P-sum<P-bestans){
                bestans=sum;

            }
            return;
        }

        rec(i+1,sum+A[i]);
        rec(i+1,sum);
    }
    int main()
    {
        cin>>n;
        cin>>P;
        for(int i=0;i<n;i++){
            cin>>A[i];
        }
        rec(0,0);
        cout<<bestans;
        return 0;
    }

八皇后問題

  • n皇后暴搜解答:
    (時間複雜度會爆)
    O(n2*n!)
    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
    #include <bits/stdc++.h>

    using namespace std;
    int nq(int n){
        int P[14];
        int total=0;
        for(int i=0;i<n;i++){
            P[i]=i;
        }
        do{
            bool valid=true;
            for(int i=0;i<n;i++){
                for(int j=i+1;j<n;j++)
                    if(abs(P[i]-P[j])==j-i){ //P[i]-P[j])==j-i可以比對是否在同一斜線
                        valid=false;
                        break;
                    }
            }
            if(valid){
                total++;
            }
        }while(next_permutation(P,P+n)); //字典排序P到P+n
        return total;
    }
    int main()
    {
        for(int i=1;i<12;i++){
            cout<<nq(i)<<' ';
        }
        return 0;
    }

    以下為遞迴解:
    O(n*n!)
    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 <iostream>

    using namespace std;
    int nqr(int n,int k,int p[]){
        int total=0;
        if(k>=n){
            return 1;
        }
        for(int i=0;i<n;i++){   //嘗試當前行的每一個位置
            bool valid=true;
            for(int j=0;j<k;j++){
                if(p[j]==i || abs(i-p[j])==k-j){ //檢查是否與前面衝突
                    valid=false;
                    break;
                }
            }
            if(!valid){
                continue;
            }
            p[k]=i;
            total+=nqr(n,k+1,p);
        }

        return total;
    }
    int main()
    {
        int p[15];
        for(int i=1;i<12;i++){
            cout<<nqr(i,0,p)<<' ';
        }
        return 0;
    }
    遞迴解2
    (降低複雜度)
    比 O(n*n!) 低，因為會先標記後才進入遞迴
    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
    34
    35
    36
    37
    38
    39
    40
    #include <bits/stdc++.h>

    using namespace std;
    int nqr(int n,int k,int p[]){
        if(k>=n) return 1;
        bool valid[n];
        int total=0;
        for(int i=0;i<n;i++) valid[i]=true; // y軸
        // mark
        for(int j=0;j<k;j++){
            valid[p[j]]=false; //p[j]是(p[j],j)的y軸數據
            int i=p[j]+k-j; //i=y軸數據+(當前x軸-x軸數據) 往左下
            if(i<n){
                valid[i]=false;
            }
            i=p[j]-k+j; //往右上
            if(i>=0){
            valid[i]=   false;
            }

        }
        for(int i=0;i<n;i++){
            if(valid[i]){
                p[k]=i;
                total+=nqr(n,k+1,p);
            }
        }

        return total;
    }


    int main()
    {
        int p[15];
        for(int i=1;i<12;i++){
            cout<<nqr(i,0,p)<<' ';
        }
        return 0;
    }

1-10最多得分的皇后

https://judge.tcirc.tw/problem/d008

  • 延續第四天，然加上一個判斷要選哪幾列有皇后的排列就好(最佳得分並不一定是每一列皆有皇后)
    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
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    #include <iostream>

    using namespace std;
    int point[15][15];
    int best=0;
    void qr(int i,int K,int p[],int bound,int total){
        if(K>=bound){
            if(total>best){
                best=total;
            }
            return;
        }
        if(!(i & (1<<K))){
            qr(i,K+1,p,bound,total);
            return;
        }
        bool valid[bound];
        for(int j=0;j<bound;j++){
            valid[j]=true;
        }
        for(int j=0;j<K;j++){
            if(i& (1<<j) ){
                valid[p[j]]=false;
                int up=p[j]+K-j; //i=y軸數據+(當前x軸-x軸數據) 往左下
                if(up<bound){
                    valid[up]=false;
                }
                int down=p[j]-K+j; //往右上
                if(down>=0){
                    valid[down]=false;
                }

            }
        }
        for(int j=0;j<bound;j++){
            if(valid[j]){
                p[K]=j;
                qr(i,K+1,p,bound,total+point[j][K]);
            }
        }
    }
    int main()
    {
        int p[15];
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>point[i][j];
            }
        }
        for(int i=1;i<(1<<n);i++){ //將1向左移動
            int total=0;
            qr(i,0,p,n,total);
        }

        cout<<best;
        return 0;
    }

1-10刪除矩形邊界

https://judge.tcirc.tw/problem/d009

  • 有更快的dp寫法，不過這邊先用遞迴暴力解
    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
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    #include <iostream>

    using namespace std;
    int s[13][13];
    int best=100000;
    void rec(int left_y,int left_x,int right_y,int right_x,int cost){
        if(abs(left_x-right_x)==0 || abs(left_y-right_y)==0){
            if(cost<best){
                best=cost;
            }
            return;
        }
        int one=0;
        int zero=0;
        int ans=0;
        for(int i=left_x;i<=right_x;i++){
            if(s[left_y][i]==1){
                one++;
            }else{
                zero++;
            }
            ans=min(one,zero);
        }
        rec(left_y+1,left_x,right_y,right_x,cost+ans); //1
        one=0;
        zero=0;
        for(int i=left_y;i<=right_y;i++){
            if(s[i][left_x]==1){
                one++;
            }else{
                zero++;
            }
            ans=min(one,zero);
        }
        rec(left_y,left_x+1,right_y,right_x,cost+ans); //2
        one=0;
        zero=0;
        for(int i=right_x;i>=left_x;i--){
            if(s[right_y][i]==1){
                one++;
            }else{
                zero++;
            }
            ans=min(one,zero);
        }
        rec(left_y,left_x,right_y-1,right_x,cost+ans); //3
        one=0;
        zero=0;
        for(int i=right_y;i>=left_y;i--){
            if(s[i][right_x]==1){
                one++;
            }else{
                zero++;
            }
            ans=min(one,zero);
        }
        rec(left_y,left_x,right_y,right_x-1,cost+ans); //4
    }
    int main()
    {
        int m,n;
        cin>>m>>n;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                cin>>s[i][j];
            }
        }
        rec(0,0,m-1,n-1,0);
        cout<<best;
        return 0;
    }

leetcode 遞迴題目

https://leetcode.com/problems/letter-tile-possibilities/?envType=daily-question&envId=2025-02-17
如果要找所有組合的話以下是遞迴範例(一定有其他更快的)，考試複習這題不錯

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
34
35
36
37
38
39
40
41
42
class Solution {
public:
    // 使用 map 收集所有不重複的排列結果
    map<string,int> m;
    string goal;
    
    // 用 vector<bool> 來記錄 goal 中哪些位置已被使用
    void rec(string s, vector<bool> &used) {
        if(s.size() == goal.size()){
            m[s]++;
            return;
        }
        for (int i = 0; i < goal.size(); i++) {
            if (!used[i]) {
                used[i] = true;              // 標記這個位置已使用
                rec(s + goal[i], used);      // 遞迴呼叫
                used[i] = false;             // 回溯：還原這個位置
            }
        }
    }
    
    int numTilePossibilities(string tiles) {
        int si = tiles.size();
        // 用 bitmask 產生所有子集（非空）
        for (int mask = 1; mask < (1 << si); mask++) {
            string s = "";
            for (int j = 0; j < si; j++) {
                if (mask & (1 << j)) {
                    s += tiles[j];
                }
            }
            goal = s;
            vector<bool> used;
            for(int i=0;i<goal.size();i++){
                used.push_back(false);
            }
            rec("", used);
        }
        return m.size();
    }
};