LFsWang's World

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

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

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

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

連結：https://tioj.ck.tp.edu.tw/problems/1214 題目大意 判斷兩棵樹是否同構 題解 如果兩棵樹是一樣的，那可以先將樹上唯二的重心、或直徑中點找出來，那就可以一個相同的點，然後再比對樹的最小括號表示法即可完成題目要求。 AC Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495#include<bits/stdc++.h>using namespace std;vector<int> V[100];int far,far2;int dist=0;void dfs(int v, int fa, int d){ if( d > dist ){ far=v; ...

連結：https://tioj.ck.tp.edu.tw/problems/1210 題目大意 給定一個度序列，問這個度序列是否能構成一張簡單圖？ 題解 最近恰好讀了圖論的書，若一個度序列可以構造出一個簡單圖，該序列又可稱為圖序列，利用度序列判定是否為簡單圖(無自環、重邊)在這本書【演算法觀點的圖論】第一章就有提到了，有兩個定理可以使用： Erdős–Gallai theorem 若度序列 d:d1≥d2≥…dn 是圖序列 ⟺ ∑d 是偶數，且對於 1≤k≤n 都有 ∑i=1kdi≤k(k−1)+∑j=k+1nmin{k,dj} Havel–Hakimi algorithm 對於 n≥2，若度序列 d:d1≥d2≥…dn 是圖序列 ⟺ d′:d2−1,d3−1,…,d1+d1−1,d2+d1,d2+d1,…,dn也是圖序列 可以發現第二個方法比較好實作，就是把度數最大的點，都接一條邊到度數較多的邊上。由於數字都是整數，可以利用 Counting Sort 或是一些技巧，就能在 O(V) 的時間判定是否為簡單圖了。 AC...

連結：https://tioj.ck.tp.edu.tw/problems/1201 題目大意 直線上有 K 個房間，每個房間要不就是社團的人，要不就是怪人(沒社團的人)，任兩怪人之間要相隔 $M個房間，已知有 N 種不同的社團，總共有幾種，問有幾種合法的人員放置方法，取除以 P 的餘數。 題解 一開始想到數學解，由枚舉怪人的數量，再把方法數加起來，如果現在有 S 位怪人，顯然要滿足： K≥(S+(S−1)×M) K≥S+N 可以先讓所有人以最緊密的方法排列進去，第一個是怪人，再下 M 個空房間，然後再一個怪人，以此類推。最後會剩下 K−(S+(S−1)×M) 間自由擺放的房間，數量用 L 表示。根據排列組合，L 個相同物有 S+1 個相異位置可放入，共有 (L+SL) 種方法，故總方法數是 ∑(L+SL)×NK−S，因為不能保證 P 是質數，硬幹 Cmn 複雜度過高，化簡 C 找通項DP化很麻煩，因此該方法不太合適。 如果是排組問題，可以考慮回到DP的基本想法，因為怪人的數量是任意多的，前面的怪人數量不影響答案，因此狀態可以如無限背包問題一樣，設 dp[i]= 有 i...

心得 平日練習隨意寫的 A 水題，略 B 水題，略 C. Covered Points Count AC code 利用掃描線的概念，按照 x 軸順序排序，將事件排好記數即可。 D. Yet Another Problem On a Subsequence AC code 可以利用動態規劃(DP)來計算答案，若子序列 p 是合法的，則將 p 的第一個 good array 去掉後剩餘的部分也是合法的，假定 dp[i] 表示子序列開頭在第 i 項時，有多少數列滿足題目的條件，若 ai≤0，則答案為 0，否則，可以在第 i 項後的 j 個數字任意挑 ai 個數字，挑完後在乘上 d[j+1]，為剩下的部分有多少合法序列。最後的答案即為 dp 陣列的總和。 dp[i]={1i=N+1∑j=i+ain(ji)dp[j+1]otherwiseE. We Need More Bosses F G