Explain.txt

1001
简单题，没什么好说的。
#

1002
规模很小，想怎么做都行，最容易想到的就是 DFS
顺序搜索各个空置的点，存放最大值并刷新，全部遍历之后必然有最优解
基础 DFS，但是在 4x4 的规模下这样的贪心算法可以成立：
对于任一个空点，定义他的权值为它可以打到的格子总数，那么，按照权值小的往大的填，得出的结果最优。
#

1003
用一个栈搞啊搞啊的，也不算太简单了
刚开始 ACM 时候写的，拙劣的代码现在我都看不懂了
有一点要注意的是当两个数都不合法的时候，要取较大的
#

1004
说白了就是一个 DFS，每一步两种选择，选合法的路向后深入，每碰到结束就输出，完全遍历即可。
输入输出要稍加注意。
#

1005
可以 DP，广搜也行，比较基础的一道题
#

1006
解密，涉及数论，可以推出来公式
已知加密公式：
ciphercode[i] = (plaincode[ki mod n] - i) mod 28
现在要推出解密公式：
=> ciphercode[i] = plaincode[ki mod n] mod 28 - i mod 28
=> ciphercode[i] + i mod 28 = plaincode[ki mod n] mod 28
=> plaincode[ki mod n] = ciphercode[i] + i mod 28
于是，遍历 i 即可覆盖所有的 ki mod n 而完全确定 plaincode
#

1007
微积分题，用到有关级数的知识
函数 Fai(x) = sum( 1/k/(k+x), 1, inf )
显然 Fai(1) = 1.0
假如令:
Fai(x) = Fai(x) - Fai(1) + 1.0
= sum( 1/k/(k+x), 1, inf ) - sum( 1/k/(k+1), 1, inf ) + 1.0
= sum( 1/k/(k+x) - 1/k/(k+1), 1, inf ) + 1.0
= sum( (1-x) / k / (k+1) / (k+x), 1, inf ) + 1.0
然后，我们希望只累加到 N，使得它的余项大小在 10^-12 以内：
Fai(x) = sum( (1-x) / k / (k+1) / (k+x), 1, N ) +
	 sum( (1-x) / k / (k+1) / (k+x), N+1, inf ) + 1.0
我们要求出 N，使得 
R(N) = sum( (1-x) / k / (k+1) / (k+x), N+1, inf ) < 10^-12
当 k 很大的时候，可以认为：
(1-x) / k / (k+1) / (k+x) 接近于 (1-x) / k / k / k
然后根据提示，我们可以推知
R(N) = (1-x) / k / k / k + EPS(N)
其中，EPS(N) < 10^-12
可以求得，N 在 10000 多一点的地方就可以做到了。
具体操作可参见标程
#

1008
超经典搜索题，DFS 即可，但是需要一些剪枝手段。
首先声明，别读错题了，是有 n^2 个小木块，这些小木块不能旋转
然后把他们拍成一个方阵，使得满足要求
搜索的时候，先把所有的木块存起来，然后一排一排地放(DFS)
但是这样可能会有一种变态数据：
5 
1 1 1 1
 . . . 
接连24个
 . . .
2 2 2 2
这样的数据就绝对超时
因此必须剪枝，剪枝方法如下：
存放方块的时候用一个栈，栈里面放了方块的信息和累计个数
每读入一个，检查该方块是否已经存在，是则计数加一，不是则新建一个压栈
那么做 DFS 的时候就将多余的重复试验剪去了，这个算法 5s 多可以过
#

1009
难度不大，把规则读清楚直接模拟即可，但是规则比较乱得仔细读
#

1010
注意两点：
第一点：无论什么时候，只要用了浮点数，要注意精度问题
第二点：对于各种可能的情况要考虑周全。
可以用面向对象的设计模式使思路清晰。
计算方法：
原则上是，任意不相邻的边，如果有相交，那就是 Impossible
至于相交的情况需要细分。
面积的话，用一个圆点不动，跟其他边叉积求出有向面积累加即可。
#

1011
搜索，对于每个节点，对于他每种可衍生的左右子树进行深搜。
如果左右子树有一种为合法，则向上返回合法，直到根节点为合法。
由于是树型结构，DP是不需要的。
至于树的储存，采用数组结构，类似于堆。
#

1012
模拟，相当的蘑菇，尤其是读题方面，但把规则了解之后，并不难搞。
具体规则说明追加了一份描述文档。
#

1014
有两种选择：
数据结构好的可以考虑用个树来建模
又或者，可以一遍一遍地扫描字符串
确定优先级，然后将最高优先级的合并
详见解题报告
#

1016
这个题很有点组合数学的味道
对于括号配对的两种编码的转换
先将一种代码转换成括号字符串
然后转换成另一种代码
这样是相当直观的，不难
#

1024
博弈问题，记忆化搜索形式的 DP
当然前推法 DP 也可以
关键是找必输点，逻辑理清出了不难
再有就是日期的地方得小心

关于这道题的逻辑：
    假设有某一天是肯定能赢的：这天为 date1 = yyyy/mm/dd
明显，开始知道这样的日子有两个：即是2001/11/3和2001/10/4
    那么，现在随便找某一天，假如这个日子不合法，那这一天肯定是输的
否则，如果这一天的下个月同一天不存在，那么他 Move 到这个位置去肯定会导致他输，因此取决于紧接着的下一天是否必胜，即 win(someDay) = !win(someDay.nextday())
或者，如果这一天的下个月同一天存在，那么他有权利 Move 到这两个位置当中的任意一个，如果这两个位置当中至少有一个必输，那么他就可以将对手置于必输的位置，因此这个位置必赢，即 win(someDay) = !win(someDay.nextday()) || !win(someDay.nextmonth())
#

1025
求一个给定序列的最少上升子序列数。
贪心即可(完全可以不用链表)：
1>将所有的棍子信息放进一个链表。
2>选定一种方法，长度优先或是宽度优先，效果一样。
3>外层遍历开始：count计数----<1 loop>
4>内层遍历开始：选择表中长度最优先的一个棍子（指的是长度必须为现存棍子中最长的，如果长度相等则取宽度最大的一个）----<2 loop>
5>将其剔除，继续选择剔除，但是在后面的选择中必须保证长度宽度均分别小于刚刚剔除的棍子，并且长度优先选择。
6>重复，直到范围内不能再剔除，count++  ---->2 loop end<
7>还原最大范围，再次逐步剔除，直到整个表空  ---->1 loop end<
8>实际上安装机器的次数就是从大到小的单向路径的个数。
#

1026
一个逻辑算式的数学运算
可以采用笔算的方式计算
面向对象和位运算都可以借鉴。
#

1028
可以证明一个定理：
有一点应该可以看到的是：一个盘子只能移动一个偶数格。

那就是
如果总的盘子数为奇数，肯定可以；
如果总的盘子数为偶数，则考察奇数位置的黑盘子数目和偶数位置的黑盘子数目
如果他们之间至多相差1
那可以达到
否则的话，那就不能达到
#

1029
有一个贪心办法：
创建一个int[200]的数组，代表走廊的每一格
注意的是1和2共用一格，31和32共用一个，etc.
然后每输入一个数(1~400)
求出它们对应的编号，例如1对应0号走廊，38对应18号走廊，400对应199号走廊
用一个通式解决：x=(x-1)/2注意是整数除，得到走廊编号
然后将输入的两个走廊编号对应的走廊格子上分别加上10；
输入N张桌子的话，应该操作N次
那么到最后这个int[200]数组里面最大的数应当就是我们想要的。
#

1037
很明显的一个结论：
只要 m 和 n 任一个是偶数，那就不用走斜路，那就是 m * n
否则(m和n都是奇数)，那就只要走一次斜路就行了，是 m * n + 0.41
#

1039
构造一个编码树(每个节点有8个儿子)，一串指令可以到达它的一个节点，这个节点保存了一个字符串和概率值
难度在于建树过程，会用到 DFS，中间相当繁琐，也容易出错
其实也不需要这么复杂的数据结构，有比较暴力的排列然后查找方法，也不会超时。
#

1041
简单的几何题，先剔除太远的点，然后以其中任意一个点为左边界，查有多少个点在这个范围内
然后耗尽搜索即可，O(n^2)
#

1042
简单模拟题
按照提目的指示进行,移位方面善用deque可以得到很好的解决
剩下的，搞就是了
#

1043
很 mg 的一道模拟题，读题都烦死了，做了一整天
看清楚题目要求，用面向对象来写
其余看解题报告吧，说也说不清
#

1045
就是求和，它限制了边界，收敛性不用论证
#

1047
很基础的搜索题
BFS 或者 DFS 都行，效率一样
#

1048
Simple 算法，求12个数均值
#

1049
简单几何，先从半径求总面积，然后一除即可
#

1050
字符串模拟，注意几点：
1. 得分是 key 中次数 * word 中次数 开放的累加
2. 有这样的变态数据:
	, , , , , ,
	----------
	. . . . . .
	----------
	----------
注意输出是 0，空字符串不能算！！
就这个害我 WA 不计其数
#

1051
模拟题，没什么难的，主要是不可以在线更新状态。
必须把下一天的状态计算后存到一个新的矩阵，然后替换原来的。
这个也容易想明白。
在矩阵外面加一个值为 0 的外框可简化处理。
#

1056
模拟题，用一个 queue 来实现 worm，然后每个格子标记状态即可
#

1057
简单题，看着题目说明的步骤照着搞就是了
#

1058
基于图的模拟，先读取图，然后按照给定的路径走一圈就是了
#

1060
拓扑图的生成，每增加一个关系，向前向后各 DFS 一次
例如:
6 5
A<D               B<C
 0  0  0  1  0     0  0  0  1  0
 0  0  0  0  0     0  0  1  0  0
 0  0  0  0  0     0 -1  0  0  0
-1  0  0  0  0    -1  0  0  0  0
 0  0  0  0  0     0  0  0  0  0

A<B(注意传递关系) D<E
 0  1  1  1  0     0  1  1  1  1
-1  0  1  0  0    -1  0  1  0  0
-1 -1  0  0  0    -1 -1  0  0  0
-1  0  0  0  0    -1  0  0  0  1
 0  0  0  0  0    -1  0  0 -1  0
C<D
 0  1  1  1  1
-1  0  1  1  1
-1 -1  0  1  1
-1 -1 -1  0  1
-1 -1 -1 -1  0
如此，每标记一个新的关系(从没有到有)，计数 +1，
如果新增一个关系的时候原来已经存在关系，那么可能重复标记(不计数)
否则，出现矛盾。
然后当计数达到 n^2 - n 的时候，关系就完全确定了
注意有一点，一旦关系完全确定，以后就算有矛盾也是对的，题目得读清楚。
具体实现细节可见代码注释行
#

1061
模拟题，用栈
题目将操作说得一清二楚，照着搞就是了
#

1062
这个题关系比较扑朔迷离，是个组合数学的问题。
因此写了一份详细的解题报告，可以参考，此处略过。
#

1068
模拟，解密
先将暗文展开成 ".-" 串，同时获得暗文的节长
将节长翻转，并以此解密 ".-" 串，即得到明文
题目都说得很清楚，照着搞应该不会有错
#

1070
物理公式
交流电，虚数阻抗转换之后计算有效值即可
知道物理公式就是简单题了，有文档写出了公式
#

1073
简单模拟，先做乘法，然后转字符串检验一下就行
做的时候很早，写得太啰嗦
#

1074
由于规模较小，可以直接求和，然后枚举左上右下两个角，
应用容斥原理，O(n^4)勉强可过
但其实有 DP 的办法
#

1076
类似最长上升子序列，DP n^2 即可
#

1077
强大的组匹配模拟题，看源码的注释吧，上面写的应该够了
#

1078
基数运算，模拟。
我越来越发觉我前期写的代码实在是太难看了
#

1081
几何题，判断一个点是否在给定多边形内，经典
如果是一个内点，遍历所有边它的所有有向角度之和必定等于+360度
而如果是一个外点，这个结果应该是0度
#

1082
我做的第一个 Floyd
#

1084
图着色问题，由于说明了是平面图，因此有四色定理的前提，
搜索即可。
但是可能数据太弱，贪心乱搞居然也过了
#

1086
高精度除法
先将所有的八进制转成二进制，然后进行精度运算
因为二进制只有除二，因此可将除法转换成乘 5 再右移
#

1088
经典的 Josephu 环系列，直接模拟也不会超时。
但当然，用更强的 Josephu 环结论可以极大提高效率。
#

1089
蛮力枚举，最为高效
#

1090
解析几何公式，用中垂线交点求出外接圆心，然后搞。
#

1091
基础 BFS，经典题。
#

1092
基础最短路，用 Floyd 即可
#