2007 South Central USA Regional Programming Contest 解题报告

                                                                    农夫三拳@seu(drizzlecrj@gmail.com)

一、官方网址:

http://acm2007.cct.lsu.edu/

二、解题报告

1. One is an Interesting Number

按照题目描述的意思去做。可以预处理一下10⁶以内的平方数，立方数，四次方数，尽量避免浮点运算。

2. Verdis Quo

罗马数字转换成十进制整数，注意一下a[i]<a[i+1]的情况即可。

3. The Screen Behind the Mirror

不错的计算几何题。考察的知识包括计算一条射线和一条线段的交点，镜面发射后的角度。前者可以通过直线的参数方程和向量知识求解，后者通过分解向量为水平和垂直两个方向求解(可参见http://www.geometryalgorithms.com/Archive/algorithm_0104/algorithm_0104B.htm)。对于入射光线，计算最先遇到的Object是什么，递归得出最终结果。【注：发现把一些东东写成类很方便】

4. Another Brick in the Wall

添加源点S,汇点T，构建无向图。S点到第一排的所有点的权值为1，T点到最后一排的权值为0，其余每一个点与其相邻的点的权值为1当且仅当它们两者值不同，否则权值为0。其余不相邻的点权值为INF。计算S点到T点的最短路径即为结果。

5. The Sidewinder Sleeps Tonite

判断一个图形是否闭合，只需要考察每一个为’#‘的点的四周‘-’和‘|'的数量为0或者2（这里需要注意有可能会出现#的上方是’-‘,而下方是‘|’的情况，似乎测试数据没有包括类似这种的情况，但是我觉得应当考虑)；判断一个非问号的数字是否正确，只需要计算它四周的'-'的数量和‘|‘的数量是否与其自身相同； 判断闭合图形是否唯一，只需要沿着一条’-‘或'|'的边进行dfs，最终检查是否存在某条边没有被标记，同样我觉得这里应该检查闭合图形的合法性。

6. Rout 66

模拟题

7. Schottkey 7th Path

较复杂的字符串处理题, 我用map<string, vector<string> >搞的

8. Another Version of the Truth

刚开始我也认为这题是博弈...

通过BFS预处理每个点到每个Player的最近距离, 接着O(D*D)枚举摆放位置，进一步bfs，最终求一个最大的位置。我写的复杂度是O(D⁴*P²),其实可以写成

O(D⁴*P)。原因在于第二次的bfs过程可以直接求出增加的Influence的个数，而不需要与其它的对手再比较。

9. The Final Countdown

这题有个trick，有可能Countdown的时间已经超过了Start的时间。解法是分别保存每一个条件为true和false的holdtime，并取其中的最小值和最大值分别加入到

结果中。