首页 > 搜索 > DFS搜索 > hdu 2705 Serial Numbers-状态压缩-[解题报告]C++
2014
02-14

hdu 2705 Serial Numbers-状态压缩-[解题报告]C++

Serial Numbers

问题描述 :

A manufacturer keeps an ordered table of serial numbers by listing in each row of the table a range of serial numbers along with two corresponding pieces of information called the status code and the transfer code. A four-column table stores information about ranges of serial numbers in this order: starting serial number, ending serial number, status code, transfer code. Serial numbers as well as transfer codes are integers from 1 to 2147483647, and status codes are a single upper-case letter. The table is maintained in
increasing order of serial numbers, serial number ranges are never allowed to overlap, and for any given serial number, the table must always accurately represent the most recent data (status code and transfer code) for
that serial number.
Let’s say that 100,000 serial numbers are created with a status of "A" and a transfer code of "1". An entry for those serial numbers might look like this:
1 100000 A 1
This is obviously far more efficient than storing 100,000 individual rows all with the same status and transfer codes. The challenge arises when serial numbers within already defined ranges need to be given different
status or transfer codes. For example, if serial number 12345 needs to change to status B, the above table would need to become three separate entries:
1 12344 A 1
12345 12345 B 1
12346 100000 A 1
Now let’s change the transfer code of all serial numbers in the range 12000 to 12999 to 2. This gets us:
1 11999 A 1
12000 12344 A 2
12345 12345 B 2
12346 12999 A 2
13000 100000 A 1
Now change all existing serial numbers from 10000 to 100000 to status C and transfer code 2:
1 9999 A 1
10000 100000 C 2
Once created a serial number will never be deleted, but it is possible to have ranges of undefined serial
numbers between ranges of defined ones. To demonstrate, let’s now set all serial numbers from 1000000 to
1999999 to status Z and transfer code 99:
1 9999 A 1
10000 100000 C 2
1000000 1999999 Z 99
Finally, the table is always maintained with a minimal number of rows, meaning specifically that there will
never be two adjacent rows in the table where one would suffice. For example, consider the following serial
number table:
1 10 A 1
11 20 A 1
21 30 B 1
The first two rows could actually be represented by a single row, meaning that the table above does not have
a minimal number of rows. The same data represented by a minimal number of rows would look like this:
1 20 A 1
21 30 B 1
The following table, however, because the first two rows have non-matching transfer codes, already contains
the minimal number of rows:
1 10 A 1
11 20 A 2
21 30 B 1
Similarly, the following table cannot be reduced further because the first two rows do not represent a
continuous series of serial numbers:
1 10 A 1
12 20 A 1
21 30 B 1

输入:

Each input case begins with a single line that is a character string naming the test case. This string
contains at most 80 characters. The name "END" marks the end of the input. Following this will be 1 to 100
lines of the form "A B S T", where A, B, and T are integers in the range 1 to 231-1, S is an uppercase letter,
and A<=B. These lines are, in the order they are to be applied, the serial number transactions to be recorded,
where A is the start of the serial number range, B is the end of the serial number range, S is the status code,
and T is the transfer code. The list of serial number transactions is terminated by a line containing only a 0
(zero) character.

输出:

Each input case begins with a single line that is a character string naming the test case. This string
contains at most 80 characters. The name "END" marks the end of the input. Following this will be 1 to 100
lines of the form "A B S T", where A, B, and T are integers in the range 1 to 231-1, S is an uppercase letter,
and A<=B. These lines are, in the order they are to be applied, the serial number transactions to be recorded,
where A is the start of the serial number range, B is the end of the serial number range, S is the status code,
and T is the transfer code. The list of serial number transactions is terminated by a line containing only a 0
(zero) character.

样例输入:

First Example
1 100000 A 1
12345 12345 B 1
0
And Another
1 100000 A 1
12345 12345 B 1
12000 12999 A 2
12345 12345 B 2
0
Test Case Three
1 100000 A 1
12345 12345 B 1
12000 12999 A 2
12345 12345 B 2
10000 100000 C 2
0
Example Four
1 100000 A 1
12345 12345 B 1
12000 12999 A 2
12345 12345 B 2
10000 100000 C 2
1000000 1999999 Z 99
0
Example 5
1 10 A 1
21 30 B 1
11 20 A 1
0
Example 6
21 30 B 1
1 10 A 1
11 20 A 2
0
Example 7
12 20 A 1
21 30 B 1
1 10 A 1
0
END

样例输出:

First Example
1 12344 A 1
12345 12345 B 1
12346 100000 A 1
And Another
1 11999 A 1
12000 12344 A 2
12345 12345 B 2
12346 12999 A 2
13000 100000 A 1
Test Case Three
1 9999 A 1
10000 100000 C 2
Example Four
1 9999 A 1
10000 100000 C 2
1000000 1999999 Z 99
Example 5
1 20 A 1
21 30 B 1
Example 6
1 10 A 1
11 20 A 2
21 30 B 1
Example 7
1 10 A 1
12 20 A 1
21 30 B 1


题目描述:
给出一个边长为H的正六边形,如图。

六边形中有空格或者A或者B或者C或者D。求最少的填充空格的个数,使A、B、C、D四个区域相连通。
题目分析:
由于H的范围[2, 20]平面上点的个数上限是1201,搜是阶乘级别的,不作考虑。在想这道题的时候,有一种考虑就是,对于填充空格最少的结构S,对于其中的两点,必然是两点间的最短距离(当然这两点不包括同一分量中的两点)。如果不是,就不符合结构的最优性。所以产生了一种算法就是修改MST算法,先将一个分量放入MST集合,然后向MST集合中添加离集合最近的分量,由于分量和分量之间的路径有多条,所以深搜出路径把路径上所有的点放入MST集合,然后更新未加入MST集合的分量到MST集合的距离。这个算法应该是正确的,但是由于路径搜索的开销是指数级别的,这个想法也被否定了。
Steiner树是这样的一种图论问题,就是对于一个图G=(V, E),求最小的路径费用将规定的点连起来,形成生成树。猛地一看,会想到MST。但是我尝试了MST的子树、V子集的MST,结果都失败了,后来才知道,这个问题时NP-Complete,在数据范围较小的情况下,状态压缩DP是最好的解决方法。这个题目有点像,Steiner树。网上有一个说明是,Euclid空间上的N个点的Steiner树至多由这N个点和另N-2个点构成,而这个题的思路马上产生,由于图上只有4个点,所以,Steiner树结构经过的中间点至多有2个,枚举零个中间点、一个中间点、两个点,分别求MST,最小值就是答案。
虽然思路很明确,但是这道题还是写了一天,毛概课上程序结构大概成型,午睡时开拍,1个小时后拍成,Bug无数。晚上MCM美赛报名,八点半回寝室,Debug了一个小时,终于觉得没有问题了,交上去居然超时了!一想O(N^2*V^2) = 1200*1200*6*6 = 51,840,000是挺大的,加了几个小优化,就是如果枚举i,j点时发现G[t][k] > ans,t属于{i,j},k属于{0,1,2,3}就直接无视。
代码中预处理了,label和adj。大概会带来一定常数上的优化吧。
YY:如果没有gerrob神牛,这题我大概是1/X,小小庆祝一下。

参考代码:
由于百度的长度限制,代码贴补上去了。这个228的怪物,还是自己收藏的好。 解题转自:http://hi.baidu.com/prayan1988/item/e52ddb0d111e627abfe97e10


  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])