P8960 题解

· · 题解

传送门

首先，我们通过动手模拟可以得出：折 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;
}