ap325第六天

ap325第六天

一月 15, 2025

跳躍式二分搜基本寫法

  • 本段為找到第一個大於x的位置
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int jump_search(int a[],int n,int x){
        if(a[0]>=x) return 0;
        int po=0;
        for(int jump=n/2;jump>0;jump/=2){
            while(po+jump<n && a[po+jump]<x){
                po+=jump;
            }
        }
        return po+1;
    }

C++函數

  • binary_search()
  • lower_bound()
  • upper_bound()
    其實只要學會使用lower_bound()，這個函數是用來找到第一個大於等於某個值的位
    置，另外兩個都很像，upper_bound()找到第一個大於某值的位置，而
    binary_search()是只傳回是否找到。

lower_bound(first, last, t);
要求在[first, last)的範圍內以二分搜找到第一個大於或等於t的值，找到時回傳
所在位置，找不到時(t比最後一個大)，回傳last。以下有幾點請注意：

  • 找到時回傳的是位置，要得到陣列索引值就將它減去陣列起始位置。
  • 呼叫lower_bound()必須確定搜尋範圍是排好序的，如果你針對亂七八糟的資料
    以lower_bound()去進行二分搜，只會得到亂七八糟的結果，編譯器是不會告訴
    你沒排序的。
  • 搜尋範圍是傳統的左閉右開區間，也就是不含last；
  • 找不到時回傳last，通常這個位置是超過陣列的範圍，所以沒確定找到時不可以
    直接去引用該位置的值。
例題2-2

https://judge.tcirc.tw/problem/d011
自己寫的解:

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
#include <bits/stdc++.h>

using namespace std;
int jump_search(int s[],int n,int x){
    if(s[0]>=x){
        return 0;
    }
    int po=0;
    for(int jump=n/2;jump>0;jump/=2){
        while(jump+po<n && s[jump+po]<x){
            po+=jump;
        }
    }
    return po+1;
}
int main()
{
    int n;
    cin>>n;
    int p[n];
    int sor[n];
    for(int i=0;i<n;i++){
        cin>>p[i];
        sor[i]=p[i];
    }
    sort(sor,sor+n);
    
    vector<int > s;
    s.push_back(sor[0]);
    for(int i=1;i<n;i++){
        if(s.back()!=sor[i]){
            s.push_back(sor[i]);
        }
    }
    int a=s.size();
    int as[a];
    for(int i=a-1;i>=0;i--){
        as[i]=s.back();
        s.pop_back();
    }
    
    for(int i=0;i<n;i++){
        p[i]=jump_search(as,a,p[i]);
    }
    for(int i=0;i<n;i++){
        cout<<p[i]<<' ';
    }

    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;
#define N 100010

int distinct(int from[], int to[], int n) {
    if (n<1) return 0;
    vector<int> v(from, from+n); // copy from[] to v
    sort(v.begin(), v.end());
    to[0]=v[0];
    int num=1; // number of distinct number
    for (int i=1; i<n; i++)
        if (v[i]!=v[i-1]) // distinct
            to[num++] = v[i];
    return num;
}
int main() {
    int a[N], b[N],n, k;
    // input data
    scanf("%d", &n);
    for (int i=0;i<n;i++)
    scanf("%d", a+i);
    // sort distinct number to b
    k=distinct(a,b,n);
    // replace number with its rank
    for (int i=0;i<n;i++) {
        a[i] = lower_bound(b, b+k,a[i]) - b; // always found
    }
    // output
    for (int i=0;i<n-1;i++)
        printf("%d ",a[i]);
    printf("%d\n",a[n-1]);
    return 0;
}
  • 答案細節:
    C++ 中，陣列作為函數參數時，是以指標形式傳遞的。也就是說，當你將 b 作為參數傳入函數 distinct() 時，實際上傳遞的是 b 的記憶體地址。因此，distinct() 函數內對 b 陣列的操作會直接修改原來的 b 陣列的內容。
    所以b會自動改變。

用map實作:

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
 #include <bits/stdc++.h>
using namespace std;
#define N 100010


typedef long long LL;
int main()
{
    int a[N],n,k;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    map<int,int> S; //map第一位是key，第二位是值 first,second
    for(int i=0;i<n;i++){
        S[a[i]]=0;
    }
    int r=0;
    for(auto it=S.begin();it!=S.end();++it){ //it是迭代器，指向 map 中的每個鍵值對。
        it->second=r++;
    }
    for(int i=0;i<n;i++){
        a[i]=S.find(a[i])->second; 
    }
    for(int i=0;i<n;i++){
        cout<<a[i]<<' ';
    }
    return 0;
}

關於stl資料結構(DS)
https://zrn-code.github.io/2020/07/18/STL/

2-3快速冪

https://judge.tcirc.tw/problem/d012
最簡單寫法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int main()
{
    LL x,y,p;
    cin>>x>>y>>p;
    LL t=1;
    for(int i=1;i<=y;i++){
        t=(t*x)%p;
    }
    cout<<t;
    return 0;
}

但實在跑太慢拉~
運用分治、遞迴把它優化一下:
O(y)->O(log y)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
LL exp(LL x,LL y,LL p){ //exponentiation 快速指數運算
    if(y==0){
        return 1;
    }
    if(y & 1){ //如果y是奇數，則-1迭代
        return (exp(x,y-1,p)*x)%p;
    }
    LL t=exp(x,y/2,p); //y是偶數直接計算，因為:x^(y/2)*x^(y/2)=x^y
    return (t*t)%p; 
}
int main()
{
    LL x,y,p;
    cin>>x>>y>>p;
    cout<<exp(x,y,p);
    return 0;
}

2-4快速冪200位

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

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

using namespace std;
typedef long long LL;
LL exp(LL x,LL y,LL p){
    if(y==0){
        return 1;
    }
    if( y & 1) return (exp(x,y-1,p)*x)%p;
    LL t=exp(x,y/2,p);
    return (t*t)%p;
}
int main()
{
    string x;
    LL y,p;
    cin>>x>>y>>p;
    LL xint=x[0]-'0';
    for(int i=1;i<x.size();i++){ 
        xint=((xint*10)%p+(x[i]-'0'))%p;
    }
    cout<<exp(xint,y,p);
    return 0;
}

當x大到超過long long的時候，我們需要先求x除以p的餘
數，而除以p的餘數可以一位一位的累加計算。例如x=123, p=5，x可以看成
(1*10+2)10+3，所以x除以p的餘數也就等於
((((110%p+2)%p)*10)%p+3)%p。
所以要邊把string轉成int邊mod

2-6Two-Number problem

https://judge.tcirc.tw/problem/d015
用二分搜加速搜尋速度以A的元素在B中滑動找解

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;
typedef long long LL;
LL A[100010];
LL B[100010];
int bsearch(LL b[],int n,LL goal){
    if(b[0]>goal){
        return 0;
    }
    int beginn=0;
    for(int jump=n/2;jump>0;jump/=2){
        while((beginn+jump)<n && b[beginn+jump]<goal){
            beginn+=jump;
        }
    }
    if(b[beginn+1]==goal)  return 1;
    return 0;
}
int main()
{
    int m,n;
    LL k;
    cin>>m>>n>>k;
    for(int i=0;i<m;i++){
        cin>>A[i];
    }
    for(int i=0;i<n;i++){
        cin>>B[i];
    }
    sort(B,B+n);
    LL goal;
    int sum=0;
    for(int i=0;i<m;i++){
        goal=k-A[i];
        sum+=bsearch(B,n,goal);
    }
    cout<<sum;
    return 0;
}

  • 順便附上剛剛寫的leetcode minimize-xor
    https://leetcode.com/problems/minimize-xor/
    這題可以練習bit運算

    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
    class Solution {
    public:
        long long result;
        void cmp(int total1, int total2, vector<int> v) {
            if (total1 == total2) {
                long long i = 1;
                while (!v.empty()) {
                    result += i * v.back();
                    i *= 2;
                    v.pop_back();
                }
                return;
            }
            if (total1 > total2) {
                for (int i = v.size() - 1; i >= 0; i--) {
                    if (v[i] == 1) {
                        v[i] = 0;
                        cmp(total1 - 1, total2, v);
                        break;
                    }
                }
                /*for (auto &t : v) {
                    if (t == 1) {
                        t = 0;
                        cmp(total1 - 1, total2, v);
                        break;
                    }
                }*/
            } else if (total1 < total2) {
                for (int i = v.size() - 1; i >= 0; i--) {
                    if (v[i] == 0) {
                        v[i] = 1;
                        cmp(total1 + 1, total2, v);
                        break;
                    }
                }
            }
        }
        int minimizeXor(int num1, int num2) {
            result = 0;
            int total1 = 0;
            int total2 = 0;
            while (num2 > 0) {   
                total2 += num2 % 2;
                num2 /= 2;
            }
            vector<int> v;
            while (num1 > 0) {   
                total1 += num1 % 2;
                v.push_back(num1 % 2);
                num1 /= 2;
            }
            reverse(v.begin(), v.end());
            while (v.size() < 32) {
                v.insert(v.begin(), 0);
            }
            cmp(total1, total2, v);
            return result;
        }
    };

  • leetcode動態規劃、遞迴
    https://leetcode.com/problems/combination-sum-iv/
    我的菜菜寫法:

    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
    class Solution {
    public:
        int recursion(int n, vector<int> nums, vector<int>& dp) {
            if (n < 0) {
                return 0;
            }
            if (n == 0) {
                return 1;
            }
            if (dp[n] != -1) {
                return dp[n]; // 如果已經計算過，直接返回結果
            }
            int result = 0;
            for (auto k : nums) {
                result += recursion(n - k, nums, dp); // 累加所有可能的結果
            }
            dp[n] = result; // 記錄計算結果以提高效率
            return result;
        }
        
        int combinationSum4(vector<int>& nums, int target) {
            vector<int> dp(target + 1, -1); // 動態規劃數組，初始化為 -1
            return recursion(target, nums, dp);
        }
    };

    動態規劃更強的寫法:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution {
    public:
        int combinationSum4(vector<int>& nums, int target) {
            vector<unsigned int> dp(target+1,0);
            dp[0]=1;
            for(int i=1;i<=target;i++){
                for(int j:nums){
                    if(i-j>=0) dp[i]+=dp[i-j];
                }
            }
            return dp[target];
        }
    };

    外層迴圈：for(int i = 1; i <= target; i++)，表示我們從 1 一直計算到 target，對每個目標值 i，我們都試圖通過減去 nums 中的數字來達到這個目標。
    內層迴圈：for(int j : nums)，表示對於 nums 中的每一個數字 j，如果 i - j >= 0，即當 i - j 是有效的（不小於 0）時，我們將 dp[i - j] 的值加到 dp[i] 上。
    這是因為，如果我們可以從 i - j 達到 i，那麼所有能達到 i - j 的組合都可以通過再加上j來達到 i。