解题报告

总结

深度优先搜索的思想。

分析

按给定的规则一个一个生成字符串，生成到第 $n$ 个的时候停止然后输出。这个很容易将递归改为循环实现。

总结

大数的余数问题。

分析

除数为大数的求法：

int mod = 0;
char ch;
while (c = getchar())
    mod = (mod*10 + ch-'0') % b

其中 b 为被除数。即利用余数的性质从最高位逐个读入。
而题中 CRC 的求法是一个字节一个字节的算，所以对上面的程序小加修改：

mod = ((mod<<8) + ch-'0') % b

陷阱

CRC 校验码是算在除数中的。所以处理完输入文本，要重复2次上面的操作，以空出 CRC 校验码的位置。

总结

简单的模拟问题，按规则判断即可。

总结

思路很简单，考虑各种情况即可。

总结

Floyd-Warshall算法。

分析

如果有环，那么对于 Floyd-Warshall 的三重循环，$\exists k, count[i][j] > 0\ if\ (i = j)$。

总结

搜索问题，按深度优先的思路可以顺利通过。

分析

要求按字母序输出所有可能的解。思路如下：

1. 假设最后的输出保存在 $order[0\dots n]$ 的数组中，第 $n$ 层迭代确定数组的第 $n$ 个元素，全部确定之后就输出，然后回溯。
2. 进入第 $k$ 层迭代，假设当前元素为 $S = \{a,b,c,d,e\}$，当前规则为 $R = \{a<b, c<d\}$。有两个步骤：
   1. 选择第 $k$ 个元素。除当前出现在规则右边的元素之外，依字母选择。可选的元素是 $S^\prime = \{a,c\}$。
   2. 依次从 $S^\prime$ 中选取元素，例如 $a$，从 $S$ 中去掉已经选择的元素，然后去掉 $a$ 对应的规则，即 $R=\{c<d\}$，然后进行下一层迭代

总结

简单的文本处理。

分析

利用 std::map、std::set 和 std::vector 等结构实现比较方便。

总结

简单的广度优先搜索。

总结

简单的几何问题。

陷阱

浮点数精度可能会导致WA。换一个不同的实现方法就可以AC。

总结

只利用给定的方法，$flip$，对数组排序。

分析

排序方式有很多。因为原题并没有要求最优解，所以有一个简单的思路：假设有一个长度为 $n$ 的栈：

1. 找到栈中最大元素的位置，$k$
2. $flip(k)$，这样最大的元素就在栈顶了
3. $flip(1)$，这样最大的元素就在栈底了
4. 对长度为 $n-1$ 的栈重复上面的步骤

基本的想法就是每次都把当前最大的元素放到栈底，循环 $n-1$ 次之后就排序完成了。

陷阱

$flip(k)$ 中 $k$ 是从栈底算的，栈底元素位置为 $1$，栈顶的位置为 $n$。