Mirror的演算法筆記

好久沒寫題目了....... 題目鏈接： https://zerojudge.tw/ShowProblem?problemid=b570 看過題目之後其實不難發現他是並查集 因為他是炸掉邊而不是加入邊 我們用並查集會很難維護他 但如果我們倒著加入邊是不是能得到一樣的效果呢？ 所以實際的做法就是倒著加入邊，每次輸出的結果也是倒著的 將每次的結果加入一個stack中 最後輸出stack中全部的值 就是答案啦！ 以下為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   DSU {     vector <int>  v;      DSU ( int   x )     {         v. resize (x);          for ( int  i = 1 ;i < x;i ++ )             v[i] = i;     }      int   find ( int   x )     { ...

題目鏈接: 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://zerojudge.tw/ShowProblem?problemid=d767 LCA算法裸題 以下為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,dou; vector < pair <int ,  int>>  ti; vector <int>  dep; int  L,cou = 1 ; void   dfs ( int   x , int   par ) {     ti[x].first  =  cou ++ ;     dou[x][ 0 ] = par;      for ( int  i = 1 ;i <= L;i ++ ) dou[x][i] = dou[dou[x][i - 1 ]][i - 1 ];      for ( auto  e:v[x]) dep[e] = dep[x] + 1 , dfs (e,x);     ti[x].second  =  cou ++ ; } bool   anc ( int   x , int   y ) {  ...

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=d686 也是區間DP 正常跑過去就能解決了 不過有些細節要處理好 不然會卡很久 以下為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,l;      while (cin >> l && l)     {         cin >> n;         vector <int>   v (n + 1 );         vector < vector <int>>   dp (n + 2 , vector <int> (n + 2 ));          for ( int  i = 1 ;i <= n;i ++ ) cin >> v[i];     ...

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=d652 區間DP經典 最小矩陣鏈乘積 不會就去看板中講義吧 以下為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;     cin >> n;     vector <int>   v (n + 1 );     vector < vector <int>>   dp (n + 1 , vector <int> (n + 1 , 1 e 9 ));      for ( int  i = 1 ;i <= n;i ++ ) cin >> v[i];      for ( int  i = 1 ;i < n;i ++ )         dp[i][i] = dp[i][i + 1 ] = 0 ;      for ( int  i = 1 ;i < n;i ++ ) ...

題目鏈接: 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://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 ' ; }