luogu P11003蓝桥村的真相 题解

题目链接：P11003 [蓝桥杯 2024 省 Python B] 蓝桥村的真相

这题一看数据范围 \(n\leq 10^{18}\) 就知道暴力会超时，所以这题一定有规律可循。

找规律：（以下 1 代表 true，0 代表 false）

题意：

当一个人为 \(1\) 时，后面两个人只能为 \(01\) 或 \(10\)。

当一个人为 \(0\) 时，后面两个人只能为 \(00\) 或 \(11\)​。

第一位为 1

接 01

字符串变为 \(101\)，第二位为 \(0\)，且 \(0\) 之后一定为 \(00\) 或者 \(11\)，且第三位为 \(1\)，所以第四位一定为 \(1\)，字符串变 为：\(1011\)。

依此规律向下推，依次为 \(10110\)，\(101101\)，\(1011011\)，\(10110110\)。

可见一直出现 \(101\)，即当 \(n\) 整除 \(3\) 时，每三位中都出现一次假，总共有 \(\frac{n}{3}\) 个假，答案加上 \(\frac{n}{3}\)。

接 10

依次推理，为 \(110\)，\(1101\)，\(11011\)，\(110110\)，\(1101101\)，\(11011011\)​。

可见一直出现 \(110\)，即当 \(n\) 整除 \(3\) 时，每三位中都出现一次假，总共有 \(\frac{n}{3}\) 个假，答案再加上 \(\frac{n}{3}\)。

第一位为 0

接 11

也不难得到 \(011\)，\(0110\)，\(01101\)，\(011011\)，\(0110110\)，\(01101101\)​。

可见一直出现 \(011\)，即当 \(n\) 整除 \(3\) 时，每三位中都出现一次假，总共有 \(\frac{n}{3}\) 个假，答案再加上 \(\frac{n}{3}\)。

接 00

分别得到 \(000\)，\(0000\)，\(00000\)，\(000000\)，\(0000000\)，\(00000000\)。

无论 \(n\) 为几，都出现 \(n\) 次假，答案加上 \(n\)。

总结

当 \(n\) 整除 \(3\) 时，答案为

$$
\frac{n}{3}+\frac{n}{3}+\frac{n}{3}+n=2\times n
$$

当 \(n\) 不整除 \(3\) 时，答案就为 \(n\)，即 \(n\) 个假相接。

代码：

c++

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline void solve()
{
	int n;
	cin>>n;
	cout<<(!(n%3)?(n*2):n)<<endl;
}
signed main() 
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

介于是 Python 组的题目，也放一下 Python 代码

Python

t=int(input())
for _ in range(t):
    n=int(input())
    if n%3==0:
        print(n*2)
    else:
        print(n)