牛客练习赛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
