xy0v0's Blog

Back

做法#

容易发现的是:

  • 若给定集合 {p1,p2,⋯ ,pn}\{p_1,p_2,\cdots,p_n\} ,那么当 pi=pi+1p_i=p_{i+1} 且 pi+pi+1=ip_i+p_{i+1}=i 时方案数可翻倍。(开头必然有两种)
  • 若集合合法,则必须满足:
    1. pi<ip_i < i
    2. pi+pi+1=ip_i + p_{i+1} = i 或 pi=pi+1p_i = p_{i+1}

考虑对集合的构造,构造到第 ii 位时,前缀若有 AA 个 1, BB 个 0, 记 x=min⁡(A,B),y=max⁡(A,B)x=\min (A,B),y=\max(A,B) ,可得到以下:

条件消耗的值新状态x<y, cnt⁡[x]>0x(x,y+1)x<y, cnt⁡[x]=0y(x+1,y)x=yx(x,y+1)\begin{array}{c|c|c} \text{条件}&\text{消耗的值}&\text{新状态}\\ \hline x<y,\ \operatorname{cnt}[x]>0 & x &(x,y+1)\\ x<y,\ \operatorname{cnt}[x]=0 & y &(x+1,y)\\ x=y & x &(x,y+1) \end{array}

这里在 x<yx<y 且 cnt[x]cnt[x] 正时必须选择 xx ,因为如果此时消耗 yy ,那么新状态为 (x+1,y)(x+1,y) ,永远不可能选择到 xx

代码#

补题 | ICPC EC 线上一 D

https://www.xy0v0.top/blog/icpcecol-d
Author xy0v0 Published at Copyright CC BY-NC-SA 4.0