教案解题报告

1、Pr Folding解题摘要题意简述给出 8 种不同的折纸操作，并规定纸上每个点的坐标，完成两个任务：任务一：根据给出的操作序列，计算最后向上一面的坐标；任务二：给出最后向上一面的坐标，求出字典序最小的一个操作序列。（详见原题）分析本题包含了两个任务，两者之间的关系不是很大，分别进行分析。任务一任务一的难度不是很大，由于给出了操作序列，操作就可以了。只需要依次模拟进行每一步的折纸而最后朝上的那一面原本是纸的正面还是的确定，也十分简单。发现，如果第一步的折叠操作是“大写字母”（也就是将纸的一部分折下去，被另一部分盖住），那么这时候纸露在外面的部分都是原来纸的正面，今后不论如何折叠，纸的将不可能再

2、被翻出；同样的，如果第一步折叠操作是“小写字母”（也就是将纸的一部分翻起，盖住另一部分），那么这时候露在外面的部分都是原来纸的，今后无论怎样折叠，纸的正面也在也不可能被翻出来。因此，判断最后朝上的那一面的正反，只需要看折纸操作序列的第一个字母，如果是大写，则最后那一面是原来纸的正面（“F”）；如果是小写，则最后那一面就是原来纸的（“B”）。任务二任务二看起来无从下手，每一步操作都有八种不同的选择，而怎样的序列能够最后使给出的部分1向上也没规律。那应该如何解决呢？经过分析，发现，最后一次折叠前，只要目标面完整的出现在当前纸的表面（显然应当是正面或的一半），就一定有办法通过一次折叠使它朝上（具体办

3、法见表 1）。1下文中，称“给定的最后向上的部分”为“目标面”。任务一任务二基本思路模拟贪心时间复杂度O(Nk)O(Nk)空间复杂度O(1)O(1)表 1根据这个性质继续向前倒推，就可以得出这样一个结论进行每一步操作时，都应当在保证目标面始终在当前纸的表面的前提下，选择字典序最小的操作进行折叠。因此，解决任务二的大体思路就被分为两步：（1）保证目标面在当前纸的表面，尽量选择字典序小的折叠操作，直到目标面成为当前纸的正面或为止。（2）如果这时目标面朝下，那么可以通过改变操作序列的最后一个字母，将目标面调整为朝上的。第一步中，应该如何构造操作序列呢？前面在任务一的分析中，得出了这样一个结论：第一个

4、折叠操作字母的大小写决定了露在外的部分是纸的正面还是。因此也可以发现，每次折叠时，如果当前目标面朝上，那么就需要进行一次“大写字母”的折叠操作；如果当前目标面朝下，那么就需要进行一次“小写字母”的折叠操作。进一步分析，折纸操作中，操作“B”“T”“b”“t”都是将纸在 y 方向上的长度减半，而相应的“L”“R”“l”“r”都会让纸在 x 方向上长度减半。而“B”和“T”、“b”和“t”、 “L”和“R”、“l”和“r”在实际效果上几乎是相同的也就是说，经过这些相对的折叠，露在表面的部分是相同的。因此完全可以忽略“T”“t”“R”和“r”，在第一步构造折叠操作序列时，只使用“B”“b”“L”和“

5、l”。而又因为“B”比“L”小，“b”比“l”小，因此，如果当前的纸在 y 方向上的长度不等于目标面 y 方向上的长度时，“B”或“b”。又会优先使用因此，构造操作序列的过程又分为两步：（1）首先通过一系列“B”和“b”，使得当前纸在 y 方向上的长度和目标面相同；更具体地，如果目标面在当前纸的正面，则用“B”，否则用“b”。（2）再通过一系列“L”和“l”，使得当前纸 x 方向上的长度也和目标面相同如果目标面在当前纸的正面，则用“L”，否则用“l”。这样，就可以得到第一步求大致的折叠操作序列也就完成了。第二步的调整处理要容易很多，首先判断目标面当前是朝上还是朝下，如果朝下，则修改操作序列的最

6、后一个字母“B”改为“T”，“b”改为“t”，“L”改为“R”，“l”改为“r”。这样一来，任务二也就得到了的解决。通过前面的分析，折纸操作规则。坐标表示发现，有两个方面内容与解题密切相关，分别是纸的坐标表示和2这里所说的位置，都是指最后一次折叠前目标面在纸上的位置。目标面原来的位置最后一次折叠操作朝上的上半部2B朝上的右半部L朝上的左半部R朝上的下半部T朝下的下半部B朝下的左半部L朝下的右半部R朝下的上半部T纸的坐标表示也就是对一张纸经过若干次折叠后情况的表示。通过前面的分析也可以看出，一张纸被折叠进去的部分再也不会对纸的折叠产生任何影响。因此只需要一下整张纸正反两面共 8 个角的坐标就可以

7、了，也就是从(x1 , y1)到(x8 , y8)，（见表 2）。这样也就能够很容易的表示任意时刻纸的状态了。表 2折纸操作明确了纸的坐标表示，那么折纸操作的规则也就很容易确定了，表标转换规则：3给出了具体的坐表 3时空复杂度分析上面分别分析的两个任务的解决方法，以及一些相关信息的处理。那么这个算法的时空复杂度又如何呢？空间上，只需要当前纸的状态和目标面的情况就可以了，复杂度为O(1)。时间上，对于每一组数据，不论是任务一还是任务二，都只需要依次模拟，这样的时间复杂度，也就是O(k)，其中 k 表是操作序列的长度，本题中不会超过 20。3这里的“左上角”，表示与正面左上角相对的点。实际上是将纸

8、水平翻过来以后的右上角。(x1 , y1)(x2 , y2)(x3 , y3)(x4, y4)(x5 , y5)(x6, y6)(x7 , y7)(x8, y8)B(x1 ,y1)(x2 ,y2)(x3 , (y1+y3)/2)(x4 , (y2+y4)/2)(x3 ,y3)(x4,y4)(x3 , (y1+y3)/2)(x4 , (y2+y4)/2)L(x1+x2)/2,y1)(x2 ,y2)(x3+x4)/2,y3)(x4,y4)(x1+x2)/2,y1)(x1 ,y1)(x3+x4)/2,y3)(x3 ,y3)R(x1 ,y1)(x1+x2)/2,y2)(x3 ,y3)(x3+x4)/2

9、,y4)(x2 ,y2)(x1+x2)/2,y2)(x4,y4)(x3+x4)/2,y4)T(x1 , (y1+y3)/2)(x2 , (y2+y4)/2)(x3 ,y3)(x4,y4)(x1 , (y1+y3)/2)(x2 , (y2+y4)/2)(x1 ,y1)(x2 ,y2)b(x7 ,y7)(x8,y8)(x7 , (y5+y7)/2)(x8 , (y6+y8)/2)(x5 ,y5)(x6,y6)(x7 , (y5+y7)/2)(x8 , (y6+y8)/2)l(x5+x6)/2,y5)(x5 ,y5)(x7+x8)/2,y7)(x7 ,y7)(x5+x6)/2,y5)(x6,y6)(x7+x8)/2,y7)(x8,y8)r(x6,y6)(x5+x6)/2,y6)(x8,y8)(x7+x8)/2,y8)(x5 ,y5)(x5+x6)/2,y6)(x7 ,y7)(x7+x8)/2,y8)t(x5 , (y5+y7)/2)(x6, (y6+y8)/2)(x5 ,y5)(x6,y6)(x5 , (y5+y7)/2)(x6, (y6+y8)/2)(x7 ,y7)(x8,y8)(x1 , y1)(x2 , y2)(x3 , y3)(x4, y4