机房模拟20180813

T1 

 

 我们可以轻松地发现这道题是一道dp的题目

对于整张图来说，总共有2*n-2地度数，由于每一个点都至少有一个度数，我们就只剩下n-2的度数可以进行自由分配

我们将每个点看做一个点加上一条没有连上其他点的边，然后在更新的时候将所有点联向当前树的叶子节点上，然后根据其度数做一下背包就好了

f[i] 表示树上已经有i 个点的最佳权值

假设度数为i的贡献为a[i]，当一个节点插入的时候，会损失a[1]的价值，增加a[i-j+1]的价值，所以转移方程为

f[i]=max(f[i],f[j]+a[i-j+1]-a[1]),1<=j<=i;

然后直接转移即可

这道题是今天最难的题了.......

T2

k%i可以转化成k-floor(k/i)，所以说在连续一段以内的除法德商完全相同，只有被除数k不同，而这一段是连续的，所以可以使用等差数列求和

数的因数不会超过sqrt(n),所以每一次枚举商相同的块，for循环跑一遍就出答案了

T3

 今天最水的题目，直接二分答案，然后向左右一次减一，等差数列求和，然后判断是否可行.....（这道题基本全A.......）

总结一下....T2的正解没有想到，但是靠优化的暴力苟了70分(数据梯度不大.....只有3组是超过了1e8的)

T3水过

T1手推失败.....