题解-货物运输、货物分组、反杀
T1 货物运输
部分分设置
对于30%我们可以直接暴力dfs是指数级复杂度。
对于50%的部分分，我留给某些可能的二分答案然后平方判断的做法。
对于一条链的情况，直接扫一遍就行。
正解思路
对于全部数据，我们首先对所有边按照边长排序。
然后对于一个连续的区间我们选了里面所有的边，代价是
我们枚举区间，然后使用并查集进行连通性判断。时间复杂度
T2 货物分组
部分分设置
对于10%的数据，我们暴力枚举分组数以及分组情况。
对于30%的部分分，留给暴力DP
对于60%的部分分，我们稍后会介绍一个暴力DP
正解思路
首先考虑一个DP
表示前n个分成m组的最小花费。我们只要枚举
之后
这样转移是的。我们考虑使用先付代价来DP.
表示前n个分成若干组的最小代价。那么我们枚举k之后
其中表示l~r的重量和加上其中最大值减最小值。
这样是的。
我们发现我们在转移过程中，可以用一个单调栈来维护最大值和最小值的变换，然后用线段树维护区间最值，就能每次更新答案。
时间复杂度
T3 反杀
部分分设置
对于的数据，我们暴力运算即可。
对于的数据，给一些有可能的与
无关的做法。
对于的数据，给推出第一个式子的做法。
正解思路
对于这个式子，我们把他分开，分别计算左右两边，然后相乘就为答案。
我们先来看右半边，通过打表发现，它的取值只有0,-1,1三种。我们思考为什么会出现这种现象。
我们考虑对于式子 我们使用扰动法找到它的递推式：
显然对于 都有
高中数学告诉我们这是一个周期为6的函数。我们把它前6项找出来，分别是1,1,0,-1,-1,0.
那么对于当
时，
. 当
为奇数时，
. 当
为偶数时，
右边的式子解决了，我们来看左边的式子。
我们把换成
那么我们有
我们考虑一个这样的式子 它实际上等于
考虑他的组合意义易证。
那么是满足上面的形式的，所以
那么左右两边我们都已经可以得到封闭形式了。
其中
我们发现很小，并且是个素数，考虑
定理，时间复杂度
阿里巴巴一面146人在聊