A. 校门外的树
问题描述
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0,1,2,...,L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入形式
第一行有两个整数L(1≤L≤10000)和M(1≤M≤100)，L LL代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出形式
输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
样例输入
500 3 150 300 100 200 470 471
样例输出
298
B. 合格的素数
问题描述
求A..B之间包含数字D的素数个数。(1≤A≤B≤4000000,B≤A+1000000)
输入形式
1行，三个整数A,B,D
输出形式
1个整数，满足条件的素数个数
样例输入
10 15 3
样例输出
1
C. 高精度乘法
问题描述
求两个正整数之积
输入形式
共两行，每行一个正整数，每个数小于1000位
输出形式
求两整数的积
样例输入
12 12
样例输出
144
D. 纪念品分组
问题描述
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
数据规模：
50%的数据满足：n≤15；
100%的数据满足：le 2001≤n≤30000，80≤W≤200。
输入形式
第1行包括一个整数w，为每组纪念品价格之和的上限。
第2行为一个整数n，表示购来的纪念品的总件数。
第n+2行每行包含一个正整数Pi(5≤Pi≤w)，表示所对应纪念品的价格。
输出形式
输出仅一行，包含一个整数，即最少的分组数目。
样例输入
100 9 90 20 20 30 50 60 70 80 90
样例输出
6
E. 愤怒的牛
问题描述
Bessie 设计了一款新游戏：Angry Cows。在这个游戏中，玩家发射奶牛，每头奶牛落地时引爆一定范围内的干草。游戏的目标是使用一组奶牛引爆所有干草。
N NN捆干草排列在数轴上的不同位置。第i ii捆干草的的位置为xi。如果一个威力为R的奶牛在x位置落地，她将引爆[x−R,x+R]范围内的所有干草。
你现在可以发射K头奶牛，每头奶牛的威力都R RR，现在你需要确定R RR的最小值，使得用K头奶牛可以引爆所有干草。
输入形式
第一行两个整数N,K(1≤N≤5×104,1≤K≤10)。
接下来N行，第i行一个整数xi(0≤x≤109)。
输出形式
输出一个整数，即 R 的最小值。
样例输入
7 2 20 25 18 8 10 3 1
样例输出
5
F. 智取金币
问题描述
贝西和她的朋友邦妮挖到了一个宝箱，里面藏着N枚金币！但是金币对奶牛没用，她们一直用这些金币来玩游戏。游戏开始之前，金币会被排成一条队列，在第i个位置的金币价值为Ci。贝西和邦妮轮流取金币，轮到拿的时候，只能选择队列的最前面的那块，或队列最后面的一块，所有金币取完之后，游戏就结束了。
贝西和邦妮都是非常聪明的，她们从不犯错，会采用最好的策略让自己取到的金币价值最大。假设贝西是先手，请帮她计算一下，她最多能拿价值多少的金币？
输入形式
第一行：单个整数：N，1≤N≤5000
第二行到第N+1行：第i+1行有一个整数：Ci≤5000
输出形式
单个整数：表示如果双方都按最优策略进行游戏，先手可以拿到的最大价值之和
样例输入
4 30 25 10 35
样例输出
60
G. 合并果子
问题描述
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n−1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1 11，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
数据规模：
对于30 ％ 30％30％的数据，保证有n≤1000；
对于50 ％ 50％50％的数据，保证有n≤5000；
对于全部的数据，保证有n≤10000。
输入形式
第一行：是一个整数n(1≤n≤10000)，表示果子的种类数。
第二行：包含n个整数，用空格分隔，第i个整数ai(1≤ai≤20000)是第i ii种果子的数目。
输出形式
输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。
样例输入
3 1 2 9
样例输出
15
H. 数独
问题描述
将格子填满使得
每一行， 每一列，和每一个小的九宫格恰好包含1−9这9个数字,正是由于规则简单而又变化多端，数独一时间风靡全球。
现在，我们希望你能编写一个程序解决数独问题。
输入形式
输入数据一共9 99行，每行有9个字符。输入数据描述了一个待解决的数独，其中，“?”表示数独中的空缺。我们的输入数据总保证有唯一解。
输出形式
输出一共9行，每行9个数字，表示你的答案。
样例输入
5????7??6 ?6????5?4 ?834????? ???182?4? ??1???9?? ?7?369??? ?????543? 1?5????9? 7??2????1
样例输出
514927386 967831524 283456179 659182743 321574968 478369215 892615437 135748692 746293851
I. 地平线上的高楼
问题描述
约翰带上她的奶牛到城市里观光，在落日的余晖里，他们看到了城市的高楼的边缘在地平线上形成的美丽图形．
这个图形由N(1≤N≤40000)座高楼抽象而成．把地平线看成数轴，每座楼有两个整数的起始坐标和终止坐标Ai和Bi(1≤Ai<Bi≤109)．当然，每座楼会有一个高度Hi(1≤Hi≤109)．
请计算这个阴影构成的图形的面积．
输入形式
第一行输入N。
之后N行每行输入三个整数Ai，Bi和Hi。
输出形式
阴影构成的图形的面积．
样例输入
4 2 5 1 9 10 4 6 8 2 4 6 3
样例输出
16
样例说明
第1座楼和第4座楼有面积为1的重合部分．所以总面积为3 × 1 + 1 × 4 + 2 × 2 + 2 × 3 − 1 = 16。
J. 天天爱跑步
问题描述
小 C 同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。
这个游戏的地图可以看作一棵包含n 个结点和 −1 条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从1 到 的连续正整数。现在有m 个玩家，第 i 个玩家的起点为 Si ，终点为Ti 。 每天打卡任务开始时，所有玩家在第0秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以每个人的路径是唯一的）
小 C 想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点j jj的观察员会选择在第Wj秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第Wj秒也正好到达了结点j。 小 C 想知道每个观察员会观察到多少人？
注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。 即对于把结点j作为终点的玩家：若他在第Wj秒前到达终点，则在结点j jj的观察员不能观察到该玩家；若他正好在第Wj秒到达终点，则在结点j 的观察员可以观察到这个玩家。
输入形式
第一行有两个整数n nn和m mm。 其中n nn代表树的结点数量，同时也是观察员的数量,m mm 代表玩家的数量。
接下来n−1行每行两个整数u和v vv，表示结点u到结点v有一条边。
接下来一行n个整数，其中第j jj个整数为Wj ，表示结点j jj出现观察员的时间。
接下来m行，每行两个整数Si 和Ti ，表示一个玩家的起点和终点。 对于所有的数据，保证1≤Si,Ti≤n ，Wj≤n 。
输出形式
输出1 11 行n 个整数，第 j 个整数表示结点 j 的观察员可以观察到多少人。
样例输入
6 3 2 3 1 2 1 4 4 5 4 6 0 2 5 1 2 3 1 5 1 3 2 6
样例输出
2 0 0 1 1 1
样例说明
对于 1 号点，W1=0 ，故只有起点为 1 号点的玩家才会被观察到，所以玩家 1 和玩家 2 被观察到，共 2 人被观察到。
对于 2 号点，没有玩家在第 2 秒时在此结点，共 0 人被观察到。
对于 3 号点，没有玩家在第 5 秒时在此结点，共 0 人被观察到。
对于 4 号点，玩家 1 被观察到，共 1 人被观察到。
对于 5 号点，玩家 2 被观察到，共 1 人被观察到。对于 6 号点，玩家 3 被观察到，共 1 人被观察到。
