ap325第二章

二月 15, 2025

AP325

第二章排序

sort
sort()除了前兩個參數指定範圍之外，還可以傳入
第三個參數，第三個參數是一個比較函數，這個函數負責告訴sort()排序的順序是什
麼：比較函數必須傳入兩個參數，如果第一個參數要排在第二個的前面就回傳true，
否則回傳false。
簡單來說:
1
2
3
bool cmp(int j,int i){
return j>i;
}

https://leetcode.com/problems/find-the-prefix-common-array-of-two-arrays/?envType=daily-question&envId=2025-01-14

心血來潮寫的leetcode每日一題

class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int n=A.size();
        int m=n;
        int P_A[52]={};
        int P_B[52]={};
        int Aarr[52];
        int Barr[52];
        vector<int> ans; //寫成vector<int> ans(n,0)的話意思是大小為n，數據為0
        int num=0;
        for(int i=n-1;i>=0;i--){
            Aarr[i]=A.back();
            Barr[i]=B.back();
            A.pop_back();
            B.pop_back();
        }
        for(int i=0;i<n;i++){
            P_A[Aarr[i]]+=1;
            P_B[Barr[i]]+=1;
            if(P_A[Aarr[i]]>0 && P_B[Aarr[i]]>0){
                num++;
                P_A[Aarr[i]]--;
                P_B[Aarr[i]]--;
            }
            if(P_A[Barr[i]]>0 && P_B[Barr[i]]>0){
                num++;
                P_A[Barr[i]]--;
                P_B[Barr[i]]--;
            }
            ans.push_back(num);
        }
        return ans;
    }
};

二分搜基本寫法

#include <bits/stdc++.h>

using namespace std;
int bsearch(int a[],int left,int right,int x){
    while(left<=right){
        int mid=(left+right)/2;
        if(a[mid]==x){
            return mid;
        }
        if(a[mid]<x){
            left=mid+1;
        }
        if(a[mid]>x){
            right=mid-1;
        }


    }
    return -1;
}
int main()
{
    int p[100];
    for(int i=0;i<100;i++){
        p[i]=rand()%100; //random 保證數字1到99
    }
    sort(p,p+100);
    for(int i=0;i<100;i++){
        cout<<p[i]<<' ';
    }
    cout<<'\n';
    cout<<bsearch(p,0,100-1,p[7]);
    return 0;
}

跳躍式二分搜基本寫法

本段為找到第一個大於x的位置

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
自己寫的解:

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

教科書解:

#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實作:

 #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
最簡單寫法:

#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)

#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

#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中滑動找解

#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運算

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/
我的菜菜寫法:

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

動態規劃更強的寫法:

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。

2-6set寫法

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

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
int main()
{
    int m,n;
    LL k;
    cin>>m>>n>>k;
    set<LL>s;
    int A[m];
    LL x;
    for(int i=0;i<m;i++){
        cin>>A[i];
    }
    for(int i=0;i<n;i++){
        cin>>x;
        s.insert(x);
    }
    sort(A,A+m);
    int total=0;
    for(int i=0;i<m;i++){
        if(s.find(k-A[i])!=s.end()){ //s.find(k-A[i])會返回找到他的位置
            total++;
        }
    }
    cout<<total;
    return 0;
}

2-7互補團隊

https://judge.tcirc.tw/problem/d016
自己練習，tle的答案，感覺寫得很亂，進步空間很大

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
LL total=0;
int n;
set<pair<int,int>> sss;
void recursion(string s[],int m,map<char,int> ma,int now,int deep){
    set<char> se;
    for(int i=0;i<s[now].size();i++){
        se.insert(s[now][i]);
    }
    for(auto k:se){
        ma[k]++;
    }
    if(deep==1){
        bool valid=true;
        for(char ch='A';ch<='A'+m-1 && ch<='Z';ch++){
            if(ma[ch]<=0|| ma[ch]>=2){
                valid=false;
                return;
            }
        }
        if(valid){
            total++;
            return;
        }
    }
    for(int i=0;i<n;i++){
        if(i!=now && sss.find({min(i,now),max(i,now)})==sss.end()){
            sss.insert({min(i,now),max(i,now)});
            recursion(s,m,ma,i,1);
        }
    }

}
int main()
{
    int m;
    cin>>m>>n;
    map<char,int> ma;
    for(char ch='A';ch<='Z' ;ch++){
        ma[ch]=0;
    }
    string str[n];
    for(int i=0;i<n;i++){
        cin>>str[i];
    }
    for(int i=0;i<n;i++){     
        recursion(str,m,ma,i,0);
    }
    cout<<total;
    return 0;   
}

看提示寫的:

#include <bits/stdc++.h>

using namespace std;
int k=1;
int m,n;
int main()
{

    cin>>m>>n;
    k=(1<<m)-1;
    //cout<<k<<'\n';
    string s[n];
    for(int i=0;i<n;i++){
        cin>>s[i];
    }

    set<int> se;
    for(int i=0;i<n;i++){
        int team=0;
        for(int j=0;j<s[i].size();j++){
            /*if(s[i][j]=='A'){
                team|=1;
            }*/
            team |=(1<<(s[i][j]-'A'));
        }
        se.insert(team);
    }

    int total=0;

    for(auto t:se){
        if(se.find(k-t)!=se.end()){
            total++;
        }
    }
    cout<<total/2; //由這邊可以發現這題還可以優化，因為total被計算兩次
    return 0;
}

2-9子集合乘積(折半枚舉)

https://judge.hlhs.hlc.edu.tw/ShowProblem?problemid=e036
不足以通過這一題所有測資。這個程式的方法也很直接，我們逐一考慮每一個
元素，以一個map M1來記錄著目前所有可能的子集合乘積，相同的乘積只記錄一筆，
但記錄能產生此乘積的子集合個數。對於下一個元素a[i]，把原有的所有可能在乘上
此新元素，就是新的可能乘積。在計算過程，新的乘積不能直接加到原來的裡面，否則
無法分辨新舊。因此要利用一個 map M2 來暫存，當一個元素處理完畢後交換 M1 與
M2，以便下一個元素時再從M1計算到M2。
(我看不懂…)

// subset product = 1 mod P, slow method 
#include<bits/stdc++.h> 
using namespace std; 
typedef long long LL;
int main() { 
    int i, n; 
    LL p, a[50]; 
    scanf("%d%lld", &n, &p); 
    for (i=0;i<n;i++) 
        scanf("%lld", &a[i]); 
    map<LL,LL> M1; // (product, number) 
    M1[a[0]]=1; // The first element appear once 
    for (i=1;i<n;i++) { // for each element 
        // compute from M1 to M2 
        map<LL,LL> M2(M1); // copy M1 to M2 
        for (auto e:M1) { 
            LL t = (e.first*a[i])%p; 
            M2[t] = (M2[t] + e.second)%p; 
        } 
        M2[a[i]] = (M2[a[i]] + 1)%p; // for {a[i]} 
        M1.swap(M2); 
    } 
    printf("%lld\n", M1[1]); 
    return 0; 
}

接下來要來學折半枚舉

查看评论

ap325第二章

ap325第二章

第二章 排序

二分搜基本寫法

跳躍式二分搜基本寫法

C++函數

例題2-2

2-3快速冪

2-4快速冪200位

2-6Two-Number problem

2-6set寫法

2-7互補團隊

2-9子集合乘積(折半枚舉)

第二章排序