---
tags: 程式設計,APCS與競賽入門
slideOptions:
transition: 'fade' # 換頁動畫
---

# 常用問題解決方法

---

## 目錄
- 前綴和
- 差分
- 快速冪
- 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$ :cry:

----

### 如何改善

----

新增一個數列，第 $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.生產線](https://zerojudge.tw/ShowProblem?problemid=g597)

---

## 複雜度比較

----

| 技巧 | 單點修改 | 區間修改 | 區間查詢 |
| ------ |:---------------- |:----------------- | ---------------- |
| 前綴和 | $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$ :cry:
- 數字過大，因此每次都要取餘數 $(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</br>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();
}

---

## 大家加油


----

## 大家加油