某岛

… : "…アッカリ~ン . .. . " .. .
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
亦或方程 + 大数