天天看點

2017年中國大學生程式設計競賽-中南地區賽暨第八屆湘潭市大學生計算機程式設計大賽題解&源碼(A.高斯消元,D,模拟,E,字首和,F,LCS,H,Prim算法,I,胡搞,J,樹狀數組)

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

題解:

2017年中國大學生程式設計競賽-中南地區賽暨第八屆湘潭市大學生計算機程式設計大賽題解&源碼(A.高斯消元,D,模拟,E,字首和,F,LCS,H,Prim算法,I,胡搞,J,樹狀數組)

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

2017年中國大學生程式設計競賽-中南地區賽暨第八屆湘潭市大學生計算機程式設計大賽題解&源碼(A.高斯消元,D,模拟,E,字首和,F,LCS,H,Prim算法,I,胡搞,J,樹狀數組)

我的了解是:

題意:選取一段區間求和取絕對值,加在初始化為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

2017年中國大學生程式設計競賽-中南地區賽暨第八屆湘潭市大學生計算機程式設計大賽題解&源碼(A.高斯消元,D,模拟,E,字首和,F,LCS,H,Prim算法,I,胡搞,J,樹狀數組)

陷阱:此題好像用lld不會過,要用int64,我也不知道啥情況QAQ

J-----------------------------------------------------------------------------------

題目連結:http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1269

2017年中國大學生程式設計競賽-中南地區賽暨第八屆湘潭市大學生計算機程式設計大賽題解&源碼(A.高斯消元,D,模拟,E,字首和,F,LCS,H,Prim算法,I,胡搞,J,樹狀數組)

源碼:(來自某位學長)