牛客练习赛40题解

2019-05-04 UPD：见评论

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

欢迎dalao交流做法

牛客练习赛40题解

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

小D的剧场

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

转移方程为

can为 表示不合法， 表示合法。

时间复杂度 。

小A与任务

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

复杂度

小A与欧拉路

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

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

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

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

复杂度

小A与最大子段和

似乎好多人被题面误导了

令

表示以 为右端点的 “最大子段和”，假设左端点为

则

可得 ，可以使用斜率优化

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

另有一种 单调， 不单调的推法（鸣谢验题人）

表示以 为左端点的"最大子段和"

令

(上面的 k 变成 j 了)

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

复杂度 ，时限比较宽松，两个log也可以通过

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

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

小D的lemon

默认

更换枚举顺序，先枚举 ，原式化为

将 同时除以

设 ，则

设

首先筛出 ，然后可以在 的时间内预处理出 的前缀积

可以在线性筛的过程中计算

取值有 种，所以每次询问可以 回答

总复杂度

小D的剑阵

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

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

将割掉 到某一把剑 的边视为不选择 ，割掉 到 的边视为选择 。

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

设 表示选择 能得到的攻击力， 表示选择 能得到的攻击力， 表示 都选时额外获得的攻击力， 表示 都不选时额外获得的攻击力， 表示只选一个时扣除的攻击力

可得

( x, y, 都不选)

( x, y 都选)

(不选 x，选 y )

(选 x，不选 y )

只需要求出一组合法的解，人为构造

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

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

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