Hdu暑期多校训练6

来自PC Wiki
跳到导航 跳到搜索

Records

[Contest]

Solutions

A

考虑这显然是一个最小割模型

$$S->$$树上结点$$->$$相机$$->T$$

树上结点到相机为$$INF$$,$$S$$到树为苹果价值,相机到$$T$$为毁坏相机的代价

然后考虑答案就是$$\sum{a_i}-mincut(S,T)$$

这个最小割直接建图显然GG,考虑用一些其他方法模拟网络流

考虑将最小割转化成最大流

然后对于树的每一个结点,我们考虑维护一个map,$$f(u,i)$$表示到$$u$$这个结点,然后在他的子树内$$j$$深度处的流量还有多少

我们考虑贪心地流完这个流量:

1.如果当前能流走,那么一定流走

2.每次流的时候,尽可能从距离较远的地方流

然后这个东西我们提前把需要处理的相机挂在对应子树根上就行了

然后对于子树没用完的流量,我们启发式合并map

这个东西看上去是两个$$\log$$的

但是可以用类似长链剖分的分析方法,发现是一个$$\log$$的

所以复杂度$$O((n+m) \log n)$$

B

倒着做,由于数据随机所以LIS长度是$$O(\sqrt n)$$级别的

每次暴力找出一个LIS,然后如果删除的点不在LIS上那就答案不变,否则暴力重构

复杂度$$O(n\sqrt n \log n)$$

C

考虑用图模型来描述这个问题,每个点表示$$x_i$$的前缀和

然后我们每购买一条限制就是连一条$$(l-1,r)$$的无向边

如果图连通就是能问出答案

然后我们连完所有边之后考虑删掉一些边,这样就是最大化删掉的边集合的权值

考虑删掉的边集对所有边全部连上的图的补图是留下的边的集合

那么要求补图连通,这等价于补图中存在生成树,而生成树是图拟阵的基,所以补图的连通性满足拟阵性质,记为$$M_1$$

然后从每个集合里删的边是有限制的,这个形成一个划分拟阵$$M_2$$

然后就是带权拟阵交

将每个拟阵中的边$$x$$建一个点,再建一个源$$S$$和一个汇$$T$$

然后如果$$x$$在当前答案集合中,则点权为$$-w_i$$,表示反悔的代价

否则答案就是$$w_i$$,表示选择的收益

然后不在当前答案集合中,那么如果答案集合$$I$$中加入$$x$$满足$$M_1$$,那么连边$$S->x$$,如果加入$$x$$后满足$$M_2$$,那么连边$$x->T$$

然后就是考虑交换两部分的元素的情况

如果$$x$$在$$I$$中,$$y$$不在$$I$$中:

如果$$I$$去掉$$x$$加入$$y$$满足$$M_1$$,那么$$x->y$$连边

如果$$I$$去掉$$x$$加入$$y$$满足$$M_2$$,那么$$y->x$$连边

然后因为需要最大化删除的边的权值,所以跑最长路

然后沿着最长路增广,选择状态取反

这样如果能增广的话答案一定比原来大$$1$$

那么增广$$\sum{(c_i-k_i)}$$次即可

如果开始图就不连通或者增广不到这个次数,那么就是无解

D

显然有一个结论,两边时间相等最优

考虑按$$\frac{a_i}{b_i}$$排序,每次一定是将$$\frac{a_i}{b_i}$$较小的给A,较大的给B

那么对于排好序的情况,一定是A取了一段前缀,B取了一段后缀,然后中间分界点的那个一部分给A,一部分给B,这个可以利用时间相等解方程求出来

现在动态加入就是利用树状数组维护A的前缀和和B的后缀和

每次二分分界点然后树状数组求值

复杂度$$O(n \log ^2 n)$$,常数较小

E

考虑枚举上边界,下边界向下推

只有$$O(n)$$个需要更新的关键点

线段树维护动态最大子段和

F

考虑每个式子的两个绝对值取正/负,一个式子相当于划分了四个象限,暴力枚举取哪个象限从而确定x,y的取值范围

这样做方案数表面上$$O(4^n)$$但实际上有效状态只有$$O(n^2)$$

确定取值范围后我们得到了n个未知数为x+y和x-y的同余方程组,此处并不用CRT,而是直接考虑枚举x,y,代入方程组观察是否合法即可

同时注意到模数只有2,3,4,5,所以60为一个循环节,x,y只用在0~59之间枚举然后计数即可

复杂度$$O(60^2n^3)$$

G

考虑二分答案,然后每个球半径加上$$\frac{mid}{2}$$,变成判定是否有$$k$$个球相交

当前球的最大半径为$$R$$时,考虑将三维空间划分成边长为$$2R$$的立方体网格

然后考虑一个球的球心处于某个网格中,那么只有周围$$27$$个格子的球才可能与他相交

那么我们检查这些格子中的球心与该球是否相交

若一个格子中有$$O(\sqrt{k})$$个球,那么一定存在$$k$$对球相交

那么我们在检查出$$k$$对相交球之后就结束,复杂度是$$O(n \sqrt k)$$的

但是现在球的半径变小的时候这个性质并不成立

那么我们考虑按半径从大往小枚举球,当半径小于之前网格边长的$$\frac{1}{4}$$时重构网格

这样重构次数最多$$O(\log w)$$次 ($$w$$为值域)

然后复杂度就是$$O(n (\sqrt{k}+\log w)\log w)$$的

H

枚举$$f(n,m)-n$$,暴力

I

不带权$$k$$个不相交LIS的我们有一个经典的杨表做法:

维护$$k$$层杨表

像维护单调栈求LIS那样(其实那个就是一个一层杨表),每次新插入一个数字,如果大于等于当前层最大数就直接插进去

否则插入到对应位置,然后找出大于他的第一个值,把这个值塞进下一层

现在要解决带权问题,显而易见的一个思路是把权为$$w$$的值拆成$$w$$个$$w$$

套用上面方法可以完成

但是拆完之后总数不能保证,因此我们需要map维护出现次数

这个东西每次最多导致一个颜色段一分为二,就是递归下去的插入次数翻倍

那么复杂度就是$$O(2^k n \log n)$$

J

如果是一个有根树,那么可以考虑树上依赖背包

这个背包是带权背包,可以转成括号序列DP来$$O(1)$$转移避免卷积合并过程

然后发现这个权值是乘起来的,所以$$\lfloor{\frac{m}{j}}\rfloor在$$$$ j \geq \sqrt{m}$$只有$$O(\sqrt{m})$$种取值

然后分成大于和小于等于$$\sqrt{m}$$两种情况DP,转移一下,状态数$$O(n\sqrt{m})$$

然后无根树转有根树套一层点分治

复杂度$$O(n\sqrt{m}\log{n})$$

K

考虑方案数可以用DP求出:

$$dp[i][j]$$表示前$$i-1$$位$$\bmod m$$的和为$$j$$,然后$$[i,n]$$中有多少种填法可以使整个串$$\bmod m$$的和为$$0$$

然后转移是$$dp[i][j] = \sum{dp[i+1][(10*j+k) \bmod m]}$$,其中$$k$$为第$$i$$为能填的数

$$dp[n+1][0]=1$$,向前递推,$$dp[1][0]$$为方案数

然后现在要求第$$k$$小的方案数

有一种暴力做法就是在这个DAG上贪心,预处理后继的方案数范围(min和max),枚举后继,然后在DAG上一位一位找

这样复杂度会爆炸

这时候需要用一些技巧,在DAG上轻重链剖分

对于每个点,他的后继中方案数最大的为重后继,否则为轻后继

走一个轻后继方案数减半,最多跳$$O(\log n)$$次

因此倍增预处理重后继即可

每次倍增跳重链,然后暴力跳轻链

复杂度$$O(nm \log n + n \log n \log k)$$

L

签到题