题解：B4532 [信息与未来 2026] 折纸

qianyuzhe · 2026-05-27 14:12:34 · 题解

题意简述

对一张 2^n\times2^n 的纸做恰好 n 次纵向对折和恰好 n 次横向对折后，求原本位置 (1,1) 的一格现在在从上往下数第几层以及其正反面是否与原来相同。

题目分析

由于 (1,1) 刚开始在左上角，又因为每次折叠后角落仍将变为角落，所以该格一定永远在角落。

我们考虑维护一个布尔变量 a，表示其是否在下半部分；维护一个布尔变量 b，表示其是否在右半部分；维护一个整型变量 l，表示其在从上往下数第几层。

先考虑 s_i=\texttt{D} 的情况。注意到 l 的改变只与 a 有关。若 a=1，则仅仅将上半部分的 2^i 层加到下半部分，即 l\gets l+2^i。若 a=0，则不仅要 a\gets 1，上下还会颠倒，即 l\gets 2^i-l+1。

if(s[i]=='D'){
    if(a)c+=1<<i;
    else{
        a=1;
        c=(1<<i)-c+1;
    }
}

其它三种情况同理，由对称性，我们可以写个函数来减少码量：

void f(bool&x,bool y){
    if(x==y)l+=1<<i;
    else{
        x=y;
        l=(1<<i)-l+1;
    }
}

然后再看第二问：注意到正反面只与 a\oplus b 的值有关，即 "UD"[a^b]。

代码

#include<bits/stdc++.h>
using namespace std;
int n,i,l=1;
bool a,b;
char c;
void f(bool&x,bool y){
    if(x==y)l+=1<<i;
    else{
        x=y;
        l=(1<<i)-l+1;
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    for(i=0;i<2*n;i++){
        cin>>c;
        if(c=='D')f(a,1);
        if(c=='U')f(a,0);
        if(c=='R')f(b,1);
        if(c=='L')f(b,0);
    }
    cout<<l<<' '<<"UD"[a^b];
}