LFsWang's World

連結：https://tioj.ck.tp.edu.tw/problems/1497 題目大意 給一個字串，求一個字串的Suffix Array。 題解 AC Code 使用 std::Sort 複雜度為 O(|S|log2⁡|S|) 123456789101112131415161718192021222324252627282930313233343536373839#include<bits/stdc++.h>using namespace std;vector<int> sa(string str){ int len = str.size(); vector<int> rank(len), sa(len), tmp(len); for(int i=0;i<len;++i) { rank[i] = str[i]; sa[i] = i; } sort(sa.begin(), sa.end(), [&](int s, int e){ ...

題目 考慮一張無向的加權圖 G=V,E,w(s,t)，求 G 的生成樹中，權重非嚴格第二大的生成樹。 演算法 先找出 G 的最小生成樹 GM=VM,EM,wM(s,t) 設 S=∅ 對於所有的邊 e=s,t∈E−EM 找到 GM 中，點 s 到點 t 的路徑上，邊長最長的邊 e′ 將 GM−e′+e 加入至集合 S 中 S 中權重和最小的樹即為所求 證明 先考慮一個樸素作法，因為次小生成樹與最小生成樹至少有一條邊不一樣，因此，可以枚舉最小生成樹的邊，將其刪除之後，再求最小生成樹，那次小生成樹必然會是這 V−1 顆樹中的其中一種。 接下來，可以證明刪掉一條邊的圖，存在一個最小生成樹，與原來的最小生成樹只有一條相異的邊。考慮 Kruskal 演算法，如果把第 i 個加入最小生成樹的邊 ei=(si,ti) 刪除的話，並不影響加入第 i 條邊之前的決策。接下來，將原來最小生成樹第 i+1 條邊到 V−1 條邊加入這一個新的樹中，那會得到兩個獨立的兩個連通塊 (原來MST砍掉 s 到 t 的邊 )，此時再找到一條最小的邊 e′ 將這兩個連通塊接在一起，就形成了一個最小生成樹，且這顆 ...

連結：https://tioj.ck.tp.edu.tw/problems/1445 題目大意 求連接所有元件的方法中，第一小與第二小的代價是多少，如果不存在輸出 −1。 題解 求最小生成樹與次小生成樹。最小生成樹很簡單，Kruskal 一下就好了，所以關鍵在如何求次小生成樹。 可以證明存在一個次小生成樹 T′ ，是最小生成樹 T 加上一條邊 e′ 之後，再將形成的環，刪除除了 e′ 之外的最長邊。 詳細演算法參考這邊：次小生成樹演算法與證明 要如何求一顆樹任兩點間的邊長的最大值呢？可以考慮 LCA的倍增法，在 dp 的同時，也記錄下目前區間的邊長最大值就好了。 該實作時間複雜度為 O(Elog⁡E+Elog⁡V) AC Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949 ...

連結：https://tioj.ck.tp.edu.tw/problems/1037 題目大意 再二維 N×M 的格子中，有一個起點與終點，今天要從起點走 K 步，每步的距離為 di，方向上下左右任選，如果走超出格子就循環的走，問是否存在一種方法可以走到終點。 題解 一個很暴力的 O(KNM) 動態規劃，因為複雜度看起來很危險，但時間挺寬鬆的，所以對細節做了一些優化，然後就過了，而且還頗快的 AC Code 12345678910111213141516171819202122232425262728293031323334#include<bits/stdc++.h>using namespace std;bool dp[2][100][100];int main(){ ios::sync_with_stdio(false); cin.tie(0); int N,M,T,d1,d2; int sx,sy,ex,ey; cin>>N>>M>>sx>>sy>>ex>> ...

連結：https://tioj.ck.tp.edu.tw/problems/1443 題目大意 題目寫得很亂，總結一下：給一張二分圖，問最小點覆蓋是多少，即要最少要選幾個點，才能使每一條邊至少有一端點被選中。 題解 二分圖上有 最大匹配最小點覆蓋最大匹配=最小點覆蓋證明待補，完整的證明我有用到cut。可以直接用匈牙利演算法 (Kőnig’s theorem) 簡單的求出最大匹配。 AC Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include<bits/stdc++.h>using namespace std;vector<int> V[100001];int m[100001];int P,Q,K,T,s,t;bool used[100001];bool dfs(int v){ for(int e:V[v]) { if(used[e])continue; ...

連結：https://tioj.ck.tp.edu.tw/problems/1443 題目大意 F(n)={0if n=0F([n2])+n−2[n2]otherwise給定 n，問 F(0),F(1)…,F(n) 中的最大值為何。 題解 如果仔細觀察一下，F(n) 的結果是 n 寫成二進位時有多少 1，因此這題要問的答案就很明顯了，就是到數字 n 進位最多有幾個 1。答案等於 ⌊log2⁡(N+1)⌋ 這裡做法有點懶惰，直接用 python 大數算，速度跟自己開大數模板差不多。 AC Code 12import mathprint(math.floor(math.log(int(input())+1,2)))

連結：https://tioj.ck.tp.edu.tw/problems/1704 題目大意 今天有 N 個橘子，每個橘子都有相異的重量。今天要挑出一些橘子，由重量小到大吃掉這些橘子。已知第 i 在第 j 順位吃掉的話，那就有 Ai,j 的飽足感。問至少要吃幾顆橘子才能有至少 k 的飽足感 題解 可以考慮動態規劃。先將橘子由小到大排序，用 pi 表示排完序後的橘子，原來的編號是什麼，設 dp[i][j] 表示全部吃了 j 個橘子，且最後一顆是 pi 的最大飽足度，那可以很輕鬆地發現 dp[i][j]=Api,j+maxj=1,2,…i−1dp[i−1][j]因為max的部分可以在 O(1) 時間解決掉，故該方法可以在 $O(n^2) 的時間找出滿足條件答案。 AC Code 123456789101112131415161718192021222324252627282930313233343536373839404142#include<bits/stdc++.h>using namespace std;vector<pair<int,int>> ...

連結：https://tioj.ck.tp.edu.tw/problems/1418 題目大意 有 N 位同學要每三個人湊成一組，每湊成一組可以計算出一個雷度，問要怎麼湊才能使整體雷度最低。 題解 這題目名稱感覺挺容易起爭議的，而且這題時限我覺得設計的很差，只有特定的實作才能過最後一筆。 如果不記最後一筆，可以很簡單的用位元DP處裡掉，因為可以任選三人，DP時因此可以固定先選一人，再任選兩人，讓枚舉的複雜度變低，可以再 O(n22n) 的時間完成。 dp[S]={0if S=∅min{dp[S−{i,j,k}]+v[i][j]+v[j][k]+v[k][i]}otherwise其中 i,j,k∈S 要過最後一筆，我試過先提出可以用行的數字放在新的陣列中處裡，不過這樣反而讓其他的優化處理變差。然後參考網路上有的實作，DP變成向後更新數字，然後就過了，我覺得很莫名。約有4倍的速度差，我個人認為是這樣處裡能留下的快取比向前的還要來的多，不過一般出題卡這種細節我覺得不太行。 AC Code 1234567891011121314151617181920212223242526272829303 ...

連結：https://tioj.ck.tp.edu.tw/problems/1331 題目大意 給定 a,b,x,y 問下遞迴數列第 n 項的數值是多少，取其除以 232 的餘數： {S0=aS1=bSn=xSn−2+ySn−1題解 因為 n 的範圍是 109，很顯然的要用矩陣快速冪來計算。矩陣的構造方法就如同費式數列 [01xy]n[S0S1]=[SnSn+1]利運快速冪來計算可以在 O(23log⁡n) 計算出答案。 AC Code 1234567891011121314151617181920212223242526272829303132333435363738394041#include<bits/stdc++.h>using namespace std;using u32 = uint32_t;using matrix = vector<vector<u32>>;matrix A,T;//a*=b;inline void mul(matrix &a, const matrix &b){ //static m ...

連結：https://tioj.ck.tp.edu.tw/problems/1306 題目大意 有一個字串 T，詢問多個字串 Pi 分別在 T 中出現幾次。 題解 很久以前寫過這題，用的是雜湊，不過看起來WA了之後這題就被擱置了，無聊又點開這題，意外地找到當初WA的BUG… 給大家猜猜看： 1234567ll pw(ll a,ll e){ if(e==0)return 1; ll t = pow( a*a%MOD , e/2); if( e&1 )return a*t%MOD; return t;} 字串的題目可以考慮使用雜湊的技巧來把題目水過，以這題來說，就可以用Rolling hash直接比對，不過實作上時限稍緊，要把細節處理好才能AC，比較要注意的重點是處理相減的取模時，用 (A-B+M)%M 比 C=A-B; if(C<0)C+=M 慢上至少兩倍，再雜湊中，這常用的細節會大幅度的影響執行時間，要十分注意。 除了雜湊之外，這也是經典的AC自動機要解決的問題，AC自動機可以在 O(T+∑Pi) 找出每個 P 在 T 中出現幾 ...