在公元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$个//+子序列