Mirror的演算法筆記

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=d555 就先找相同x時最大的y 如果更大的x時y也更大就pop掉 單調佇列 以下為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,c = 1 ;      while (cin >> n)     {         deque < pair <int ,  int>>  dq;         vector < pair <int , int>>   v (n);          for ( auto   & e:v) cin >> e.first,cin >> e.second;          sort (v. begin (),v. end ());     ...

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

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

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

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=a813 連續寫了兩題有關單調性的題目,真的是有夠難寫的 這題其實是麻煩在有同樣高度的樓 我一直沒想到每新增一個等高樓就要再把答案加一次等高樓的數量 真的是白癡= = 這題的單調性就是如果有一個更高的樓出現 之前比他小的樓都不可能被看到 而如果是一個更矮的樓出現,則之前那些更高的樓會看不到他 再處理等高樓之後問題就解決了 以下為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 >> t; deque <int> dq; unordered_map <int , int> m; dq. emplace_back (t); m[t] ++ ; for ( int i = 1 ;i < n;i ++ ) { cin >> t; while (dq. size () && t > dq. back ()) { r += m[dq. back ()]; m[dq. back ()] = 0 ; dq. pop_back (); } if (dq. size () && t == dq. back ()) r += m[t]; else dq. emplace_back (t); m[t] ++...

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

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=a457 https://tioj.ck.tp.edu.tw/problems/1720 由題述可知 答案的數量為 特派員分數與民眾分數相對的數量 按照特派員分數排序 求民眾分數的逆序數對則可得答案 以下為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 ); #define lowbit ( x ) x &- x struct BIT { vector <int> v; void modify ( int x , int val ) { for (;x < v. size ();x += lowbit (x)) v[x] += val; } ll query ( int x ) { ll r = 0 ; for (;x;x -= lowbit (x)) r += v[x]; return r; } }; int main () { AC int k,m; ll r = 0 ; cin >> k >> m; BIT sum; vector < pair <int , int>> v (k); vector <int> tmp (k); for ( int i = 0 ;i < k;i ++ ) cin >> v[i].first; for ( int i =...