常用問題解決方法

靜態求取區間和

• 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\)

如何改善

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

區間 [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];
}
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];
}

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

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

APCS 2021/11 3.生產線

• 計算 \(a^x\)
• 暴力 \(\to O(x)\)
• 如果 \(x>10^8 \to TLE \to sad\)
• 數字過大，因此每次都要取餘數 \((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;
}

vector<int> v(1000);
 
// 這樣也可以用來輸入
for(int &i:v){
    cin>>i;
}
 
for(int a:v){
    cout<<a<<" ";
}

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

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

大家加油