在公元3202
年的BJTU算法竞赛中,有一道构造题
rankYu 发现了$n$ 个高能粒子,他可以有两种操作:
- 1 所有粒子能量值 $+1$。
- 2 所有 能量值为偶数 的粒子能量值变为原来的 $\frac{1}{2}$。
请构造一个操作序列把所有粒子的能量值变成相同。
+
表示 $1$ 操作,/
表示 $2$ 操作,!
表示操作结束。最多可以操作 $200$ 次。
这道题的答案(python)也十分简单:
print("//+"*66+"!")
但是这道题的通过率不甚理想,所以rankYu打算重新审视每个人的输出,如果满足以下两个条件即为通过:
!
结尾。//+
子序列。字符串的子序列指的是删除部分字符(可以为空)后剩余的字符串,比如bjtuacm
的子串包括bm
,juac
,但是不包括ab
,cc
,f
,不同的删除下标代表不同的子序列。
第一行一个整数$n,1\le n \le 200$代表字符串长度
第二行为一个字符串$s$,保证$s$只有/+!
三种字符
YES
代表字符串符合上文中的两个条件,NO
反之
字符串包含$1$个!
,$10$个/
,$10$个+
,$1$个!
,一共$C_{10}^2\times 10 = 450$个//+
子序列