C.City Folding
题意:有一个由 \(2^n\) 条等长线段组成的线,你可以进行 \(n\) 次 对折 ,可以从左向右对折或从右向左对折,给出初始时线段的编号 \(P\) ,问如何对折 \(n\) 次才能使对折后该线段恰好在从下往上数第 \(H\) 层?
\(\operatorname{Solution}\) 构造
可以倒过来考虑这个过程（即从最后一次折叠开始）。
如果H在纸的上半部分，那么在这步之前，它在折叠在另一张纸上的那一半。通过观察，我们可以得出，对于每一步，我们是否应该折叠H所在的部分
如果在这个时刻，这个位置应该是将被折叠的一半的一部分，那么如果P在左半区，答案为L，相反，如果它不应该在折叠的一半上，答案为R
不要忘记，每当我们将一部分折叠在另一部分的顶部时，其元素的顺序就会颠倒。
时间复杂度 \(O(n)\)
K.Kind Baker
蛋糕为100×100网格的方形蛋糕块。如果集合中的每一对碎片都是直接连接的（它们共享一侧）或间接连接的（有一个碎片序列，可以通过直接连接的碎片从一个碎片到另一个碎片），那么一个碎片集合就是连接的。
Flora有一台机器，可以接收一组相连的蛋糕块，并在每一块蛋糕上涂上一定的图案。每次机器运行时都会使用不同的图案。在使用机器给定次数后，每件物品上都会有一个（可能是空的）图案组合。如果两件物品的图案组合不同，则视为不同类型。Flora想知道她必须使用该机器才能获得 \(k\) 种不同类型的蛋糕块的最小次数，以及每次使用该机器时选择一个连接的蛋糕块集合的可能方法。
\(\operatorname{Solution}\) 构造
首先，如果我们使用机器 \(n\) 次,我们最多可以有 \(2^n\) 不同类型的作品。所以我们知道 \(n\) 的值必须至少为 \(log2k\).
证明:
首先，如果k=1,则输出0。否则，用所有 \(n\) 填充第一列和第一行,现在我们有两种不同的类型，所以我们可以从k的值中减去2.
假设 \(k\leq 4000\)， \(n\leq12\) .\(2^\frac{n}{2}\leq100\).此外。令 \(k_1=⌊n/2⌋\) ,\(k_2=(n+1)/2\) 。对于每个值 \(i\in[0，k1)\) ,在从2到100的所有行上迭代，如果当前行的id设置了第i位，则将颜色i添加到整行。对于其他 \(k_2\) 值，对列执行同样的操作.
不难注意到，通过这样做，我们正好生成了 \(2^n\)种不同类型的碎片。此外，由于我们在第一行和第一列的每个单元格中使用了每种颜色，每种颜色都形成了一个连接的组件。所以这个方案是正确的。
剩下还需要做的部分是使不同类型的数量恰好等于 \(k\) 。这可以通过几种方式来实现。可以只执行所描述的过程，直到检测到已经有 \(k\) 个类型，或者可以生成所有 \(2^n\) 个类型，然后清除一些单元格，直到数量减少到刚好 \(k\) 即可。
时间复杂度 \(O(k)\)