常用問題解決方法


目錄

  • 前綴和
  • 差分
  • 快速冪
  • 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