LFsWang's World

題目大意 計算 3xmod10007 題解 使用歐拉降冪公式 ak≡{akk<φ(n)ak%φ(n)+φ(n)k≥φ(n)對 x 取 φ(10007)=10006 的餘數即可。 AC Code 12345678910111213141516171819202122#include <bits/stdc++.h>using namespace std;using ll = long long;int main() { ios::sync_with_stdio(false); cin.tie(0); const ll mod = 10007; const ll phi = mod - 1; // 10007 is prime ll pw[2 * phi] = {1, 0}; for (int i = 1; i < 2 * phi; ++i) pw[i] = 3 * pw[i - 1] % mod; int x; while (cin >> x)...

題目大意 實作 heap，並輸出 level order 題解 能懶就懶。 C++ 有 heap 實作的函數可以用，可以不用自己寫。 push_heap 的用法是，先把元素放到陣列的最後面，再呼叫此函數即可。 由於 heap 是一個完全二元樹 (Complete Binary Tree)，因此該資料結構的 level order 就是由陣列順序直接輸出即可。 AC Code 123456789101112131415161718192021222324252627#include <bits/stdc++.h>using namespace std;using ll = long long;int main(){ ios::sync_with_stdio(false); cin.tie(0); int N, x; vector<int> v; while (cin >> N) { vector<int> mhp, Mhp; while (N--)...

在實作一些演算法，如 Miller-Rabin 時，會出現 long long 整數相乘再取餘數的步驟。 12long long a, b, c;auto res = a * b % c; 然而若 a*b 的結果大於 long long 的表達範圍的話會溢位，便無法取得正確的結果。因此會需要自行實做乘法來避免溢位。具體方法可以參考維基百科，簡單來說就是模擬直式乘法：如果每次最多乘以 2，那麼一個 63 bit 的整數可以在 64 bit 的空間內計算出來不會發生溢位。因此實作上用 uint64_t 來儲存即可。 不過絕大多數的 OJ 與競賽編譯器都使用 GCC，而 GCC 帶有非標準的 128 bit 整數 __int128 :link:，如果環境允許使用的話，那麼就只需要把 long long轉型到__int128運算即可。 很久以前有人說__int128運算上很慢，因此似乎讓後者的實做不是特別的流行。既然最近剛好寫到了一題，就來做個實驗。 就直白說結論了：__int128 比自行用迴圈實作乘法快了 30~50 倍 (O3 優化)。 因此如果環境許可的話，就用...

A. 威廉伯爵的農場 題目大意 給平面座標的三個點，問圍成的三角形面積乘以一個常數 c，所有數字都是 int 範圍的整數，c 是 2 的倍數，保證答案可以用 long long 表示 題解 Keys : 向量運算 數值處理 高中數學有提到，兩向量 a→、b→，圍成的平行四邊形面積是 |a→×b→|，所以這一題的答案就是 12×c×|a→×b→|，其中 |a→×b→|=|xayb−yaxb|，此外要注意除以 2 的次序避免溢位的問題。 B. ⼤樓彩繪 題目大意 有 m 角柱，角柱的側邊每個面都有 n×n 的網格，每個網格有 c 種顏色可以選擇，問有幾種著色方法 題解 Keys : 排列組合 Burnside’s lemma 快速冪 一個很顯然的事情是一個面有 cn2 種不同的塗法，這個數字姑且稱為 p ，那如何計算有多少的塗法呢？ 如果知道 Burnside’s lemma 的話就有 1m∑i=1mpgcd(m,i)C. 金坷垃運輸網 題目大意 給一張無向圖，問 a、b 兩點之間是否存在兩個獨立的路徑，即如果任意地把圖中的一條邊移除， a、b 依舊連通 題解 Keys...

連結：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...

題目 考慮一張無向的加權圖 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...

連結：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; ...

連結：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)))