P8960 折纸 题解

· · 题解

题目描述

题目需要你回答 t 个问题，每个问题可以要求你把一张纸按照一个给定 01 串 s 的规则对折 n 次后展开。对于第 i 次折叠，如果 s_i=0，将纸从左到右对折，使左边对齐右边；如果 s_i=1，将纸从右到左对折，使右边对齐左边。对折全部是从上方翻。接下来将会展开，展开后纸片在原位，只是保留了折痕。

题目想要知道的是，从左往右数第 k 个折痕是峰折（向上突起的折痕）还是谷折（向下凹陷的折痕）。如果该询问的答案是峰折，输出 Up；否则输出 Down。

题目思路

这道题有很多种解法。这里讲一讲我的思路。

我们可以手动折叠以下试一试，发现折痕的形成是很有规律的。每一次的折痕其实相当于在前一次的折痕之间进行一系列的“插入”操作。也即，第 n 次操作形成的折痕其实在前 n-1 次形成的折痕之间。（这是一个规律性的结论，难以给出严格的证明。下同。）

图示：

而每一次插入的折痕也是有规律的，依次都是“峰，谷，峰，谷……”（这种情况编号为1）或“谷，峰，谷，峰……”（这种情况编号为2）交替出现。那么什么时候插入的是情况1、什么时候插入的是情况2呢？通过找规律发现，这其实和上一次折叠的方向有关。如果上一次是从左往右折叠，那么插入的将是情况1，否则将是情况2。那么，我们就可以根据这些规律来设计算法计算第 k 个折痕是峰折还是谷折。

这里我们考虑用分治递推的方式来解决这个问题。假设我们现在已知第 k 个折痕必然是在前 floor 次折叠当中产生的，并且在前 floor 次折叠产生的折痕当中位于第 cur 个。如果 cur\&1=1 ，也即 cur 为奇数，那么第 k 个折痕必然是第 floor 次折叠产生的第 (cur>>1)+1 个折痕。否则第 k 个折痕必然在前 floor-1 次折叠中产生。此时 cur 应该是多少呢？经过推理得到，应该变成 cur>>1 。接下来在对此进行重复的递推即可。当 floor=1 时，cur 只可能为 1 ，因此我们的递推必然是有穷的。

思路明白了，代码就好些了。这里因为个人习惯加了一些看起来冗余的读入优化。代码很丑，请见谅。

代码

详见注释。

#include<cstdio>
#define f_inline inline __attribute__((always_inline))
using namespace std;
using UL=unsigned long;//用于存储非负整数
f_inline char gc()//快速读入一个字符
{
#define MAXN 100000
    static char buf[MAXN],*l,*r;
    return (l==r)&&(r=(l=buf)+fread(buf,1,MAXN,stdin),l==r)?EOF:*l++;
#undef MAXN
}
f_inline UL read()//快速读入一个非负整数
{
    register char ch(gc());
    register UL x(0);
    while(ch<'0'||ch>'9')
        ch=gc();
    while(ch>='0'&&ch<='9')
        x=(x<<1)+(x<<3)+(ch^48),
        ch=gc();
    return x;
}
f_inline void read_str(register char *p)//快速读入一个字符串
{
    *p=gc();
    while(*p<'0'||*p>'1')
        *p=gc();
    while(*p>='0'&&*p<='1')
        *(++p)=gc();
    *p='\0';
}
char s[65];//用于存储题目中描述的折叠方式
int main()
{
    register UL t(read());//读入数据组数
    while(t--)//重复进行t次
    {
        register const UL n(read()),k(read());//按照题目要求读入n和k的值
        read_str(s+1);//读入字符串，下标从1开始
        register UL cur(k),floor(n);//初始化cur和floor的值
        while(!(cur&1))//只要没有达到边界条件就重复递推
            cur>>=1,
            --floor;
        cur=(cur>>1)+1;
        register const bool flag(floor == 1 || s[floor - 1] == '1');
        //如果flag==true,那么当前第一次插入的是谷折，否则是峰折
        //多次实验可以得到，如果上一次是向左折的那么flag<-true,否则flag<-false
        fputs(flag?((cur&1)?"Down\n":"Up\n"):((cur&1)?"Up\n":"Down\n"),stdout);//按照题目要求输出
    }
    return 0;
}