Mirror的演算法筆記

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=a674 Floyd把DP式改成\(dp_{ij}=min(dp_{ij},max(dp_{ik},dp_{kj}))\)就行了 至於原因就請自己思考看看啦 以下為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  c,s,q,cnt = 1 ;      while (cin >> c >> s >> q && c && s && q)     {         cout << " Case # " << cnt ++<< ' \n ' ;         vector < vector < ll >>   v (c + 1 , vector < ll >(c + 1 , 1 e 9 ));          for ( int  i = 0 ;i < ...

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=b058 回溯求DAG上的最長路 先拓撲排序並記錄現在這個點的值是從哪個幾個點轉移過來的 最後dfs回去求點數 以下為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 node { int val,deg = 0 ,mx = 0 ; bool tag = 0 ; vector <int> child; vector <int> par; }; vector < node > v; int dfs ( int x ) { int r = 0 ; if (v[x].tag) return 0 ; v[x].tag = 1 ; for ( auto e:v[x].par) r += dfs (e); r ++ ; return r; } int main () { AC int n,m; while (cin >> n >> m) { int r = 0 ,ans = 0 ; v. clear (); v. resize (n + 1 ); vector <int> back; for ( int i = 1 ;i <= n;i ++ ) cin >> v[i].val; for ( int i = 0 ;i < m;i ++ ) { int f,...

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=c435 一個很漂亮又不難的題目 看答案之前建議自己思考一下 由於\(n\leq10^5\) 所以不能\(O(n^2)\)枚舉 然後很顯然最大的\(a_i-a_j\ |\ i<j\)就是最大的\(a_x\ |\ x\leq i\)減去\(a_j\) 以下為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,tmp = 0 ,r = 0 ; cin >> n; for ( int i = 0 ;i < n;i ++ ) { cin >> t; r = max (tmp - t,r); tmp = max (tmp,t); } cout << r << ' \n ' ; }

題目鏈接: 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://zerojudge.tw/ShowProblem?problemid=d713 動態中位數 可參考 https://mirrorshih.blogspot.com/2019/08/tioj-2026_25.html 唯一的區別是這題偶數情況要輸出兩個堆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 ll n; std :: priority_queue < ll > mx; std :: priority_queue < ll,vector < ll > ,greater < ll >> mn; cin >> n; cout << n << ' \n ' ; mx. emplace (n); while (cin >> n) { if (n > mx. top ()) mn. emplace (n); else mx. emplace (n); if (mx. size () > mn. size () && mx. size () - mn. size () > 1 ) mn. emplace (mx. top ()),mx. pop (); if (mn. size () > mx. size ()) mx. emplace (mn. top ()),mn. pop (); if ((mx. size () + mn. size ()) & ...

題目鏈接: 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...

丟一個模板在這裡以免忘記 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 += p ^ ' 0 ' ; } 可能會用到的題目:TIOJ 1930 , ZJ c223 , TIOJ 2026

題目鏈接: 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://zerojudge.tw/ShowProblem?problemid=d718 這題是模擬排隊 不過有一個插隊的情況 於是我們用list取代queue 我們用一個unordered_map去存這些人分別屬於哪些團體 方便之後查詢 再來我們用一個vector去存這些團體是否在list中 在的話就進行插隊 而插隊我們用一個vector去存現在這個隊伍中每個團體的最後一個人所在的iterator 就解決啦 以下為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,t,cnt = 1 ; while (cin >> n) { cout << " Line # " << cnt ++<< ' \n ' ; unordered_map <int , int> um; for ( int i = 0 ;i < n;i ++ ) { cin >> m; for ( int j = 0 ;j < m;j ++ ) { cin >> t; um[t] = i; } } string s; list <int> l; vector <int> v (n + 1 , 0 ); vector ...

I/O優化 https://horikitacoding.blogspot.com/2019/07/how-to-optimize-your-code-in-c.html 離散數學-同餘 https://ithelp.ithome.com.tw/articles/10205727

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=c223 這題原意是要觀察出合併後數字會遞增 可以用一個queue去存 合併時可以\(O(1)\)取得最小值 全部合併時間複雜度為\(O(n)\) 但這題根本不是考你上面說的那些= = 他需要加一大堆輸入輸出優化 還有RadixSort才能過(據說) 因為我沒刻RadixSort所以只拿到99% 以下為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 ); long long readint (){ long long a = 0 ; char c = ' 0 ' ; while (c >= ' 0 ' && c <= ' 9 ' ){ a = (a << 3 ) + (a << 1 ) + c - ' 0 ' ; c = getchar (); } return a; } void writeint ( long long d ){ if (d == 0 ){ putchar ( 48 ); return ; } int len = 0 ; char n[ 20 ]; while (d > 0 ){ n[len] = d % 10 + 48 ; len ++ ; d /= 10 ; } for ( int i = len - 1 ;i >= 0 ;i -- ) putchar (n[i]); } int main () { //AC ll n,t,sum; while ( 1 ) { n = readint (); if ( ! n) ...