T1
题目描述
被无止境的农活压榨得筋疲力尽后，Farmer John打算用他在MP3播放器市场新买的iCow来听些音乐，放松一下。FJ的iCow里存了N(1 <= N <= 1,000)首曲子，按1..N依次编号。至于曲子播放的顺序，则是按一个Farmer John自己设计的算法来决定：
* 第i首曲子有一个初始权值R_i(1 <= R_i <= 10,000)。
* 当一首曲子播放完毕，接下来播放的将是所有曲子中权值最大的那首（如果有两首或多首曲子的权值相同，那么这些曲子中编号最小的那首会被选中）。
* 一首曲子在播放结束后，它的权值会被平均地分给其他N-1首曲子，它本身的权值清零。
* 如果一首曲子的权值无法被平均分配（也就是说，无法被N-1整除），那么被N-1除的余数部分将会以1为单位，顺次分配给排名靠前的曲子（也就是说，顺序为曲目1、曲目2...依次下去。当然，刚播放过的那首曲子需要被跳过），直到多出的部分被分配完。
在选定的下一首曲子播放完毕后，这个算法再次被执行，调整曲子的权值，并选出再接下来播放的曲目。
请你计算一下，按FJ的算法，最先播放的T(1 <= T <= 1000)首曲子分别是哪些。
输入
第1行: 2个用空格隔开的整数：N 和 T
第2..N+1行: 第i+1行为1个整数：R_i
输出
第1..T行: 第i行为1个整数，表示iCow播放的第i首曲子
样例输入
3 4
10
8
11
样例输出
3
1
2
3
数据范围限制
提示
每一首曲子播放前，三首曲子的权值分别为：
R_1 R_2 R_3
10 8 11 -> 播放 #3 11/2 = 5, 权值余量 = 1
16 13 0 -> 播放 #1 16/2 = 8
0 21 8 -> 播放 #2 21/2 = 10, 权值余量 = 1
11 0 18 -> 播放 #3 ...
T2
题目描述
万圣节又到了！Farmer John打算带他的奶牛去参加一个化装晚会，但是，FJ只做了一套能容下两头总长不超过S(1 <= S <= 1,000,000)的牛的恐怖服装。FJ养了N(2 <= N <= 20,000)头按1..N顺序编号的奶牛，编号为i的奶牛的长度为L_i(1 <= L_i <= 1,000,000)。如果两头奶牛的总长度不超过S，那么她们就能穿下这套服装。
FJ想知道，如果他想选择两头不同的奶牛来穿这套衣服，一共有多少种满足条件的方案。
输入
第1行: 2个用空格隔开的整数：N 和 S
第2..N+1行: 第i+1为1个整数：L_i
输出
第1行: 输出1个整数，表示FJ可选择的所有方案数。注意奶牛顺序不同的两种 方案是被视为相同的。
样例输入
4 6
3
5
2
1
样例输出
4
数据范围限制
提示
【输出说明】 4种选择分别为：奶牛1和奶牛3；奶牛1和奶牛4；奶牛2和奶牛4；奶牛3和奶牛4。
T3
FJ的N(1 <= N <= 100)头奶牛们最近参加了场程序设计竞赛:)。在赛场上，奶牛们按1..N依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。
整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为A的奶牛的编程能力强于编号为B的奶牛(1 <= A <= N; 1 <= B <= N; A != B)，那么她们的对决中，编号为A的奶牛总是能胜出。
FJ想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有M(1 <= M <= 4,500)轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。
输入
第1行: 2个用空格隔开的整数：N 和 M
第2..M+1行: 每行为2个用空格隔开的整数A、B，描述了参加某一轮比赛的奶 牛的编号，以及结果（编号为A，即为每行的第一个数的奶牛为胜者）
输出
第1行: 输出1个整数，表示排名可以确定的奶牛的数目
样例输入
5 5
4 3
4 2
3 2
1 2
2 5
样例输出
2
数据范围限制
提示
【输出说明】 编号为2的奶牛输给了编号为1、3、4的奶牛，也就是说她的水平比这3头奶 牛都差。而编号为5的奶牛又输在了她的手下，也就是说，她的水平比编号为5的 奶牛强一些。于是，编号为2的奶牛的排名必然为第4，编号为5的奶牛的水平必 然最差。其他3头奶牛的排名仍无法确定。
T4
1155. 贝茜的晨练计划(cowrun)
(File IO): input:cowrun.in output:cowrun.out
时间限制:
1000 ms 空间限制:
262144 KB 具体限制
Goto ProblemSet
T4
题目描述
奶牛们打算通过锻炼来培养自己的运动细胞，作为其中的一员，贝茜选择的运动方式是每天进行N(1 <= N <= 10,000)分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息。
贝茜的体力限制了她跑步的距离。更具体地，如果贝茜选择在第i分钟内跑步，她可以在这一分钟内跑D_i(1 <= D_i <= 1,000)米，并且她的疲劳度会增加1。不过，无论何时贝茜的疲劳度都不能超过M(1 <= M <= 500)。如果贝茜选择休息，那么她的疲劳度就会每分钟减少1，
但她必须休息到疲劳度恢复到0为止。在疲劳度为0时休息的话，疲劳度不会再变动。晨跑开始时，贝茜的疲劳度为0。
还有，在N分钟的锻炼结束时，贝茜的疲劳度也必须恢复到0，否则她将没有足够的精力来对付这一整天中剩下的事情。
请你计算一下，贝茜最多能跑多少米。
输入
第1行: 2个用空格隔开的整数：N 和 M
第2..N+1行: 第i+1为1个整数：D_i
输出
第1行: 输出1个整数，表示在满足所有限制条件的情况下，贝茜能跑的最大距离
样例输入
5 2
5
3
4
2
10
样例输出
9
数据范围限制
提示
【输出说明】 贝茜在第1分钟内选择跑步（跑了5米），在第2分钟内休息，在第3分钟内跑 步（跑了4米），剩余的时间都用来休息。因为在晨跑结束时贝茜的疲劳度必须 为0，所以她不能在第5分钟内选择跑步。
2016.8.15
考试思路：
T1
这题比较简单，其实就是模拟选歌和平均分配权值的过程而已，每次找最大权值的一首歌，输出，然后给除了它自己以外的n-1首歌加上r[i] div (n-1)，然后判断能不能整除，如果不能则从1到n，除了自己以外，一个一个加上1，每次给其他权值加上1时，dec(除剩的余数)，直到余数变为0则退出这个循环。
T2
这题就更简单了，直接从小到大快排然后两个for循环i从1到n-1，j从i+1到n，暴力枚举每一个l[i]+l[j]是否小于等于s，当然还要加上一点优化，就是如果l[i]+l[j]大于s，则l[i]即使再加后面的l[j]也一定不会满足条件，所以退出内循环，每次满足条件答案加一，就可以了。
T3
这题比赛时没想出方法，只是听见别人说可以用弗洛伊德算法，所以一直围绕这个来想，但也没有想出来。
T4
动态规划。f[i,j]表示第i分钟疲劳值为j的最大路程，因为每次休息都必须休息到疲劳值为0，还有结束时疲劳值一定为0，所以可推出状态转移方程，核心代码如下：
[plain]
view plain
copy
for i:=1 to n do begin f[i,0]:=f[i-1,0]; //这次的最大值先赋为上次的最大值 for j:=1 to m do begin if i>=j then f[i,0]:=max(f[i,0],f[i-j,j]); //比较现在的最大值和之前在第j分钟时休息哪个更大 f[i,j]:=max(f[i-1,j-1]+a[i],f[i,j]); //比较怎么走值最大 end; end;
正确思路：
T1
同上。
T2
同上。
T3
使用弗洛伊德算法，把输入的a和b进行处理，f[a,b]:=a,f[b,a]:=a,表示这a和b的胜者为a，也就是他们两个的父亲，然后和常规的弗洛伊德算法一样，三层循环，中转点k放外面，判断f[i,k]是否等于i，而f[k,j]是否等于k，如果成立，则证明i间接性的击败了j，f[i,j]:=i,f[j,i]:=i,最后判断每一只奶牛的父亲和儿子是否累加起来等于n-1，如果是则累加答案，就可以了。核心代码如下：
[plain]
view plain
copy
for k:=1 to n do for i:=1 to n do for j:=1 to n do if (i<>j) and (f[i,j]=0) and (f[i,k]=i) and (f[k,j]=k) then begin f[i,j]:=i; f[j,i]:=i; end; for i:=1 to n do begin t:=0; for j:=1 to n do begin if f[i,j]<>0 then inc(t); end; if t=n-1 then inc(ans); end;
T4
同上。
转载请注明原文地址: https://ju.6miu.com/read-1303556.html
