数据结构与算法

背景

今天是琪露诺到寺子屋上课的第一天，代课的八云蓝老师讲的一些代码和算法根本搞不懂啦，好想回家冻青蛙！

寺子屋中的题目可能会让新生一时半会摸不到头脑，上白泽慧音老师建议同学们可以动用任何方式来获取思路。

题目一：时间空间复杂度

八云蓝老师课上讲了有关估计算法效率的知识，即时间复杂度和空间复杂度的概念。请你帮琪露诺同学整理有关知识点：什么是时间复杂度？什么是空间复杂度？这两个概念的基本表示形式是什么？为什么复杂度中的常数项可以被省略？

假设橙的大脑符合现代计算机标准计算速度（即约为1e8次计算每秒），
要处理1e5~1e6量级的数据最差使用什么时间复杂度的算法？
要处理1e4量级的数据最差使用什么时间复杂度的算法？

题目二：算法初步

背景

上课时琪露诺使用了符卡冻符「Perfect Freeze」 冻结了一些弹幕（≤10000），现在琪露诺想知道具体有多少弹幕，她把所有弹幕排成一列，从第一个开始报数。

以 Ax 为报数周期，最后一个报的数为 Ay
以 Bx 为报数周期，最后一个报的数为 By
以 Cx 为报数周期，最后一个报的数为 Cy
以 Dx 为报数周期，最后一个报的数为 Dy

任务

请你编写一段程序（语言任意），实现以下功能。

现在你已知上面这八个数据，请你帮助琪露诺计算一共冻结了多少弹幕。如果有多个答案，输出最小值。

输入

输入为四行：

1
2
3
4

Ax Ay
Bx By
Cx Cy
Dx Dy

(0 ≤ 以上所有数据 < 20)

输出

输出为一行：所有的弹幕总数

参考样例

1
2
3
4

2 1
6 3
5 1
4 1

1

21

解释

21mod2=1
21mod6=3
21mod5=1
21mod4=1

题目三：栈

背景

数清楚弹幕的数量之后，在下课后琪露诺与橙玩起了弹幕匹配的小游戏，琪露诺冻结了一系列不同种类的弹幕（括号）
即：左括号‘(’，右括号‘)’，左中括号‘[’，右中括号‘]’，左大括号‘{’，右大括号‘}’

现在橙将这些括号（每种括号可能有多个）以某种顺序排列，现在要将每一对左右括号进行匹配，让琪露诺判断这段括号序列是否合法。

合法的例子：对于任意的一个括号，一定存在一个不与其他括号匹配的括号与其匹配。

1
2

"()"
"({[]})[()]"

非法的例子：存在一个括号，没有一个不与其他括号匹配的括号与其匹配

1
2
3

"("
"([)"
"}{"

任务

请你编写一段程序（语言任意），实现以下功能。

输入

第一行为总行数，之后每一行输入一段括号序列（一段仅包含以上六种括号的字符串）

输出

如果该行的括号序列合法，输出“YES”，反之输出“NO”

参考样例

1
2
3
4

3
}{
({[]})[()]
([)

1
2
3

NO
YES
NO

提示

如果你有一定的编码基础，看了以上题目有自己的想法的，尽情地去发挥自己的想象吧！欢迎多样化的答案与思考。

如果你实在没有任何思路，不妨去查询学习栈的有关知识！

题目四：尼姆游戏

背景

放学后琪露诺与橙玩取弹幕游戏，可是琪露诺总是输给橙。游戏规则如下：

地上有 $n$ 堆弹幕（每堆弹幕数量小于 $10^4$，大于 0），每人每次可从任意一堆弹幕里取出任意多枚弹幕扔掉，可以取完，不能不取。每次只能从一堆里取。最后没弹幕可取的人就输了。

橙告诉琪露诺，在每堆弹幕数量被确定的情况下，可以直接确定谁会必胜。假设两人都像八云紫一样老谋深算（指两人足够聪明，每一步都会采取最优策略），琪露诺先手，对于给定的弹幕堆判断谁一定可以取胜。

如果琪露诺取胜，输出 Cirno
如果橙取胜，输出 Chen

任务

请你编写一段程序（语言任意），实现以下功能。

输入

第一行一个整数 $n$，表示一共有 $n$ 堆弹幕（$n$ ≤ $10^4$）
第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 堆弹幕中一共有多少个弹幕

输出

如果先手必胜输出 Cirno，如果后手必胜输出 Chen

参考样例

样例 1

1
2

2
1 1

1

Chen

解释

琪露诺先拿第一堆的一个弹幕，第一堆为空
橙再拿第二堆的一个弹幕，第二堆为空
琪露诺没有弹幕可以拿了，橙获胜

样例 2

1
2

2
3 1

1

Cirno

解释

琪露诺先拿第一堆的两个弹幕，第一堆还剩一个
橙再拿第一堆的一个弹幕，第一堆为空
琪露诺再拿第二堆的一个弹幕，第二堆为空
橙没有弹幕可以拿了，琪露诺获胜

样例 3

1
2

10
5 5 4 4 3 3 2 2 1 1

1

Chen

提示

这道题对于没有了解过博弈论的同学可能有些困难，推荐去学习有关巴什博弈的相关知识。

加分点

对于以上算法题目，能否分别分析出你写出的算法的时间复杂度呢？

如果对于更大的输入规模，能不能更加优化算法的时间复杂度呢？

你的代码风格是否规范，其他人能否比较轻松地读懂你的代码呢？