# 常用問題解決方法 --- ## 目錄 - 前綴和 - 差分 - 快速冪 - 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 ```cpp= [1-9|7-9] 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 ```cpp= 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); } ``` ---- 分析複雜度 $($ 或讓電腦跑跑看 $)$ - 奇怪，怎麼還是一樣慢 ```cpp= 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 ```cpp= 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$ 簡化版 ```cpp= 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 迴圈實作 ```cpp= 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 迴圈進階用法 ---- ```cpp= vector<int> v(1000); // 這樣也可以用來輸入 for(int &i:v){ cin>>i; } for(int a:v){ cout<<a<<" "; } ``` --- ## Struct ---- 舉個有趣的例子(除了對...而言) ```cpp= 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(); } ``` --- ## 大家加油  ---- ## 大家加油