杂题 ·

241017模拟

题目
此处内容需要 才可见

好几天不更了= =

T1 Star Way To Heaven

一眼二分,再看看就可以发现直接找上下边界即可。但是考试时不仅被卡了常数,还被爆了int。。。正确的方法是并查集合并,每次合并后检查合法情况,可以剪枝。

 

T2 God Knows

先来想暴力DP。我们规定i为下标,p[i]为权值,那么设f[i]:选了下标为i的线段,同时下标在它前面的线段均已被覆盖的最优解。那么,既然我选了当前点,上一个转移点就一定不能与当前点发生交叉,同时两个点之间还不能遗漏任何位置,也就是说,合法转移点的下标小于当前点,权值小于当前点,而且,为了保证能把中间的都盖住,还必须保证越靠前的转移点权值越大。这样,暴力DP就可以搞了,直接找小于当前点的权值的上升序列中的元素的f值最小值即可(好拗口)。

考虑用数据结构搞这个东西。大家都打的线段树,但是我不想搞得这么麻烦,于是来尝试分块做法。考虑到我们每次只需要查询一个前缀上的最长上升序列,那么我们可以在每个块维护从右往左的上升序列,查询时先在小块内暴力跳,记录上升序列最大权值和最小f值,遇到大块二分跳到的位置即可。修改时小块暴力,维护用来二分的几个信息即可。

代码很乱。

 

T3 Lost My Music

考试的时候一直在想一些奇怪的方法优化,但是并没有想到正解,无奈打了50分暴力。对式子取相反数,发现是斜率的形式。我们要求的是最大斜率,所以可以动态维护下凸壳,同时由于下凸壳的单调性,我们可以二分栈顶的位置。由于每次只会修改一个元素,所以我们可以在DFS回溯时轻松搞定。

 

参与评论