Mirror的演算法筆記

題目鏈接: https://tioj.ck.tp.edu.tw/problems/2053 想學矩陣快速冪很久了 這次終於把他刷掉啦 其實矩陣快速冪就是矩陣乘法+快速冪而已 只要轉移式符合矩陣乘法的性質就可以使用 像費氏數列中的\(F_n=F_{n-1}+F_{n-2}\) 可以推導出如下矩陣 \(\left [\begin{array}{c}F_n\\F_{n-1}\end{array}\right ]=\left [\begin{array}{cc}1&1\\1&0\end{array}\right ] \times \left [\begin{array}{c}F_{n-1}\\F_{n-2}\end{array}\right ]\) 也就是說我們的每一項都能透過前兩項矩陣乘法後得來 這時候我們就可以使用快速冪的性質在\(O(logn)\)的時間複雜度下求得\(F_n\)的值了! 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using   namespace  std; using   namespace  __gnu_cxx; using   namespace  __gnu_pbds; using   ll   =   long   long ; #define   AC  ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); struct   martix {     ll m[ 2 ][ 2 ];      martix   operator *( martix   a )     {         martix r;          for ( int ...

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1879 裸橋連通分量 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using   namespace  std; using   namespace  __gnu_cxx; using   namespace  __gnu_pbds; using   ll   =   long   long ; #define   AC  ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); vector < vector <int>>  v,bcc; vector < pair <int , int>>  edge; vector <int>  low,tag; int  c = 1 ; stack <int>  s; void   dfs ( int   x , int   be ) {     low[x] = tag[x] = c ++ ,s. emplace (x);      for ( auto  e:v[x])     {          int  v = edge[e].second;          if ( ! tag[v])         {              dfs ...

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1137 同TIOJ 1256 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using   namespace  std; using   namespace  __gnu_cxx; using   namespace  __gnu_pbds; using   ll   =   long   long ; #define   AC  ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); vector < vector <int>>  v; vector <int>  tag,low; vector <bool>  vertex; int  c = 1 ,r = 0 ; void   dfs ( int   x , int   par ) {     tag[x] = low[x] = c ++ ;      int  child = 0 ;      for ( auto  e:v[x])     {          if ( ! tag[e])         {             child ++ ;              dfs ...

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1256 裸求割點 tarjan萬歲 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using   namespace  std; using   namespace  __gnu_cxx; using   namespace  __gnu_pbds; using   ll   =   long   long ; #define   AC  ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); vector < vector <int>>  v; vector <int>  tag,low; vector <bool>  ver; int  c = 1 ,r = 0 ; void   dfs ( int   x , int   par ) {      int  child = 0 ;     tag[x] = low[x] = c ++ ;      for ( auto  e:v[x])     {          if ( ! tag[e])         {             child ++ ;              dfs ...

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1161 這題要把所有的技能想象成一個坐標 放在\(xy\)軸上 然後枚舉所有x 每次多於k個點時就把最大的y拿掉 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std ; using namespace __gnu_cxx ; using namespace __gnu_pbds ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int t,n,k; cin >> t; while (t -- ) { cin >> n >> k; int r = 1 e 9 ; vector < pair <int , int>> v (n); std :: priority_queue <int> pq; for ( int i = 0 ;i < n;i ++ ) cin >> v[i].first >> v[i].second; sort (v. begin (),v. end ()); for ( int i = 0 ;i < n;i ++ ) { pq. emplace (v[i].second); if (pq. size () == k) r = min (r,v[i].first + pq. top ()),pq. pop (); } cout << r << ' \n ' ; } }

題目鏈接: https://tioj.ck.tp.edu.tw/problems/2026 動態中位數 維護一個大根堆和一個小根堆 大根堆存小於等於中位數的數 小根堆存大於中位數的數 插入的數如果小於等於中位數就丟進大根堆 比中位數大就丟進小根堆 奇數情況下 大根堆的數字比小根堆多1則大根堆的top為中位數 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std ; using namespace __gnu_cxx ; using namespace __gnu_pbds ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int q,n,x; cin >> q; std :: priority_queue <int> mx; std :: priority_queue <int ,vector <int> ,greater <int>> mn; cin >> n >> x; mx. emplace (x); while ( -- q) { cin >> n; if (n == 1 ) { cin >> x; if (x > mx. top ()) mn. emplace (x); else mx. emplace (x); if (mx. size () > mn. size () && mx. size () - mn. size () > 1 ) mn. emplace (mx. top ()),mx. pop (); if (mn. size () > mx. size ...

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1231 greedy一定要吃到大的 但由於過期的關係可能會少選 所以我們模擬過期的時間 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std ; using namespace __gnu_cxx ; using namespace __gnu_pbds ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int n,a,b,k,p = 0 ,r = 0 ; cin >> n; vector < pair <int , int>> v (n); for ( int i = 0 ;i < n;i ++ ) cin >> v[i].first >> v[i].second; cin >> k; sort (v. begin (),v. end (),[](pair <int , int> a ,pair <int , int> b ){ return a.second > b.second;}); std :: priority_queue <int> pq; for ( int i = k;i;i -- ) { while (p < v. size () && v[p].second >= i) pq. emplace (v[p ++ ].first); if (pq. empty ()) r -- ; else r += pq. top (),pq. pop (); } cout << r << ' \n ' ; }

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1566 維護兩個m大小的單調佇列 一個遞增一個遞減 分別代表區間最大值和區間最小值 遞增的單調佇列中 當\(v_j\ >\ v_i\)且\(i\ <\ j\)時 \(v_i\)會比\(v_j\)早被pop掉且\(v_j\)在時\(v_i\)沒有存在的意義 遞減的同理 再處理超出區間的值pop掉這個問題就解決啦 不過有個小細節我一直不知道 就是\(2^{31}\)是2147483648 超出int範圍的2147483647 所以要開long long 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std ; using namespace __gnu_cxx ; using namespace __gnu_pbds ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int n,m,l = 1 ; ll k,t; cin >> n >> m >> k; deque < pair < ll, int>> mx,mn; queue < pair < ll, int>> q; for ( int i = 1 ;i <= n;i ++ ) { cin >> t; if (i > m) l ++ ; while (mx. size () && i - mx. front ().second >= m) mx. pop_front (); while (mn. size () && i - mn. front ().second >= m) mn. pop_front (); while ...

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1618 Monotone queue again 維護一個遞減的deque 還有那個視野的條件 在deque裡面存index 就能O(1)取得current pos和deque.front()的距離 超過視野範圍就pop_front() 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std ; using namespace __gnu_cxx ; using namespace __gnu_pbds ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int n,k,p; ll r = 0 ,t = 0 ;; cin >> n >> k; vector < pair <int , int>> v (n + 1 ); deque <int> dq; for ( int i = 1 ;i <= n;i ++ ) cin >> v[i].first; for ( int i = 1 ;i <= n;i ++ ) cin >> v[i].second; for ( int i = 1 ;i <= n;i ++ ) { t += v[i].second; while (dq. size () && v[dq. back ()].first <= v[i].first) t -= v[dq. back ()].second,dq. pop_back (); dq. emplace_back (i); while (dq. front () < i - k + 1 ) t -= v[d...

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1930 這題就是用linked list模擬插隊 單人插隊的部分可以參考 https://mirrorshih.blogspot.com/2019/08/zj-d718-waiting-in-line_23.html 而重組的部分我本來用erase和insert寫會TLE 被大佬波路特石指點之後知道可以用splice在常數時間內移動一個區間 發放商品的部分我只能想到線性掃過商品的數量 不確定是不是因為這個原因TLE 最後我是加輸入優化過的 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std ; using namespace __gnu_cxx ; using namespace __gnu_pbds ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); inline char readchar () { static const size_t bufsize = 65536 ; static char buf[bufsize]; static char * p = buf, * end = buf; if (p == end) end = buf + fread_unlocked (buf, 1 , bufsize, stdin), p = buf; return * p ++ ; } template < class T > void input (T & a ) { static char p; while ((p = readchar ()) < ' 0 ' ) ; a = p ^ ' 0 ' ; while ((p = readchar ()) >= ' 0 ' ) a *= 10 , a += ...

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1225 又是一個Monotone queue的題目 維護一個單調遞減的stack 當有一個比top大的數字出現時 top必須被抹除才符合單調性 比較top左邊的數字和新加入的數字 選擇比較小的加入答案 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std ; using namespace __gnu_cxx ; using namespace __gnu_pbds ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int n,t; ll r = 0 ; cin >> n; stack <int> s; while (n -- ) { cin >> t; while (s. size () && t >= s. top ()) { s. pop (); if (s. size ()) r += min (t,s. top ()); else r += t; } s. emplace (t); } while (s. size () > 1 ) { s. pop (); r += s. top (); } cout << r << ' \n ' ; }

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1176 寫到快瘋掉了......... 由於這題要記錄每一個牛能看到幾個 所以一定要開一個vector去存能看到幾個 於是我一開始寫了這份\(O(n^2)\)的code #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std ; using namespace __gnu_cxx ; using namespace __gnu_pbds ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int n,t; cin >> n; vector <int> M (n), r (n, 0 ); vector <bool> stop (n, 0 ); for ( int i = 0 ;i < n;i ++ ) { cin >> M[i]; for ( int j = 0 ;j < i;j ++ ) { if ( ! stop[j] && M[i] >= M[j]) r[j] ++ ,stop[j] = 1 ; else if ( ! stop[j]) r[j] ++ ; } } for ( int i = 0 ;i < n;i ++ ) cout << r[i] << ' \n ' ; } 拿了個82分 看起來還可以 然後仔細想了想該怎麼優化 想到了一個unordered_set+queue的優化 #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std ; u...

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1911 這題就維護一個最大堆一個最小堆 pop的時候就把instack設為0 另一個堆就可以知道當前的top是否存在 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std ; using namespace __gnu_cxx ; using namespace __gnu_pbds ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int n; std :: priority_queue <int> max_heap; std :: priority_queue <int ,vector <int> ,greater <int>> min_heap; unordered_map <int , int> m; while (cin >> n && n) { if (n ==- 1 ) { while (min_heap. size () &&! m[min_heap. top ()]) min_heap. pop (); if (min_heap. size ()) cout << min_heap. top () << ' ' ,m[min_heap. top ()] -- ,min_heap. pop (); } else if (n ==- 2 ) { while (max_heap. size () &&! m[max_heap. top ()]) max_heap. pop (); ...