第十五届蓝桥杯省赛PythonB组E题【蓝桥村的真相】题解（AC）_蓝桥杯15届校赛b组真题解答

题意分析

下文中 $1$ 表示真，$0$ 表示假。

• 由于 $1$ 是真话，所以 $1$ 的背后一定为 $01$ 或者 $10$。
• 由于 $0$ 是假话，所以 $0$ 的背后一定为 $00$ 或者 $11$。

故题目的意思为，构造长度为 $n$ 的 $01$ 字符串，有多少个字符串中的所有字符满足上述条件。

---

假设一个字符串 $s$ 的第一位为 $1$：

根据上述规则，我们先讨论这个 $1$ 背后接着 $01$，那么字符串为：

101
1

第二位为 $0$，且 $0$ 的背后一定为 $00$ 或者 $11$，且第三位为 $1$，所以第四位一定为 $1$，字符串变为：

1011
1

同理：

10110
1

101101
1

1011011
1

...
1

由于字符串首尾相接，当出现 $n=4,5,7,8,\dots$ 时，最后一个字符不符合构造条件。

综上，当 $n\%3=0$ 时，循环节为 101，每 $3$ 位中必存在一个 $0$，答案加上 $n/3$。

---

---

接下来我们讨论，当第一位为 $1$ 时，后头接着 $10$ 的情况。

110
1

第二位为 $1$，且 $1$ 的背后一定为 $01$ 或者 $10$，且第三位为 $0$，所以第四位一定为 $1$，字符串变为：

1101
1

同理：

11011
1

110110
1

1101101
1

...
1

由于字符串首尾相接，当出现 $n=4,5,7,8,\dots$ 时，最后一个字符不符合构造条件。

综上，当 $n\%3=0$ 时，循环节为 110，每 $3$ 位中必存在一个 $0$，答案加上 $n/3$。

---

---

假设一个字符串 $s$ 的第一位为 $0$：

根据上述规则，我们先讨论这个 $0$ 背后接着 $11$，那么字符串为：

011
1

第二位为 $1$，且 $1$ 的背后一定为 $01$ 或者 $10$，且第三位为 $1$，所以第四位一定为 $0$，字符串变为：

0110
1

同理：

01101
1

011011
1

0110110
1

...
1

由于字符串首尾相接，当出现 $n=4,5,7,8,\dots$ 时，最后一个字符不符合构造条件。

综上，当 $n\%3=0$ 时，循环节为 011，每 $3$ 位中必存在一个 $0$，答案加上 $n/3$。

---

---

接下来我们讨论，当第一位为 $0$ 时，后头接着 $00$ 的情况。

000
1

第二位为 $0$，且 $0$ 的背后一定为 $00$ 或者 $11$，且第三位为 $0$，所以第四位一定为 $0$，字符串变为：

0000
1

同理：

00000
1

000000
1

0000000
1

...
1

无论 $n$ 为多少均存在答案，答案加上 $n$。

---

总结

综上所述，当 $n\%3=0$ 时，上述四种情况答案之和为：

$$\frac{n}{3}+\frac{n}{3}+\frac{n}{3}+n$$

化简得 $2n$。

当 $n\%3\ne 0$ 时，上述仅有第四种情况存在答案，故答案为 $n$。

【在线测评】

import sys
sys.setrecursionlimit(1000000)
input = lambda:sys.stdin.readline().strip()

T = int(input())
for _ in range(T):
    n = int(input())
    if n % 3 == 0:
    	print(2 * n)
    else:
    	print(n)
1
2
3
4
5
6
7
8
9
10
11

【在线测评】