day2的暴力分拿的还算稳，然而只会打暴力......

T1数论题， 30分暴力直接走人

T2很像一个DP，先打了暴力留着对拍，结果刚了两个小时毛都没写出来，暴力也萎了......

T3最小生成树啊，码完kruskal直接走人，后来才知道prim可以拿60分，我ri......

30+0+30=60

T1 挖掘机技术哪家强：

题目描述：

有人问现实中为什么总是男生追求女生，反过来很少。实际上女生也是想主 动追求男生的，但是世俗中对于主动追求男生的女生有种歧视，这样就使得女生 不大敢主动追求男生。但是面对喜欢的男生，难道就不出手么？女生只能步步为 营，挖坑来引诱男生往里跳。这时候问题就来了，挖掘机技术到底哪家强？ 被热血沸腾的广告洗脑了若干天后，Matt 终于下定决心，毅然登上了开往 泉城的列车，决心寻找生活的希望。 来到布鲁谢特学院后，Matt 逐渐地了解了各种型号的挖掘机。在这里我们 可以认为有大挖掘机和小挖掘机两种。 今天 Matt 的任务很简单： 首先他要用大挖掘机挖出恰好 N 单位体积的砂土。 由于小挖掘机比较笨拙，它每次挖的砂土体积是固定的。也就是说，设每次挖 x 单位体积砂土，那么 N 需要被 x 整除。在挖出若干堆体积为 x 的砂土后，Matt 需要计算 x 的“难挖指数” 。体积 x 的“难挖指数”定义如下：对于某个不超过
x 的体积 y，如果 x 与 y 的最大公约数为 1，那我们认为体积 y 是“难挖的” ，x 的“难挖指数”就要加上 y。 由于 Matt 之后还需要用小挖掘机处理被大挖掘机挖出的砂土，他希望知道 所有可能的 x 的难挖指数的和，这样他好估算今天要干多久，不然作为布鲁谢特 的高才生，他出门要被笑话的。

T2 孤独一生：

题目描述：

下课了，Polo 来到球场，但他到了之后才发现…..被放了飞机…… 无事可做的他决心找点乐子，比方说……跳台阶…… 球场边有 N 个台阶拍成一行，第 i 个台阶的高度是 Hi(0<Hi<=10^9)，第 0 个台阶，也就是地面的高度为 0。 Polo 打算把这 N 个台阶分成两个集合 Sa,Sb（可 以为空） ，对于一个台阶集合 S={P1,P2,...P|S|}，其中 P1<P2<...<P|S|，他需要花费 ∑|H_p_i-H_p_i-1|的体力值来完成。 现在他希望两次跳跃所需的总体力值最小，你能帮帮他吗？

50分暴力：

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<cmath>
 6 #include<algorithm>
 7 #define ll long long
 8 using namespace std;
 9 
10 const int maxn = 5010;
11 
12 int n,h[maxn];
13 ll dp[maxn][maxn];
14 
15 int main() {
16   scanf("%d", &n);
17   for(int i=1; i<=n; i++) scanf("%d", &h[i]);
18   memset(dp,127/3,sizeof(dp));
19   dp[0][0]=0,dp[1][0]=dp[0][1]=h[1];
20   for(int i=0; i<=n; i++) {
21     for(int j=0; j<i-1; j++) {
22       dp[i][j]=dp[i-1][j]+1ll*abs(h[i]-h[i-1]);
23       dp[j][i]=dp[i][j];
24     }
25     for(int k=0; k<i-1; k++) {
26       dp[i][i-1]=min(dp[i][i-1],dp[k][i-1]+1ll*abs(h[i]-h[k]));
27       dp[i-1][i]=dp[i][i-1];
28     }
29   }
30   ll ans=1000000000000000;
31   for(int i=0; i<n; i++) {
32     ll res=min(dp[n][i],dp[i][n]);
33     ans=min(ans,res);
34   }
35   printf("%lld", ans);
36   return 0;
37 }

T3 地壳运动：

题目描述：

JZ 是一个坐落在地壳运动活跃的山区的城市，常受地质灾害的袭击。 城市中建立了 N 个应急避难所以躲避灾害，这些避难所从 1～N 编号。此外 有 M 条道路连接这些避难所，所有避难所间均可通过这 M 条道路直接或间接到 达。由于是在规划良好的市区，道路可以由若干个平行于 x 或 y 坐标轴的线段组 成，所以避难所 xi 和 yi 之间的道路可以用(ui,vi)来表示，道路的长度为 ui+vi。 由于地壳运动会导致地面拉伸或收缩， 可用两个实数k1,k2 描述城市的伸缩程度， 此时某条道路的实际长度变ui*k1+vi*k2。有若干个独立的询问，每次询问给 出 k1 和 k2，政府都希望在此地壳运动前提下，以最小的花费维护其中一些道路， 使得只用这些被维护的道路仍能使所有避难所间相互连通。 因为花费与道路的实 际总长成正比，所以你需要对每一次询问求出被维护道路的最短实际总长。

联考8.5