A------------------------------------------------------------------------------------
題目連結:http://202.197.224.59/OnlineJudge2/index.php/problem/read/id/1260
題解:随機 n 個數把矩陣補全成 n × n 的。那麼就是要算伴随矩陣的第一行,也就是逆矩陣的第一列,高斯消元即可。
源碼:(Q神寫的高斯消元,先貼一下诶,待補)
B------------------------------------------------------------------------------------------
題目連結:http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1261
題解:考慮 Kruskal 的過程,肯定是同樣權值的邊連通了一個點集。如果要讓 MST 變大,就是要讓某個權值的邊不再連通。這是全局最小割問題,可以網絡流也可以用 Stoer–Wagner 算法。
C------------------------------------------------------------------------------------------
題目連結:http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1262
題解:
D------------------------------------------------------------------------------------------
題目連結:http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1263
題解:将n*m的照片放大a*b倍,然後直接輸出,此題隻要模拟即可
源碼:
E-------------------------------------------------------------------------------
題目連結:http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1264
我的了解是:
題意:選取一段區間求和取絕對值,加在初始化為0的數值上,選了的區間不能再選,問最大的和是多少
解法:字首和排序,最大和最小相減加起來就好了
F-------------------------------------------------------------------------------
題目連結:http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1265
題解:首先對 a 離散化,之後可以 O(n^3 ) 枚舉序列 X.如果之後用 O(n) 的 LCS dp 會使複雜度變成 O(n^4 ).
std 用的方法是 2^3 枚舉 X 的一個子序列,通過預處理一個next(i,c) 表示 i 位置後 c 字元第一次出現的位置,來 O(1) 判斷是否是 A 的子序列。
某位學長的了解:
将a數組離散化,枚舉三元素,n^3
求LCS,花費n*3,現在總體複雜度是n^4的
求LCS這步可以 優化,我們預處理吃nex[i][c],目前i位置後面第一個c在哪裡
就可以在2^3下O(1)求出LCS了
有個坑的地方就是 a[i]可能會大于m,wa了很久
源碼:(來自某位學長)
G-------------------------------------------------------------------------------
題目連結:http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1266
題解:括号序列就是要求前 (2k + 1) 個裡面至少要有 k 個左括号。那麼先把所有括号翻成右括号,之後重新翻回左括号。
那麼從左到右貪心,用一個堆維護現在可以翻回左括号的位置。每次相當于加兩個目前段的字元,取一個最小的。是以事件隻有最小的被拿完了,或者目前段拿完了。模拟即可。
H--------------------------------------------------------------------------------
題目連結:http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1267
題解:按照 Prim 算法計算生成樹。假設初始點 v 0 是某條直徑的端點。那麼距離 v 0 最遠的 v 1 必然是直徑的另一個端點。
又因為距離任意點最遠的要麼是 v 0 要麼是 v 1 ,是以剩下的點隻需要連往 v 0 和 v 1 中較遠的一個即可。
我的了解:
題意:要把所有的邊都聯通,并要求權值之和最大
解法:因為是顆樹,那就沒必要讨論兩點的最短路了(畢竟樹是沒有回路的),那麼重點是落在了如何找到權值之和最大的方法
我們找到這顆樹相距最遠的兩個點(樹的直徑)A,B 剩餘的點取距離A或者B最遠的那條,需要進行兩次dfs,距離儲存最大的
然後加起來就行,因為A到B我們多加了一次,再減去就是結果!
I----------------------------------------------------------------------------------
題目連結:http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1268
陷阱:此題好像用lld不會過,要用int64,我也不知道啥情況QAQ
J-----------------------------------------------------------------------------------
題目連結:http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1269
源碼:(來自某位學長)