总结

深度优先搜索的思想。

分析

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

posted @ 2013-06-17 22:50 happyac 阅读(325) | 评论 (0)编辑 收藏

总结

大数的余数问题。

分析

除数为大数的求法:
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 校验码的位置。

posted @ 2013-06-17 16:33 happyac 阅读(1233) | 评论 (0)编辑 收藏

总结

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

posted @ 2013-06-17 16:21 happyac 阅读(226) | 评论 (0)编辑 收藏

总结

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

posted @ 2013-06-16 23:07 happyac 阅读(241) | 评论 (0)编辑 收藏

总结

Floyd-Warshall算法。

分析

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

posted @ 2013-06-16 09:18 happyac 阅读(270) | 评论 (0)编辑 收藏

总结

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

分析

要求按字母序输出所有可能的解。思路如下:
  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\}$,然后进行下一层迭代

posted @ 2013-06-14 20:30 happyac 阅读(1123) | 评论 (0)编辑 收藏

总结

简单的文本处理。

分析

利用 std::mapstd::setstd::vector 等结构实现比较方便。

posted @ 2013-06-14 15:10 happyac 阅读(165) | 评论 (0)编辑 收藏

总结

简单的广度优先搜索。

posted @ 2013-06-13 18:44 happyac 阅读(318) | 评论 (0)编辑 收藏

总结

简单的几何问题。

陷阱

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

posted @ 2013-06-13 14:17 happyac 阅读(227) | 评论 (0)编辑 收藏

总结

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

分析

排序方式有很多。因为原题并没有要求最优解,所以有一个简单的思路:假设有一个长度为 $n$ 的栈:
  1. 找到栈中最大元素的位置,$k$
  2. $flip(k)$,这样最大的元素就在栈顶了
  3. $flip(1)$,这样最大的元素就在栈底了
  4. 对长度为 $n-1$ 的栈重复上面的步骤
基本的想法就是每次都把当前最大的元素放到栈底,循环 $n-1$ 次之后就排序完成了。

陷阱

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

posted @ 2013-06-12 21:37 happyac 阅读(1302) | 评论 (0)编辑 收藏

仅列出标题
共3页: 1 2 3