某島

… : "…アッカリ~ン . .. . " .. .
August 18, 2012

Andrew Stankevich’s Contest #1

Overview:

。。。大媽題第一套。。。大部分都是以前做過的題目。。所以感到難度不是很大?。
。。用來複習的話倒是不錯。。推薦 D 和 F。。。

http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=4512#overview

Problem A. Chinese Girls’ Amusement
數論 + 大數..

Problem B. Reactor Cooling
上下界網路流..

Problem C. New Year Bonus Grant
樹的最大邊覆蓋集。。
樹形 DP。。(F[u] 被覆蓋,G[u] 覆蓋別人。

Problem D. Matrix Multiplication
。。。演算法導論上的一個習題 。。(參見 習題 22.1-7 。。pg 324

$latex \sum{A}=B^TB=\sum_{i,j}\sum_k{B_{ki}B_{kj}}=\sum_k\sum_{i,j}{{B_{ki}B_{kj}}}&s=4$

(上式以 wiki 頁的習慣用法為準。A 矩陣代表鄰接矩陣, B 矩陣代表關聯矩陣。。。。
。。實際上上面的公式的意思就是 A 是原圖的所對應的線圖的鄰接矩陣。(所謂線圖大概就是點線互換的意思。。。。
於是 Aij 就表示邊 i 和邊 j 之間通過多少個定點相互關聯。。(。。在一般圖中。。 這個值只會取 0, 1, 2 。。。
於是從度數的角度來考慮。。一個度數為 k 的頂點會給整個矩陣帶來 k^2 個收益。。。
所以上面的值也等於所有頂點度數平方的總和。

。。O(n + m)。)。

(反過來乘的話會得到原本的鄰接矩陣。。。。累和的話會得到對應線圖的度數平方和。
。由於每條邊固定和兩個頂點關聯。。(因為在一般圖中這個值實際是個定值。。(m * 2^2 。。所有出起題目來沒什麼意思。。
http://en.wikipedia.org/wiki/Incidence_matrix

Problem E. Nice Patterns Strike Back
SCDP + 矩陣乘法

Problem F. Get Out!
計算幾何

Problem G. Beautiful People
LIS。。

Problem H. Cracking RSA
亦或方程 + 大數