做男人不容易系列 Solutions
Amber
2 years ago, I trained in Fudan University in Shanghai and attended this contest hold by Lou Tiancheng. The title of this contest is “hard to be a man”and the subtitle is “If you are a man, pass all 8 problems”. I got only 1 problem accepted at that time. Actually, no one can be “a man” except LTC himself at that time. Now there is still only 3 guys who finished all problems except the problemsetter LTC. They are timgreen, geworm, Savior. How I admire them!
Well, I decide to be a man before my 18th birthday. For my foreign friends, I decide to write the English version in the description and the solution with my poor English.
Problem A (POJ 1737): Connected Graph
[Description]
Find the number of connected labeled undirected graphs with n nodes.
出有标号的n个点的无向连通图的个数.
[Solution]
If we do not considered whether the graph is connected, there exists 2^C(n, 2) graphs in total. Let G(n) = 2^C(n, 2). If we know the number of unconnected ones, we will know the answer indirectly. Let F(n) is the answer. Consider the connected component C that contains node 1 and with the size k, namely |C| = k. Because C is unconnected, k < n. So there exists C(n – 1, k - 1) ways to choose another k - 1 nodes to make up connected component C. So there exists C(n – 1, k – 1) * F(k) different connected component C. Any graphs G(n-k) for remaining nodes are okay. So the answer is:
It takes O(n^2) to calculate this formula.
利用补集转化思想, 若不考虑连通性,则有n个点的任意图有G(n)=2^C(n, 2)个. 只要求出不连
通图的个数就知道答案F(n). 考虑含结点1的连通块C, |C| = k. 由于不连通,有k < n成立. 则有C(n - 1, k – 1)种方法选择另k-1个结点与结点1组成C. 所以有C(n - 1, k – 1) * F(k)种方法组成C. 剩下的结点组成一个任意图即可. 答案为:
复杂度为O(n^2).
[Reference]
[1]The information from the On-Line Encyclopedia of Integer Sequences: A001187 Number of connected labeled graphs with n nodes.
[2]杨俊, <<PKU 1737 解题报告>>, IOI2005国家集训队报告
Problem B (POJ 1738): An old Stone Game
[Description]
There are n(n<=50000) piles of stones in a line. Each time we can merge two adjoining piles to a new pile until there is only one pile. Minimize the summation of the number of stones in the new pile after merging.
在开始有n(n<=50000)堆的石头堆排成一行.每次可以合并相邻的两个石头堆成为一个新堆,可以得到这个新堆的石头数的分数.直到剩下一堆.出一种合并计划,使分数最小,求这个最小分数.leftist
[Solution]
This problem is equivalent to construct an Optimal Alphabetic Binary Search Tree (OABST).As the same As Huffman tree, minimize the summation of the weighted paths lengths of the external nodes(leaves). The difference is that the external nodes in OABST must be in order (alphabetic), namely merge the only adjoining piles each time. It can be solved in O(n^2) by dynamic programming after optimizing by the quadrilateral inequation. But it is not fast enough for this problem. The Hu-Tucker algorithm with the complexity O(nlogn) will be introduced in the following. This algorithm has 3 phases. Beca
use this problem does not need to output the merging method, just to implement the Phase 1 is okay.
Phase 1, Combination:
The goal of this phase is to build an optimal binary tree in which the depths of the external nodes are the same as the final OABST.
The work sequence is a sequence which consists of the internal or external nodes.
The initial work sequence of nodes consists of all the external nodes in order.
During each iteration of this phase a new working sequence is produced by combining two nodes wi and wj in the previous working sequence into one internal node wi+wj which replaces the leftmost node wi of the two and removing the rightmost one wj from the current sequence.
We call the pair of the nodes wi, wj which is combined in each iteration the Local Minimum Compatible Pairs (LMCP). In each iteration, LMCP is unique. It satisfies the following 4 rules:
Rule(1): In the current working sequence no external nodes occur between wi and wj.
Rule(2): The combined weight w = wi + wj is minimum.
Rule(3): If in case of tie, the subscript i of the leftmost nodes wi needs minimized.
Rule(4): If still in case of tie, the subscript j of the rightmost nodes wj needs minimized.
We use the rectangle to denote an external node and the circle to denote an internal node in the following.
For example, n = 5, w = (5, 2, 2, 3, 6). Notice that in Step (2), LMCP (5, 3) spans the internal node (2+2).
The implementing of this phase is the most complex and the most important also. We can find that the order of the continuous internal nodes does not matter. Namely the internal nodes between the two adjoining external nodes are similar to be executed the greedy algorithm of Huffman tree in part. In other words, external nodes divide the work sequence into some segments, the internal nodes between the two adjoining external nodes builds a set of the internal nodes (use the dashed circle to denote).

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。