xjoi模拟赛43

t1:
观察到操作之和左右的端点有关,于是我们就可以分别开两颗线段树维护端点的位置

查询的时候也就是tree_l(1,r)-tree_r(1,l-1)

复杂度O(nlogn)

.

当时非常naive 的用一颗线段树维护了区间的修改以及最大值,手推几种样例就可以轻松的被hack掉

~~论打暴力的必要性~~

t2

类似01背包的做法,只不过维护每一个状态的前k优值,转移也是类似二路归并行了

vector会t掉,我写了一个~~启发式合并~~的set,然后打萎并且被卡常数了

复杂度O(NKV)

.

t3:神奇的背包

首先对于每一个物品求出他的价值

于是我们可以定义一个状态g[i][j]表示对于第i个节点,他用了j次魔法对于买一次这个物品的最小的费用

g[i][j]的求解可以通过他子树的状态跑一边背包得到

然后我们再设f[i][j]表示用了i次魔法体积为j的最大获得的价值

再对f[i][j]跑一边背包

于是我们就在O(K^{2}VN)解决了这个问题

论灵活利用背包的重要性.

.

今天真的要爆0了啊,~~还要c题puts("0")有10分~~..

主要还是没有打好对拍啊,以后看题慢一些,尽量打好对拍,能做的题不能丢

今天丢了200pts gg

发表评论

电子邮件地址不会被公开。 必填项已用*标注