CF1480

2021-02-09 约 699 字预计阅读 2 分钟

easy problem

考虑英雄被击杀的次数时固定的, 只有最后一次击杀不算, 所以把那次击杀放在最后

考虑二分, 如果 a[mid]>a[mid+1] 则在$mid\to r$中间必有一个点否则在$l\to mid$中间必有一个点

很容易看出一个$\mathcal O(n^2)$的dp 计$f_{j}$表示现在两个颜色分别为 a[i] 和 j 的最长长度, 然后就可以转移了这时我们又可以发现一个性质既如果$f_i>f_j$则$f_j$一定无用然后就可以用set转移了

只需将D1的取最大改为取最小即可

首先一定有解

如果$l=1,r=2^k$的话则构造$k+2$个点首先数归即可得到由$k+1$个点的图,然后$k+1$向$k+2$连一条为1的边,1向$k+2$连一条为1的边,$i\in {2,k+1}$向k+3连一条$2^{k-1}$的边
如果$l\neq 1$则做一遍$(1,r-l+1)$终止节点向终止节点+1连一条为$l-1$ 的边
如果$r\neq 2^k$则记$r−1=\sum_{i=0}^kR_i\times2^i$为r-1的二进制展开$R_i\in {0, 1}$先做一遍(1, 2^k)新建一个点$k+3$, 1向$k+3$连一条为1的边, 接着对于$0\leq i\leq k$的每一个i, 如果$R_i=1$i+2向 k+3连一条 $1+\sum^k_{j=i+1}R_j\times2^j$的边

一开场两分钟秒了A, B想了一个假算法, Wa了两次, 才意识到错误, 然后一直没有头绪, 突然想出了算法, 因为没有考虑边界情况Wa了3发, 然后rk升到了14 然后无意中看到uoj群中的讨论, 会了C写了一发过了, rk升到了8(结果fst了)然后E一直想不出来一步. 看来水平还是又提升的空间

目录