自动搬运

查看原文

来自洛谷，原作者为

	Moon_Traveller 心之所向，素履以往。|| 寄->摆。

搬运于2025-08-24 22:44:07，当前版本为作者最后更新于2023-01-23 11:07:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

首先，我们通过动手模拟可以得出：折 $n$ 次时，折痕数为 $(2^n - 1)$。

我们先来模拟一下每次折后的结果（设谷为 0，峰为 1）：

当 $n = 3, s = \tt{010}$ 时:

1 2 3 4 5 6 7 // 这一行表示折痕位置

第一次折：
      0      
第二次折：
  1       0
第三次折：
0   1   0   1
所有折痕：
0 1 1 0 0 0 1

当 $n = 3, s = \tt{011}$ 时:

1 2 3 4 5 6 7

第一次折：
      0
第二次折：
  1       0
第三次折：
0   1   0   1
所有折痕：
0 1 1 0 0 0 1

多试几组数据之后，我们可以粗略得出一个结论：折痕与 $s$ 的最后一位无关。

那么，我们可以猜测：第 $i$ 次折，折痕的朝向与 $s_{i-1}$ 有关。

再次观察上面模拟的结果，可以发现，折痕的得出过程类似于一个二叉树。第 $i$ 层的节点（$i$ 从 $1$ 开始），左子树与 $s_{i-1}$ 相反，右子树与 $s_{i-1}$ 相同。

也就是说，最后的结论只与前一次折的方向有关。具体的实现方法可以用二分，每次折叠后把结果存储起来，最后得出的结果就是最终结果。

代码：

#include <iostream>
#include <cmath> // pow() 函数要用到这个
using namespace std;

long long T;
long long n, k;
char s[65];
bool b[65];
bool flag; // true => Up, false => Down

int main()
{
    cin >> T;
    for(int t = 0; t < T; t++)
    {
        cin >> n >> k;
        for(long long i = 1; i <= n; i++)
        {
            cin >> s[i];
            b[i] = (s[i] == '1'); // 将字符串存成bool型数组，方便比较
        }
        long long l = 1, r = pow(2, n) - 1; // 二分的初始左右边界
        long long i = 1;
        flag = false; // 第一道折痕一定是谷折
        while(l <= r) // 从第二次折开始遍历
        {
            i++; // 第i-1次折叠
            long long mid = (l + r) >> 1;
            /*
            上面那句相当于：
            long long mid = (l + r) / 2;
            */
            if(k < mid) // 处理左半部分
            {
                r = mid - 1;
                flag = !b[i - 1];
            }
            else if(k > mid) // 处理右半部分
            {
                l = mid + 1;
                flag = b[i - 1];
            }
            else // 如果 (k == mid) 说明到达了目标位置，可以输出了
            {
                cout << (flag ? "Up" : "Down");
                /*
                上面那句可以替换成：
                if(flag)
                {
                    cout << "Up";
                }
                else
                {
                    cout << "Down";
                }
                */
                cout << endl; // 别忘了换行
                break;
            }
        } 
    }
    return 0;
}