汕大Apr. Monthly 解题分析
1001 Alice and Bob
本题考察二分算法思想的逆思维，只要能够从题目描述感觉到，看出是二分思想的蜕
变，哪就很简单了。答案是2^N-1。简单题，数据规模很小。
1002 Architect's Trouble
本题考察几何计算能力，要注意精度，这个可能是导致最多人WA的地方，甚至没人能
够AC。
1003 Rippo's Connection Work
本题考察图论当中，任意两点间的最短路径。直接使用Floyd算法可以解决，数据规
模不大，O(N^3)可以通过，但要注意特殊数据，两个相同点之间的最短路径为0，还
有不存在通路时输出"Cannot Be Connected."
1004 Drawing
本题考察凸包思想，不用去求凸包。可以想象每次求出剩余点的凸包，然后将凸包上
的点用线段依次连起来，再去掉已经被连接的点，再重复前面的凸包过程。可见答案
很简单：[N/2]，N是不重复的点的数目。
1005 The Game with God
这是一个经典的随机过程模型：Hidden Markov Model(隐马尔科夫模型)。求解的关
键在于，用条件概率公式表示出所求，然后DP求解。另外，本题需要特别注意计算过
程中的精度问题。
复杂度: O(T*N*N)
1006 Count the Sum of Index
本题考察字符串下标处理，进行一次性统计的方法，关键要读懂题目，是一道简单题
，但不容易AC，因为必须细心缜密，注意到题目给出的规模，最大字符串下标1000000
，因此必须考虑到特殊数据，当sum=1+2+…+N时，N=1000000，则sum的值超出long的
表示范围，必须使用long long，不然肯定WA。
时间复杂度： O(N)
1007 Kinfkong's Problem II
本题考察容斥原理和高精度算法。看到规模N (1<=N<=10^1000)就应该想到了。
1008 The Language of Rippo
本题考察二分和贪心算法，求不增序列的个数。时间复杂度要求O(NlogN)
1009 Maximum Telepathy
本题考察数据结构的堆排序算法，由于规模较大，N=100000，M=1000，因此不能使用
最坏情况的算法复杂度O(N^2)的算法，即使qsort也不能用，特殊的有序数据使得qsort
超时，必须使用O(N*logN)的算法。由于N>>M，所以建两个堆，一个处理N的序列中的
初始建堆以及做筛选调整，一个处理M的序列的初始建堆。
时间复杂度：O(N*logN)
另外，由于本题有特定的约束条件，1<=Ai, Bi<=1000000，因此可以使用聪明而方便
的快速标记方法，可以不需要排序也能AC，而且效率较高，复杂度可降为：O(N)
本文地址：http://com.8s8s.com/it/it31805.htm