好题

  • 2014Beijing-Onsite F (概率dp)
  • CF361 D (一类滑窗问题)
  • atcoder-arc058-e
    一个由1-10组成的长度为n的序列,求中间存在连续的三段,和分别为 X,Y,Z,的序列(X <= 5,Y <= 7,Z <= 5)
    学习了一种新的表示法,分别用 1 10 100 … 表示 1 2 3 …
    这样如果他们的和为x,则第x位上也为1
    由于x+y+z <= 17,所以最多也只有17位,这样就可以dp了
    $d_{i,msk}$ 表示前位,当前序列为msk的序列个数
    用一个特殊状态表示当前状态已经符合条件(比如 1<<(x+y+z))
    $d_{i+1,msk<<p | 1<<(p-1)} = \sum d_{i,msk} \;\; 1 \leq p \leq 10$
    $d_{i+1,1<<(x+y+z)} = \sum d_{i,1<<(x+y+z)} \;\; if (msk \& 1<<(x-1)) and (msk \& 1<<(x+y-1)) and (msk \& (1<<(x+y+z-1))$
  • atcoder-agc005-d

思维