竞赛讨论区 > 牛客练习赛40题解
头像
咕咕咕_
编辑于 2019-11-29 20:23
+ 关注

牛客练习赛40题解

2019-05-04 UPD:见评论


鸣谢验题人 @IMH 指出数据错误和给出D题的另一种做法

欢迎dalao交流做法


牛客练习赛40题解

题解仅供参考,如果您有其他做法,欢迎交流讨论

小D的剧场

图片说明 表示目前序列放入到第 图片说明 位,最后两个数字为 图片说明 时的方案数,提前将不合法的子段标记

转移方程为

图片说明

can为 图片说明 表示不合法, 图片说明 表示合法。

时间复杂度 图片说明

小A与任务

以完成时间为关键字从小到大排序(可以交换两个完成时间不同的任务来证明这样的正确性),按这个顺序来做任务,同时维护一个关于 图片说明 的大根堆,如果规定时间内完不成任务,就从堆里取出 图片说明 最大的任务来花费金币,维护每个任务的剩余时间,如果花费金币后剩余时间不为 0 则重新push入堆

复杂度 O(nlogn)

小A与欧拉路

先考虑回路的情况。由于是一棵树,任两点间路径只有一条,从一条边走到深度更大的点,一定还会从同一条边返回以回到起点或者遍历其他子树,所以每条边需要复制一次,此时答案是边权和的两倍。

不是回路的情况可以减掉从终点回到起点的路径,要让这条路径尽量长,所以长度一定是直径的长度。

答案就是边权和的两倍减去直径长度。

求直径可以树形DP或者BFS/DFS两次

复杂度 图片说明

小A与最大子段和

似乎好多人被题面误导了

图片说明

表示以 图片说明 为右端点的 “最大子段和”,假设左端点为 图片说明

图片说明
可得 图片说明 ,可以使用斜率优化

希望最大化截距,且横坐标 图片说明 单调,斜率 图片说明 不单调,所以用单调栈维护凸壳,在凸壳上三分DP值/二分斜率

另有一种 图片说明 单调,图片说明 不单调的推法(鸣谢验题人)

图片说明 表示以 图片说明 为左端点的"最大子段和"

图片说明

图片说明 (上面的 k 变成 j 了)

这里要最小化截距,使用cdq分治

复杂度 图片说明 ,时限比较宽松,两个log也可以通过

几个关于这个写法代码细节的提示:

  • 排序时只用横坐标当关键字(横坐标相同的情况)
  • 维护凸壳时 图片说明 写成 图片说明
  • dp数组初值是0(题目中要求非空子段)

小D的lemon

默认 图片说明

图片说明
更换枚举顺序,先枚举 图片说明 ,原式化为

图片说明

图片说明 同时除以 图片说明

图片说明

图片说明 ,则

图片说明

图片说明

首先筛出 图片说明 ,然后可以在 图片说明 的时间内预处理出 图片说明 的前缀积

图片说明 可以在线性筛的过程中计算

图片说明 取值有 图片说明 种,所以每次询问可以 图片说明 回答

总复杂度 图片说明

小D的剑阵

先将 图片说明 求和,然后将选择/不选择视为在此基础上付出代价,问题就转化为了求最小代价。

对于每个约束,考虑如下的一个图,图片说明 表示源点和汇点, 图片说明 表示跟这个约束相关的两把剑, 图片说明 表示权值

将割掉 图片说明 到某一把剑 图片说明 的边视为不选择 图片说明 ,割掉 图片说明图片说明 的边视为选择 图片说明

要使 不连通,割有四种 (注意逗号)

图片说明

图片说明 表示选择 图片说明 能得到的攻击力, 表示选择 图片说明 能得到的攻击力,v0 表示 都选时额外获得的攻击力,图片说明 表示 图片说明 都不选时额外获得的攻击力,图片说明 表示只选一个时扣除的攻击力

可得

图片说明 ( x, y, 都不选)

图片说明 ( x, y 都选)

(不选 x,选 y )

(选 x,不选 y )

只需要求出一组合法的解,人为构造图片说明

最小代价即这张图的最小割

复杂度取决于使用的网络流算法,不过应该是都能通过的


标程:
A : 40352054, 40352242
B : 4035221740352034
C : 40352062
D : 三分, 分治nlog^2, 分治nlogn
E : 40352065
F : dinic ,isap,HLPP

全部评论

(8) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐