Noip2009普及组复赛问题解决报告
问题转述如下:
给出一元多项式的次数和系数，按照指定的格式要求输出多项式。
分析:
普及组的水问题。多项式应该大家都很熟悉，输出时注意以下几点就行了:
1.如果最高项为正，则开头没有加号。
2.如果系数为0，则不输出。
3.主项输出x，而不是x 1。
4.当非常项的系数为1或-1时，直接输出符号，但常数项需要输出这个数。
其中，除了第三项，其他都可以在样本中检测出来，但如果没有想到第三项，只能得50分。
程序:
var i，k，n:longint；
开始
赋值(input，' poly . in ')；复位(输入)；
赋值(output，' poly . out ')；重写(输出)；
readln(n)；
做某事
开始
读(k)；
如果k=0，则继续；
if(k & gt；0)和(i & lt& gtn)然后写('+')；
如果i=0，则写(k)
else if(ABS(k)& lt；& gt1)然后写(k) else如果k=-1然后写('-')；
如果我& lt& gt那么0
如果i=1，则写(' x ')
否则write('x^',i)；
结束；
writeln
关闭(输入)；
关闭(输出)；
结束。
2009-11-28 12:03回复
自杀猫
0粉丝
三楼
分数线的划分
问题转述如下:
给出录取人数以及所有面试人员的分数和考号。找出分数线和实际录取人数，按成绩降序输出考生的考号和成绩，成绩相同则按考号升序输出。
分析:
双重关键字排序。因为n在5000左右，为了保证不是TLE，需要使用快速排序等nlogn排序。然后将指针指向最后一个打算报名的人，滑动到最后一个同分的人。那么指针就是之前实际录取的面试官。
程序:
类型arr = arraytemp 1:= a & lt；temp 2))do Inc(I)；
while(a & gt；temp 2))do dec(j)；
如果我& lt=那么j
开始
swap(a，a ' '，a:= 0；
而k mod i=0 do
开始
公司(a)；
k:= k div I；
结束；
结束；
直到k = 1；
结束；
主程序；
var i，z，max:longint；
开始
max:=-1；
读(k)；
对于i:=1到总do
开始
如果k mod a+z-1)div z & gt；max then max:=(a+z-1)div z；
结束；
如果max & ltans然后ans:= max；
结束；
开始
赋值(input，' cell . in ')；复位(输入)；
赋值(output，' cell . out ')；重写(输出)；
ans:= maxlongint；
readln(n)；
readln(m1，m2)；
如果m1=1，则开始writeln(0)；关闭(输入)；关闭(输出)；停止；结束；
因式分解(m1，a，合计)；
对于i:=1要合计做a:= a * m2；
对于i:=1到n do
主要；
如果ans=maxlongint那么writeln(-1)否则writeln(ans)；
关闭(输入)；
关闭(输出)；
结束。
回复
自杀猫
0粉丝
五楼
公路游戏
问题转述如下:
有一条有n个点的环形道路，第I个点通过一条边与i+1点相连(第n个点通过一条边与1点相连)。每个点可以以不同的成本产生一个机器人，机器人可以顺时针走不超过p步(每一步用一个单位时间)，捡起此时路上的金币。路上最多只能有一个机器人。在不同的时间，每条路上有不同数量的金币。求最终能获得的金币的最大数量。(即捡到的金币数减去生产机器人所需的金币数)。
分析:
题目的描述极其恶心。理清思路后，你应该能搞清楚这个题目是动态编程。因为m，n高达1000，所以只能设计时间复杂度为O(mn)的动态量规。这类问题的动态尺度比较好，即:
其中f[i，j]是I时刻J点获得的最大金币数Coin[i，j]是I时刻J路上的金币数。Cost[k]代表在k点购买机器人花费的金币数，其中1 < = k & lt；=n .Step[i，j]表示当f[i，j]的状态存在时机器人已经走过的步数。Past[j]是j之前的点，即past [I] = I-1 (2
注意，这个动态量规是三维的，但是因为前一阶段的最优值不变，所以我们只需要在计算完这一阶段的最优值后，顺便保存最大的一个作为下一阶段的最优值即可。
程序:
var i，j，k，n，m，p，pastmax，now max:longint；
硬币，f，步骤:数组[0..1000,0..longint的1000]；
成本，过去:数组[1..longint的1000]；
开始
assign(输入，' game . in ')；复位(输入)；
assign(output，' game . out ')；重写(输出)；
filldword(step，sizeof(step) shr 2，maxlongint)；
readln(n，m，p)；
对于i:=2到n do
过去[I]:= I-1；
过去[1]:= n；
对于i:=1到n do
对于j:=1到m do
read(coin[j，I])；
对于i:=1到n做read(cost[I])；
past max:= 0；
对于i:=1到m do
开始
now max:=-maxlongint；
对于j:=1到n do
开始
如果step[i-1，past[j]]& lt；那么警
开始
if past max-cost[past[j]]& gt；f[i-1，过去[j]]
然后开始步骤[i，j]:= 1；f[i，j]:= past max-cost[past[j]]+coin[I，past[j]]；结束
否则开始step[i，j]:=step[i-1，past[j]]+1；f[i，j]:=f[i-1，past[j]]+coin[i，past[j]]；结束；
结束
否则开始步骤[i，j]:= 1；f[i，j]:= past max-cost[past[j]]+coin[I，past[j]]；结束；
如果f[i，j]& gt；nowmax then nowmax:=f[i，j]；
结束；
past max:= now max；
结束；
writeln(now max)；
关闭(输入)；
关闭(输出)；
结束。