常用問題解決方法

目錄

  • 前綴和
  • 差分
  • 快速冪
  • for迴圈

前綴和

靜態求取區間和

index 1 2 3 4 5 6 7
value 5 6 2 8 10 1 4
  • 2~5 = 26
  • 1~7 = 36

共 \(N\) 個元素，進行 \(Q\) 次 \((N,Q \le 5 \times 10^5)\)

  • 暴力最差 \(\to O(N \times Q)\)
  • \((5 \times 10^5)^2 \approx 2.5 \times10^{11}\)
  • \(TLE\) \(\to\) \(sad\)
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

如何改善

新增一個數列，第 \(k\) 個存 1~k 的總和

index 1 2 3 4 5 6 7
value(V) 5 6 2 8 10 1 4
prefix sum(P) 5 11 13 21 31 32 36

區間 [l,r] 總合為 \(P_r-P_{l-1}\) ，特別定義 \(P_0=0\)

code










const int N=500010;

int n;
int v[N],psum[N];

// 建構 prefix sum 陣列
for(int i=1;i<=n;++i){
    psum[i]=psum[i-1]+v[i];
}

差分

差分是跟前綴和相反的操作，每一項都存與前一項的差

index 1 2 3 4 5 6 7
value(V) 5 6 2 8 10 1 4
Difference(D) 5 1 -4 6 2 -9 3

應用：區間加值，單次詢問

APCS 2021/11 3.生產線

複雜度比較

技巧 單點修改 區間修改 區間查詢
前綴和 \(O(n)\) \(O(n)\) \(O(1)\)
差分 \(O(1)\) \(O(1)\) \(O(n)\)
BIT \(O(\log_2{(n)})\) \(O(n\log_2{(n)})\) \(O(\log_2{(n)})\)

快速冪

  • 計算 \(a^x\)
  • 暴力 \(\to O(x)\)
  • 如果 \(x>10^8 \to TLE \to sad\)
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
  • 數字過大，因此每次都要取餘數 \((a=a \times a \; \% \; b)\)

解法 \(1\) \(:\) 遞迴

  1. \(a^{13} = a^6 \times a^6 \times a\)
  2. \(a^6 = a^3 \times a^3\)
  3. \(a^3 = a \times a \times a\)

歸納出

  • \(if \; x==0 \to return \; 1\)
  • \(if \; x==1 \to return \; a\)
  • \(if \; x \% 2 == 1 \to return \; a^{\frac{x}{2}} \times a^{\frac{x}{2}} \times a\)
  • \(if \; x \% 2 == 0 \to return \; a^{\frac{x}{2}} \times a^{\frac{x}{2}}\)

first code








int POW(int a,int x){
    if(x==0) return 1;
    if(x==1) return a;
    if(x%2==1) return POW(a,x/2)*POW(a,x/2)*a;
    // x%2==0
    return POW(a,x/2)*POW(a,x/2);
}

分析複雜度 \((\) 或讓電腦跑跑看 \()\)

  • 奇怪，怎麼還是一樣慢



if(x%2==1) return POW(a,x/2)*POW(a,x/2)*a;
// x%2==0
return POW(a,x/2)*POW(a,x/2);
  • 看看這兩行，是不是有多餘的步驟

nice code









int POW(int a,int x){
    if(x==0) return 1;
    if(x==1) return a;
    int t=POW(a,x/2);
    if(x%2==1) return t*t*a;
    // x%2==0
    return t*t;
}

複雜度 \(O(\log_2(x))\)

其實沒有那麼複雜

  • 將奇數次方 \(x\) 分解成 \(a^{x-1} \times a\)

簡化版








int POW(int a,int x){
    if(x==0) return 1;
    if(x%2==1) return POW(a,x-1)*a;
    // x%2==0
    int t=POW(a,x/2);
    return t*t;
}

解法 \(2\) \(:\) 迴圈建構

想像將 \(a^x\) 中的 \(x\) 以二進位表示

  • \(Ex :\) \(13_{(10)} = 00001101_{(2)}\)
  • \(a^{(2^k)}\) 可以在 \(O(k) = O(\log_2{2^k})\) 內完成
  • 將所需的次數乘進去
  • \(13 = 8 + 4 + 1 \to a^{13} = a^8 \times a^4 \times a\)

while 迴圈實作













using ll=long long;
const ll MOD=1e9+7;

ll POW(ll a,ll x){
    ll ret=1;
    while(x>0){
        if(x%2==1) ret=ret*a%MOD;
        a=a*a%MOD;
        x/=2;
    }
    return ret;
}

C++11
for 迴圈進階用法











vector<int> v(1000);

// 這樣也可以用來輸入
for(int &i:v){
    cin>>i;
}

for(int a:v){
    cout<<a<<" ";
}

Struct

舉個有趣的例子(除了對…而言)




























































































struct Friend{
    string type,name;// ...
    
    // 建構式
    Friend(string _name,string tp="cf"){
        name=_name;
        type=tp;
    }
    
    friend operator<(Friend a,Friend b){
        if(a.type=="gf"){
            if(b.type=="gf"){
                cout<<"你完蛋喽！"<<"\n";
            }
            return false;
        }else if(a.type=="bf"){
            if(b.type=="bf"){
                cout<<"妳完蛋喽！"<<"\n";
            }
            return false;
        }else{
            return a.name<b.name;
        }
    }
}

struct Friends{
    vector<Friend> fs;
    
    void add_friend(string name,string type="cf"){
        fs.emplace_back(name,type);
    }
    
    bool find_by_name(string name){
        return count(fs.begin(),fs.end(),name);
    }
    
    bool find_gf(){
        for(auto f:fs){
            if(f.type=="gf"){
                return true;
            }
        }
        return false;
    }
    
    bool find_bf(){
        for(auto f:fs){
            if(f.type=="bf"){
                return true;
            }
        }
        return false;
    }
    
    void check(){
        int a=0;
        for(auto f:fs){
            if(f.type=="gf" || f.type=="bf"){
                a++;
            }
        }
        
        if(a>1){
            cout<<"你準備要去世喽！";
        }
    }
    
    void sortFriends(){
        sort(fs.begin(),fs.end());
    }
    
    void printFriends(){
        for(auto f:fs){
            cout<<setw(20)<<f.name<<f.type<<"\n";
        }
    }
}

int main(){
    Friends mtmatt;
    
    mtmatt.add_friend("dws(戴偉璿)");
    mtmatt.add_friend("lju(李卓岳)");
    mtmatt.add_friend("lj(羅傑)","ac");// acquaintance 點頭之交
    mtmatt.add_friend("cpp","tool");
    
    mtmatt.sortFriends();
    
    mtmatt.printFriends();
}

大家加油

大家加油

Select a repo