牛客网 模拟赛
牛客CSP-S提高组赛前集训营3
T1.
题目描述 :
Venn想要收集一些货物。
Venn有一颗n个节点的树，一开始Venn在1号节点，其他每个节点都有一定的货物储备，Venn只要经过那些节点，就可以收集到节点的所有货物。每个节点的货物只能收集一次。
显然，Venn并不能轻易的收集所有的货物。每一条连接着两个节点的路径，都有一个邪恶的怪物镇守。Venn的武力值必须不小于怪物的武力值才能安全地从这条路径上通过。
Venn一开始的武力值是0，但是她可以选择健身来提升自己的武力值。每健身一分钟，就会提升一点武力值。Venn并不想收集所有的货物，只要最终收集到的货物总量不低于W就可以了。Venn一旦开始收集，就不能再健身了。但是Venn的速度很快，可以认为收集货物和从路径上经过都不需要时间。
由于Venn还急着去颓废，所以她想让你帮她计算收集到指定数量的货物最少需要几分钟。
Solve:
可以发现， 健身时间具有单调性， 也就是健身时间越长，那么Venn可以收集到的货物数量也会越多，那么就可以二分健身时间 t,然后O(n)进行一遍dfs来check是否合法。总的时间复杂度为
T2.
题目描述 :
Venn要对货物打包。
每个货物有一定的重量，她可以用若干个箱子来装下所有的货物,但是每个箱子中物品重量总和不能超过W。
Venn有一个独特的习惯，在装货过程中，某一个箱子里货物的编号必须是一个连续的区间，并且必需依次使用箱子按照物品的编号顺序装入，具体来讲编号为1的箱子一定包含1号物品，编号最大的箱子一定包含n号物品。
对于第i个箱子，如果里面装的货物总重量为w，那么费用为i*w 。
另外对于每一个箱子，在通过门卫时还会被收税，税款是箱子中重量最大的货物的重量减去重量最小的货物的重量。
她想知道，把所有货物打包并运过门卫所需要的最小费用为多少。
solve:
动态规划
f[i]: 将 前 i 件物品分成若干组的最小价值。
每一个箱子的费用还与它是第几个箱子有关， 而我们的DP状态中并没有保存它是的几个箱子，那么可以考虑 费用提前算
如果计算每一个箱子只按照它是第 1 个箱子进行计算 ，而且最终还要与它是第几个箱子计算的结果一致，那么
可以考虑在计算f[i]时，它对后续状态的影响，我们把k ~ i个物品装入一个箱子中，假设是第 x 个箱子， 那么物品 i ~ n 就会被装入第 x + 1个箱子， 如果我们在计算f[i]时，提前将 i ~ n 的费用提前加上， 那么计算 i~ n时， 就可以当做计算 第 x 个箱子来计算。
如果从 f[1]开始就这样计算， 那么我们在计算每一个 f[i]时， 都可以将其看做是第一个箱子。
总时间复杂度为
T3
题目描述:
Venn忙碌了一整天，回到了某高中，发现自己学校正在施工，整个学校的地形全变了！Venn作为一个路痴，想要计算施工结束以后地形的复杂度。
某高中的地形可以抽象为一个n个点，m条边的无向带权简单图。(如果你不清楚什么是简单图，请阅读题面描述末尾加粗部分)。
Venn认为一个无向图的复杂程度，和它的四元环有关。一个四元环是指如果存在四个不相同的点u,v,x,y并且存在边(u,v),(v,x),(x,y),(y,u),那么这四个点和这四条边所组成的集合称为一个四元环。一个四元环的权值，是组成他的所有顶点的权值之和。Venn想要统计这张图所有本质不同的四元环的权值之和（如果你不知道什么是本质不同，请阅读文末加粗部分）。由于这个答案可能很大，你只需要求出它对10^9++7取模的值就行了。
solve:
从每个点往下搜四层，如果回到了这个点，那么说明有一个四元环，我们把中间经过的点累加进答案。
这样每次扩展