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://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=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 ());     ...