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

第一次參加codewars，今年入場是送耳機電腦包和Tshirt，本來學弟也會來的，結果他們說不知道怎麼去就不來了。開賽前吃點心根本搶不到，覺得動線配置蠻差的。賽前登入系統的時候不知道為什麼我們這台一直連不上，請工作人員來幫忙換了三四個人才成功。 開始比賽之後我們先刷掉了送分那題，然後讓陳彥宇跟我講「森林村莊分類」的題述，他講的大意是判斷圖中點跟點有沒有連在一起，輸出沒有直接聯通的點對，做完之後提交竟然WA了，那時候覺得這題卡住了就先放在旁邊。那時候我們先嘗試做了「搭建圍欄」，不過在嘗試了兩三次之後我發現那題是凸包+旋轉卡尺，可是我完全不會寫計算幾何QQ。之後陳彥宇和孫文浩就說「刀疤的陰謀」那題是找質因數，於是我們覺得這題比較好解。然後我又跟孫文浩討論了一下「森林村莊分類」那題，結果一聽他的描述我就發現那題根本是判二分圖，然後就AC掉了。再來也順利的AC掉「刀疤的陰謀」。刷掉這兩題後我們決定一次看完全部的題目再決定要做哪題，可能因為太急沒有很認真聽題目導致我們漏掉了一個20分但不難的「刀疤的獎勵」。最後我們是決定開「搶得先機II」，做完多餘的時間再做「星空下的塵砂」，「搶得先機II」那題就bfs走迷宮，不過實做稍微麻煩了一點，但還是確實地拿了下來，這時候因為已經沒多少時間我們就沒有繼續做了。 雖然這場比賽有很多時間感覺都被浪費掉了，也有幾題其實不難的題目我們可能沒有注意或剛好不會寫相關的算法就不得不放棄，有點可惜。但整體來講感覺還是打得不錯啦，以我們高職菜雞而且學演算法沒多久來看我個人認為還算滿意。