Noip2007解题报告

第一题：scholar
这个题没什么特别的，主要考察大家对编程的熟练程度。可用二维数组a的a[1,i]记录下语文成绩，再用a[1,i]、a[3,i]记录总分、编号。因为数据最多就300个，所以排序可以用冒泡。在排序时可以将序号也排序，方便控制下标。
我的程序如下：
program scholar(input,output);
var
n,x,y,z,i,j:integer;
a:array[1..300,1..3] of integer;
procedure swap(var a,b:integer);
var
s:integer;
begin
s:=a;
a:=b;
b:=s;
end;
begin
assign(input,'scholar.in');
assign(output,'scholar.out');
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do
begin
readln(x,y,z);
a[i,1]:=i;
a[i,2]:=x;
a[i,3]:=x+y+z;
end;
for i:=1 to n-1 do
for j:=i+1 to n do
if (a[i,3]a[j,1]) and (a[i,3]=a[j,3]) and (a[i,2]=a[j,2])) then
begin
swap(a[i,1],a[j,1]);
swap(a[i,2],a[j,2]);
swap(a[i,3],a[j,3]);
end;
for i:=1 to 5 do
writeln(a[i,1],' ',a[i,3]);
close(input);
close(output);
end.
第二题：group
这题也不难，有许多人把它想成了DP，其实就是简单的模拟。先排序（也可用冒泡），然后用2个指针控制下标，每次把第一个（头指针对应数据）和最后一个（尾指针对应数据）相加。若比W大则将计数器加1，同时后移头指针；若比小于等于W，则计数器加1，同时将头指针后移1位，尾指针前移1位。最后输出计数器结果。
程序如下：
program group(input,output);
var
a:array[1..30000] of integer;
w,n,i,j,s:integer;
procedure qsort(h,t:integer);
var
p,i,j:integer;
begin
i:=h;
j:=t;
p:=a;
repeat
while (a[j]>p) and (j>i) do j:=j-1;
if j>i then
begin
a:=a[j];
i:=i+1;
while (a if i begin
a[j]:=a;
j:=j-1;
end;
end;
until i=j;
a:=p;
i:=i+1;
j:=j-1;
if i if j>h then qsort(h,j);
end;
begin
assign(input,'group.in');
assign(output,'group.out');
reset(input);
rewrite(output);
readln(w);
readln(n);
for i:=1 to n do readln(a);
qsort(1,n);
i:=1;
j:=n;
s:=0;
while i<=j do
begin
if i=j then
begin
s:=s+1;
break;
end;
if a+a[j]<=w then
begin
i:=i+1;
j:=j-1;
s:=s+1;
end;
if a+a[j]>w then
begin
s:=s+1;
j:=j-1;
end;
end;
writeln(s);
close(input);
close(output);
end.
第三题：escape
没必要用什么DP，还是用模拟。因为魔法值每次移动就消耗10，每秒补4，而且每移动一次也要耗1秒（有些人这个没注意）。经过比较得知，用魔法移动比跑步要快，所以我们尽量用魔法，先判断“Yes”和“No”，再求相应数据即可。
程序如下：
program escape(input,output);
var
a,b:array[0..10000]of longint;
m,s,t,i,j:longint;
function max(a,b,c:longint):longint;
var
k:longint;
begin
if a>b then k:=a else k:=b;
if k max:=k;
end;
begin
assign(input,'escape.in');
assign(output,'escape.out');
reset(input);
rewrite(output);
readln(m,s,t);
for i:=0 to 10000 do
begin
a[i]:=0;
b[i]:=0;
end;
for i:=1 to t do
begin
for j:=0 to 9 do
begin
b[j]:=max(a[j]+17,a[j+4],0);
if b[j]>=s then
begin
writeln('Yes');
writeln(i);
close(input);
close(output);
halt;
end;
end;
for j:=10 to m do
begin
b[j]:=max(a[j]+17,a[j+4],a[j-10]+60);
if b[j]>=s then
begin
writeln('Yes');
writeln(i);
close(input);
close(output);
halt;
end;
end;
a:=b;
end;
writeln('No');
writeln(a[m]);
close(input);
close(output);
end.
第四题：hanoi
典型的汉诺塔问题。只不过乘了个2。我们不需要推An与An-1的递推关系式，推An与n的关系就行了。汉诺单塔的关系式是：An=2^n-1。这里乘2，得：An=2*(2^n)-1，化简，得：An=2^(n+1)-2。用个高精度就行了。
程序如下：
program hanoi(input,output);
var
n,i,j:integer;
a:array[1..100] of 0..9;
procedure ppp(k:integer);
var
i,j,w,s:integer;
begin
a[1]:=1;
w:=0;
for i:=1 to k do
for j:=1 to 100 do
begin
s:=a[j]*2+w;
a[j]:=s mod 10;
w:=s div 10;
end;
end;
begin
assign(input,'hanoi.in');
assign(output,'hanoi.out');
reset(input);
rewrite(output);
readln(n);
ppp(n+1);
if a[1]>=2 then
a[1]:=a[1]-2
else
begin
a[1]:=a[1]+8;
a[2]:=a[2]-1;
end;
i:=100;
while a[i]=0 do i:=i-1;
for j:=i downto 1 do write(a[j]);
writeln;
close(input);
close(output);
end.