problem

1.输入输出统一为 文件名.in / 文件名.out

2.时间统一为1s

3.空间统一为32MB

4.所考察的均为Noip大纲内算法

5.感谢mlj同学为第二四题背景描述作出贡献

工件处理

题目描述

     一个工厂所运行的生产线对每个工件有2道工序A和B，每道工序有一定数量的机器可以实现，分别定义为A类机和B类机。

     对于每个工件，都必须先经工序A处理，再经工序B处理，而每个机器可以的，同时的工作，每个机器工作需要的时间不一样。

Your Task

现有N个工件，找出最早的时间让所有工件完成所有工序A和最早时间完成两道工序。

输入文件

 第一行 N M1 M2 分别为工件数，A类机数量，B类机数量。

 第二行 M1个整数描述了每个A类机处理任一个工件的时间。

 第三行 M2个整数描述了每个B类机处理任一个工件的时间。

输出文件

     一行包含两个整数，分别是最早的时间让所有的工件完成工序A作与最早的时间完成两道工序。

样例输入

5 2 3

1 1 

1 3 4

样例输出

3 5

数据约定

    60%    N<=1000   1<=M1,M2<=30  T<=20    Ans<=maxint 

100% N<=100000 1<=M1,M2<=5000 T<=10000 Ans<=maxlongint

评分方式

本题有部分分，对于每一个测试点，若你仅有第一个输出正确则得40%分数，若你仅有第二个输出正确则得60%分数，若你两个输出均正确则得100%分数，否则不得分。

山顶问题

题目描述

话说某某在cj校运会上异军突起，其实不是偶然，而是有历史原因的。

时光回溯到XX年前，某某为了心中的理想，每天爬N里山路上学。直到有一天mlj（也就是战神Mars）来到这里，被某某所打动，于是决定帮某某一把。从某某家到学校中间的这N里山路在一条直线上，第i里山路的海拔高度为Hi，如果一段相同高度的山路两边都比它低或者是山的边界，那么这段山路将被称之为“山顶”。mlj想这连绵起伏的山路爬着多累啊，于是他决定动用神力，降低某些山路的海拔高度使得山顶的个数不超过K。但mlj不想做得太明显而被某某发现，于是他求助于你。

Your Task

请求出要使“山顶”的数目不超过k，所有山路降低的高度之和至少是多少。

输入文件

 第一行两个正整数 N K。

 接下来一行N个正整数Hi。

输出文件

     一个数，最小的所有山路减少的高度之和。

样例输入

12 1

1 2 3 3 3 2 1 3 2 2 1 2

样例输出

5

样例解释

    * * *     *

  * * * * *   * * *   *

* * * * * * * * * * * *

1 2 3 3 3 2 1 3 2 2 1 2

这是之前山的形状，有3个山顶。

    * * *     -

  * * * * *   - - -   -

* * * * * * * * * * * *

1 2 3 3 3 2 1 1 1 1 1 1

这是mlj用了神力之后（‘-’表示被mlj的神力OOXX掉了），只剩下一个山顶。

数据约定

100%  K<=25 1<=Hi<=1000000

90% N<=1000

100% N<=100000

生成树

题目描述

     对于无向图G,它的任一棵生成树T的权值P(t)定义为T的所有边权的最大公约数。

Your Task

对于给定的图G，求出其所有生成树T1,T2……的权值P(T1),P(T2)……的最小公倍数。

输入文件

 第一行 N M 表示图G的点数，边数。

 接下来M行 Si Ti Di 描述一条边（Si,Ti）权值为 Di。

 保证图连通，无自环。

输出文件

     一个数，所有生成树权值的最小公倍数。

样例输入

     3 3

1 2 2 

2 3 3 

1 3 6

样例输出

6

样理解释

     有3棵生成树，权值分别为1,2,3,它们的最小公倍数为6。

数据约定

20%   M=N-1

 30%   M=N

100% N<=1000 M<=100000 Di<=2^15-1 Ans<=2^-1

保证极限数据很少。

黑白三角形

题目描述

     一天，mlj在平面上画了N个黑点和N个白点，按以下方式来连边，构成一个有向完全图。

1.I J同色，随机选择I→J或J→I

2.I J异色，若Dij>D，则白点→黑点，否则黑点→白点

这里的Dij指的是曼哈顿（|xi-xj|+|yi-yj|)，D为给定值

然后，mlj发现有很多三角形很漂亮，漂亮三角形的定义如下：

1.三个顶点I J K颜色不完全相同

2.它们之间的连的边是 I→J J→K K→I

（至于为什么mlj觉得这样漂亮，大概是火星人审美观与众不同吧）

     mlj想知道这里面漂亮三角形的个数，但他视力很差，于是求助于你。

Your Task

求出漂亮三角形最少有多少个，最多有多少个。

输入文件

     第一行两个正整数 N D 

     接下来N行Xi Yi描述第i个白点的坐标

     再接下来N行Xj Yj描述第j个黑点的坐标

输出文件

     两个数依次为漂亮三角形最少的个数，最多的个数，中间用一个空格隔开。

样例输入

2 1

1 2

1 1

3 1

2 2    

样例输出

     0 2

样例解释

左图为无漂亮三角形的情况，右图存在两个漂亮三角形，分别是(1,2,4)(1,3,4)

数据约定

40% N<=300

70%    N<=3000

100%   N<=100000  1<=x,y,d<=100000且为整数