讨论 比赛 【题解&答疑】Contest #14 C 题《序列》

【题解&答疑】Contest #14 C 题《序列》 比赛:Comet OJ - Contest #14

题目链接

C.序列

出题人

$\color{orange}{Ynoi}$

题解

定义$f_x$表示所有序列中,存在极大连续段右端点为$x$的序列个数

我们知道如果一个序列$a$有$x = n或a_x \not= a_{x+1}$,则会对$f_x$产生$1$的贡献

由于每次操作我们复制后,对$l$到$r$赋值一个新的数

所以所有序列下标为$r$的值一定和下标为$r+1$的值不同,所以此时$f_r = f_r(复制后不操作)+2^{i-1}(所有复制后都操作的序列)$

同理, 下标$l-1$的值和下标$l$的值不同,所以$f_{l-1} = f_{l-1}+2^{i-1}$

对于所有$l \leq x <r$,此时由于$l$~$r$被赋了同样的值,所以此时操作后的序列都不对$f_x$ 产生贡献,所以此时$f_x$只有复制后没有操作的部分,$f_x = f_{x}$

对于所有$x <l-1或x >r$,是否执行赋值操作对$f_x$没有影响,由于被复制了两份,$f_x = 2f_{x}$

AC 代码参考

lok666 发起于2019-11-8 22:19:23 收起
分享
举报
删除
共0条回复
最新
成为第一个回复讨论的人吧~
全屏