题解：P12335 真真随机

· · 题解

发现几乎所有人的做法答案字符串长度都是极限 \ge 4\log n（包括官方题解），但自己的是 3\log n，因此决定写一篇题解。（为自己点赞）

首先我们很容易发现，若 n 为 2 的次幂，则直接一直重复输出 LR 即可。我们还很容易发现，当连续的 L 的数量大于 1 时，再用一次 L 就相当于把 a_2 与 a_4 更换位置，那么也就意味着连续的 L 数量大于 2 时就没有意义。

我们尝试找规律。

举个例子，先以 n=16 为基础，然后添加 L 或 R 得到其他答案。

``` 0 LLRLRLRLRLR 1 LLRLRLRLLRLLR LLRLRLRLRLLR 2 LLRLRLLRLLRLR LLRLRLRLLRLR 3 LLRLRLLRLLRLLR LLRLRLLRLRLLR 4 LLRLLRLLRLRLR LLRLRLLRLRLR 5 LLRLLRLLRLLRLLR LLRLLRLLRLRLLR 6 LLRLLRLRLLRLR LLRLLRLLRLLRLR 7 LLRLLRLRLRLLR LLRLLRLRLLRLLR 8 LRLLRLRLRLR LLRLLRLRLRLR 9 LRLLRLRLLRLLR LRLLRLRLRLLR 10 LRLLRLRLLRLR LRLLRLLRLLRLR 11 LRLLRLLRLLRLLR LRLLRLLRLRLLR 12 LRLRLLRLRLR LRLLRLLRLRLR 13 LRLRLLRLLRLLR LRLRLLRLRLLR 14 LRLRLLRLLRLR LRLRLRLLRLR 15 LRLRLRLLRLLR LRLRLRLRLLR ``` 可以发现对于每个字符串我们可以分成五组，每组要么是 `LLR`，要么是 `LR`。每个答案的两种情况不一定有一定的规律，接下来以便寻找规律，我们进行调整并将多余的删除以及对齐每组： ``` 0 LLR LR LR LR LR 1 LLR LR LR LLR LLR 2 LLR LR LLR LLR LR 3 LLR LR LLR LR LLR 4 LLR LLR LLR LR LR 5 LLR LLR LLR LLR LLR 6 LLR LLR LR LLR LR 7 LLR LLR LR LR LLR 8 LR LLR LR LR LR 9 LR LLR LR LLR LLR 10 LR LLR LLR LLR LR 11 LR LLR LLR LR LLR 12 LR LR LLR LR LR 13 LR LR LLR LLR LLR 14 LR LR LR LLR LR 15 LR LR LR LR LLR ``` 对于前 $i$ 组都是 `LLR` 的： $i=1$：$0\sim 7 i=2$：$4\sim 7 i=3$：$4\sim 5 i=4$：$5\sim 5

可以发现，i=1 与 i=3 都是取了 i-1 的前半段，i=2 与 i=4 都是取了 i-1 的后半段，然而对于 8\sim 15 的第 2 组取的却是前半段，所以我们可以猜测：若这一组是 LLR，则下一组取的与这一组取的相反（即若这一组是取前半段，则下一组取后半段，若这一组取后半段，则下一组取前半段）；若这一组是 LR，则下一组取的与这一组取的相同。

枚举其他答案，发现符合猜想，我们直接找到最大的 2 的次幂替换 16 即可得到所有答案，该思路显然可用二进制实现，取前半段即 2 进制下该位为 0，取后半段即 2 进制下该位为 1。代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool a[31];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    n*=2;
    for(int i=0;i<=30;i++)
    {
        a[i]=n&1;n>>=1;
    }
    int e=0;
    for(int i=30;i>=0;i--)
    {
        if(a[i]==e)
        {
            cout<<"LLR";
            e=!e;
        }
        else
        {
            cout<<"LR";
        }
    }
    return 0;
}

爆标了，难评。