分数: 400 点
问题陈述
给你一个正整数 N 和一个序列 A=(A_1,A_2,\dots,A_N) 长度 N,包括 0 和 1.
我们称一个字符串 S 长度 N,仅由大写英文字母组成,a 好字符串 如果可以执行以下操作任意次数(可能为零),以便序列 A 不包含 0。在这里, S_i (1\leq i\leq N) 表示 i- 第一个字符 S,我们定义 S_{N+1}=S_1, S_{N+2}=S_2,和 A_{N+1}=A_1.
- 执行以下操作之一:
- 选择一个整数 i 与 1\leq i\leq N 这样 S_i=
A, S_{i+1}=R,和 S_{i+2}=C,并替换每个 A_i 和 A_{i+1} 与 1. - 选择一个整数 i 与 1\leq i\leq N 这样 S_{i+2}=
A, S_{i+1}=R,和 S_i=C,并替换每个 A_i 和 A_{i+1} 与 1.
- 选择一个整数 i 与 1\leq i\leq N 这样 S_i=
判断是否存在好的字符串。
约束
- 3\leq N\leq 200000
- A_i\in \lbrace 0,1 \rbrace (1\leq i\leq N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N
输出
如果存在好的字符串,则打印 Yes;否则,打印 No.
法官不区分大小写;例如,如果正确答案是 Yes,输出如 yes, YES,或 yEs 也将被接受。
示例输入 1
12 0 1 0 1 1 1 1 0 1 1 1 0
示例输出 1
Yes
例如, RARCARCCRAGC 是一个很好的字符串。这是因为可以更改的所有元素 A to 1 通过执行以下操作:
- 最初, A=(0,1,0,1,1,1,1,0,1,1,1,0).
- 执行第一个操作 i=2。然后, A=(0,1,1,1,1,1,1,0,1,1,1,0).
- 执行第一个操作 i=5。然后, A=(0,1,1,1,1,1,1,0,1,1,1,0).
- 执行第二个操作 i=8。然后, A=(0,1,1,1,1,1,1,1,1,1,1,0).
- 执行第二个操作 i=12。然后, A=(1,1,1,1,1,1,1,1,1,1,1,1).
由于存在好的字符串,因此输出 Yes.
示例输入 2
3 0 0 0
示例输出 2
No
好的字符串不存在。
示例输入 3
29 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
示例输出 3
Yes
自从 A 已不包含 0,每个长度的字符串 29 由大写英文字母组成是一个好的字符串。