U292234题解

junhaowang · 2024-01-29 18:41:17 · 个人记录

传送门：https://www.luogu.com.cn/problem/U292234

这道题我其实在心里酝酿很久，很早就已经出了（看看这题号有多小就知道），当时也是有了解决的思路滴。

不过一直没有时间用代码来实现一下（悲）

今天刚考完，就赶紧把惦记了很久的——这道题，做了一下。

这个代码其实讲的就是递归。

众所周知……

咳咳，递归是从外面一只刷刷刷推到最里面一层，然后从最里面一层开始，一层层往外套娃解决。

咱们也是这个思路，我们不折纸，我们投其所好，慢慢地展开。

剩下的只需要拿上一张久违的草稿纸，折一折，你就会明白思路了。

#include <bits/stdc++.h>
//#pragma GCC optimize (2)
using namespace std;;

#define int long long
#define rint register int

int
    n
;;
string
    ans
;;

string reverse (string x);; //先声明字符串反转函数

string solve (int n) //递归，一层层展开
{
    if (n == 0) //递归边界：没有折
    {
        return "";;
    }
    //接下来建议拿上白纸模拟一下展开过程，不然很难理解
    //比如solve(2)是"001"，然后拿上你的白纸展开！
    //展开到一半观察，下面一半纸是"001"，就是刚才的状态
    //上面一半纸翻转开之后凹凸会反，而且顺序还会整个左右相反，就是"011"
    //完全展开观察，除了这两半，中间还有一个凹下去的折痕
    return solve (n - 1) + "0" + reverse (solve (n - 1));;
}

signed main (void)
{
    ios::sync_with_stdio (false);;
    cin.tie (0), cout.tie (0);;
    cin >> n;;
    ans = solve (n);;
    for (rint i = 0; i < ans.length (); i++)
    //蒟蒻依稀记得ans.size()好像是O(n)的，ans.length()是O(1)的
    //所以一般就用后者吧
    {
        cout << ans [i] << ' ';;
    }
    return 0;;
}

string reverse (string x)
{
    string
        ret
            = ""
    ;;
    for (rint i = x.length (); i >= 0; i--)
    {
        switch (x [i]) //由于x[i]是char，可以用switch
        {
            case '1':
                ret += "0";;
                break;;
            case '0':
                ret += "1";;
        }
    }
    return ret;;
}