夏晓光(loveJY)的博客

IOI2021....试题

177

$f_{l,r}$表示$[l,r]$区间的外星人被干掉最小代价

显然我们可以考虑转移枚举断点,一定能分开的点.....

即杀掉那个最大的外星人的时间段上选点

$f_{l,r}=min(f_{l,mid-1},f_{mid+1,r});$

就能把区间划分为两端了

251

注意到一个胜利局面一定是先增加后减少

所以说我们可以记$f_{l,S}$表示前l个数,然后递增部分的和为S(一直包括到最大值)是否可以

递减部分一定就是$sum_l-S$了....

然后转移考虑第l+1个数分到左边还是右边

如果放到左边,2048一波....(其实直接+上长度即可)

如果放到右边,我们只需要考虑那个最大值要不要变大即可

最后如果$f_{n,\sum}$可以就行...

222

$2^a+2^b+2^c+2^d$

d是最大的

d+3步可以都消掉...显然...

就是不断除2然后拿1

但是$2^a+2^b+2^c$最优c+2

然后我们手玩第二个样例,就能造出4个1更优的b+2次??

同样的,我们可以发现他会是一条树的右链

如果右链拿出来,其实就是一个加法链

$a_1=1$

$a_2=2$

$a_n=a_n+a_{x}$

$x<n$

显然$a_n$的另一个加项一定会在右链某个位置被带走

最短的加法链使$a_n=2^a+2^b+2^c+2^d$

次数一定是$d+2$或者$d+3$

$d+2$次操作如果可以,那一定凑出的数大于$2^d$

$A-B=C-D$

$A-B=C-D+1$

$A-B=3 ,C-D=1$

$A-B=5,B-C=C-D=1$

只有这4种情况d+2其他的都是d+3吧

所以分类讨论即可

当然我们也可以搜搜搜,但是要加上一个剪枝,就是位置为i的值大等于$2^{d-2}$

详情参照

228. 基础数据结构练习题

这个和之前那个好像没得啥区别哦

但是会发现开根号没法维护标记列

于是我们考虑经典的维护区间最大最小值,然后看什么时候这个区间能变成一个数

1. 当最大值等于最小值,为区间减法

这个显然吧,所有数都一样了

2. 最大值等于最小值+1,而且最大数为一个平方数时,也就是说$sqrt(min)+1=sqrt(max)$

这个时候也能区间减吧,比方说333444,可以区间减2

正确性就是如果暴力递归我们会变成11112222,然后+2还原了33334444,然后人没了啊

3. 否则,暴力递归

最多loglog次,一个数就变成了1