首页 > 代码库 > jzyz集训 0611

jzyz集训 0611

  今天jjh和mzx搞的互测题目有必要记录一下。

  T1:序列上可以放012三种颜色,有m个限制表示[l,r]区间的颜色数目必须是c,求方案数。

  显然的DP,但关键是状态怎么设置,连续设置了n个状态都被自己推翻后gg。

  正解其实也比较容易想到,颜色数这种东西状态还是记录上一次出现的位置比较好做...想到了颜色为什么没想到链表呢?可能做的这种类型的DP比较少吧。

  T2:m个操作,第i次操作将i在[l,r)这个区间每个位置各放一份,问放完后本质不同的序列第K大的位置。

  恩...想到了类似正解的方法,但没有想到线段树。

  正解的话,按照放区间的顺序,再通过线段树01覆盖,然后根据K,可以确定答案位置一定在或不在这个区间里,然后就没了。

  本质不同可以这么解决:利用hash来判断两位置的终状态是否一样,一样的话随便设一个在线段树里的初值为1。

  hash可以搞多项式hash(区间*+标记乱搞),或者每个i随机一个hash值,利用hash的xor搞差分。

  T3:n个点,每个点有1/2概率黑,1/2概率红,问所有方案的黑点的凸包上的点的数目和。

  把枚举点变成枚举边,然后概率乱搞。

  想到了正解,但是知道该怎么解决重点,3点1线的情况。十分蛋疼。

  调了n久过不去,弃了。

  

jzyz集训 0611