精英班考试题
2017.2.10
| 题目名 | 工资 | 藏妹子之处 | 银河之星 |
| 源文件 | money.cpp/c/pas | excel.pas/cpp | galaxy.cpp/c/pas |
| 输入文件 | money.in | excel.in | galaxy.in |
| 输出文件 | money.out | excel.out | galaxy.out |
| 时间限制 | 1000MS | 1000MS | 1000MS |
| 内存限制 | 256MB | 128MB | 256MB |
| 测试点 | 10 | 10 | 10 |
| 测试点分值 | 10 | 10 | 10 |
第一题 工资
(money/money.in/money.out)
时限1000ms 内存256MB
聪哥在暑假参加了打零工的活动，这个活动分为n个工作日，每个工作日的工资为Vi。有m个结算工钱的时间,聪哥可以自由安排这些时间，也就是说什么时候拿钱，老板说的不算，聪哥才有发言权！（因为聪哥是土豪，他是老板的老板）
聪哥不喜欢身上一次性有太多的钱，于是他想安排一下拿钱的时间，使他一次性拿的钱中最大的最小。（最后一天一定要领钱）
输入
第一行 2个数 n,m
接下来n行，每行一个数，代表Vi.
输出
最小的最大钱数。
样例输入
7 5
100
400
300
100
500
101
400
样例输出
500
样例说明
100 400//300 100//500//101//400//
“//”表示老大要去拿钱。
数据范围
20% 1<=n<=20
另 20% 1<=n<=50,Vi的和不超过1000
100% 1<=n<=100,000,m<=n,Vi<=10,000
第二题 藏妹子之处（excel）
问题描述：
今天CZY又找到了三个妹子，有着收藏爱好的他想要找三个地方将妹子们藏起来，将一片空地抽象成一个R行C列的表格，CZY要选出3个单元格。但要满足如下的两个条件：
（1）任意两个单元格都不在同一行。
（2）任意两个单元格都不在同一列。
选取格子存在一个花费，而这个花费是三个格子两两之间曼哈顿距离的和（如(x1,y1)和(x,y2)的曼哈顿距离为|x1-x2|+|y1-y2|）。狗狗想知道的是，花费在minT到maxT之间的方案数有多少。
答案模1000000007。所谓的两种不同方案是指：只要它选中的单元格有一个不同，就认为是不同的方案。
输入格式：
一行，4个整数，R、C、minT、maxT。3≤R,C≤4000, 1≤minT≤maxT≤20000。
对于30%的数据, 3 ≤ R, C ≤ 70。
输出格式:
一个整数，表示不同的选择方案数量模1000000007后的结果。
输入输出样例：
| 输入样例 | 3 3 1 20000
| 3 3 4 7
| 4 6 9 12 | 7 5 13 18
| 4000 4000 4000 14000 |
| 输出样例 | 6 | 0 | 264 | 1212 | 859690013
|
第三题 银河之星
用时：1:30min 2:60min 3:30min
预估分：200
结果：
