题解：P12335 真真随机

发现几乎所有人的做法答案字符串长度都是极限

\ge 4\log n

（包括官方题解），但自己的是

3\log n

，因此决定写一篇题解。~~（为自己点赞）~~

首先我们很容易发现，若

n

为

2

的次幂，则直接一直重复输出 LR 即可。我们还很容易发现，当连续的 L 的数量大于

1

时，再用一次 L 就相当于把

a_2

与

a_4

更换位置，那么也就意味着连续的 L 数量大于

2

时就没有意义。

我们尝试找规律。

举个例子，先以

n=16

为基础，然后添加 L 或 R 得到其他答案。

n=16

时，按照上述所说，答案为 LRLRLRLRLR，枚举一下会发现无论怎么添加 L，答案都不会大于

16

，然而按照上述所说，我们最多是只能添加

5

个 L 的，因此我们枚举所有情况（每个位置都有放与不放，因此一共是

2^5

种情况），得到下表：（每个答案的两种情况不一定有一定的规律，需自己进行调整以便寻找规律）

CPP

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。每个答案的两种情况不一定有一定的规律，接下来以便寻找规律，我们进行调整并将多余的删除以及对齐每组：

CPP

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

。代码如下：

CPP

#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;
}

爆标了，难评。

题解：P12335 真真随机

文章操作

相关推荐

评论

题解：P12335 真真随机