CF1265

$Div.2$

如果有两个相邻字母相同,则肯定无解.

否则,每次用合适的方法填好连续的一段问号就可以了.

考虑从大到小加入每个数,如果在加入第 $i$ 个数后,加入的数的位置形成了一段连续的区间,则第 $i$ 个答案为 $1$ .

记录一下加入的数中,最左边的位置 $L$ 和最右边的位置 $R$ ,若 $R-L+1=i$ ,则是连续的区间.

把同一种分数的所有人看成一个数,数字大小为这些人的个数.

从大到小枚举有多少个人有奖牌,检验是否有合法解.

在有奖牌的人中,至少要有 $3$ 种分数,取分数最高的那些人获得金牌,二分出多少人得银牌时,金牌数小于银牌数.

剩下的就是铜牌,再检验一下金牌数是否小于铜牌数.

$0$ 只能和 $1$ 相邻, $3$ 只能和 $2$ 相邻.

所以当 $0$ 的数目比 $1$ 多时,答案只可能是 $010101\dots010$ 的形式,否则无解, $3$ 与 $2$ 同理.

否则,可以在开头放下一段 $0101\dots 01$ ,在末尾放下一段 $23\dots2323$ .

此时还剩下若干个 $1$ 和若干个 $2$ 没有放.

若两者数目相同,就直接在中间放下 $2121\dots21$ .

若 $1$ 的数目比 $2$ 的数目多 $1$ ,就在最开头放个 $1$ ,中间放下 $2121\dots21$ .

若 $2$ 的数目比 $1$ 的数目多 $1$ ,就在最后放个 $2$ ,中间放下 $2121\dots21$ .

其余情况无解.

设 $E(i)$ 表示当前应该去问第 $i$ 面镜子时,期望的天数.

边界有 $E(n+1)=0$ ,转移有 $E(i)=\frac{p_i}{100}E(i+1)+\frac{100-p_i}{100} E(1)+1$ .

从前往后推出每个 $E(i)=k_i\cdot E_1+b_i$ ,再根据 $E(n+1)=0$ 解出 $E_1$ .

考虑给出一个括号序列时,怎样计算它的深度.

如果最左边是 ) ,就把它删掉.

如果最右边是 ( ,就把它删掉.

如果最左边是 ( ,最右边是 ) ,就把它们同时删掉,并且让深度 $+1$ .

设 $f(i,j)$ 表示 $[i,j]$ 这段括号序列对答案的贡献,根据这个过程来 $dp$ 即可.