NOIP2011普及组解题报告
——ahbbzeq 2011.11.25 转载请注明来源
一、数字反转
没得满分只能说明一个问题，你的程序写的太少了。
[delphi]
program reverse;
var
s:string;
i,sta:longint;
begin
assign(input,’reverse.in’);reset(input);
assign(output,’reverse.out’);rewrite(output);
readln(i);
str(i,s);
sta:=1;
if s[1]=’-‘ then
begin
write(‘-‘);
sta:=2;
end;
i:=length(s);
while (s[i]=’0’) and (i>sta) do
dec(i);
while (i>=sta) do
begin
write(s[i]);
dec(i);
end;
close(input);close(output);
end.
[/delphi]
二、统计单词个数
考你的基本功，和对程序的理解，尤其是细节上的优化。直接在文章中选出单词，与给定单词长度一致时才比较，函数传参数时也不要传字符串（会很慢的，具体慢多少没试）。
[delphi]
program stat;
var
s,p:ansistring;
i,j,first,num,len,c,k:longint;
function cmp(x:longint):boolean;
var
i:longint;
begin
for i:= 1 to c do
if s[i]<> p[x+i-1] then exit(false);
exit(true);
end;
begin
assign(input,’stat.in’);reset(input);
assign(output,’stat.out’);rewrite(output);
readln(s);readln(p);
s:=upcase(s);p:=upcase(p);
c:=length(s); len:=length(p);
i:=1; num:=0; first:=-1;
while (s[i]=’ ‘)and (i<=len) do inc(i);
while (i<=len) do
begin
j:=i+1;
while (p[j]<>‘ ‘) and (j<=len) do
inc(j);
if (j-i = c) and cmp(i) then
begin
if first=-1 then first:=i;
inc(num);
end;
i:=j; while (p[i]=' ') and (i<=len) do inc(i);
end;
if first=-1 then
writeln(-1)
else writeln(num,' ',first-1);
close(input);close(output);
end.
[/delphi]
三、瑞士轮
实践证明，如果单纯的排序r次，必然结果是超时。事实上只需一次真正意义上的排序以后，在以后的比赛中，按原顺序分成两组，获胜组和失败组，这两组依然是有序的，再把这两组归并成一组，就可以了。总时间复杂度O（N*R）。 为了方便归并，下面的数组采用了滚动数组。
[delphi]
program swiss_merger;
var
n,r,q,i,j,k,c,pwin,plose:longint;
s,w,t:array[1..200050] of longint;
id:array[0..1,1..200050] of longint;
procedure qsort(n,m:longint);
var
i,j,k,t:longint;
begin
i:=n;j:=m; k:= id[0,(n+m)div 2];
repeat
while (s[id[0,i]] > s[k]) or (s[id[0,i]]=s[k]) and (id[0,i]
if i<=j then
begin
t:=id[0,i]; id[0,i]:=id[0,j];id[0,j]:=t;
inc(i); dec(j);
end;
until i>j;
if n
{ * } (‘<','>‘,’>’,’>’),
{ ) } (‘>’,’>’,’>’,’>’));
var
stack_op:array[1..maxn] of char;
stack_data0,stack_data1:array[1..maxn] of longint;
n,top_op,top_data,i,len:longint;
a0,a1,b0,b1,t0,t1:longint;
s:ansistring;
ch,now:char;
procedure push_op(ch:char);
begin
inc(top_op);
stack_op[top_op]:=ch;
end;
function pop_op:char;
begin
pop_op:= stack_op[top_op];
dec(top_op);
end;
function gettop:char;
begin
gettop:=stack_op[top_op];
end;
procedure push_data(a0,a1:longint);
begin
inc(top_data);
stack_data0[top_data]:=a0;
stack_data1[top_data]:=a1;
end;
procedure pop_data(var a0,a1:longint);
begin
a0:=stack_data0[top_data];
a1:=stack_data1[top_data];
dec(top_data);
end;
function find(ch:char):integer;
var
i:longint;
begin
for i:= 1 to 4 do
if op[i]=ch then exit(i);
end;
begin
assign(input,’exp.in’);reset(input);
assign(output,’exp.out’);rewrite(output);
top_op:=0; top_data:=0;
push_op(‘(‘); push_data(1,1);
readln(n);
readln(s); s:=s+’)’;
len:=length(s);
i:=1;
while i<=len do
begin
if i=22 then
readln;
case flag[find(gettop),find(s[i])] of
// begin
'<': begin push_op(s[i]); if (s[i]<>‘(‘) then push_data(1,1); inc(i); end;
‘=’: begin now:=pop_op; inc(i); end;
‘>’: begin
pop_data(a0,a1); pop_data(b0,b1);
now:=pop_op;
if now=’+’ then
begin
t0:= (a0*b0) mod 10007;
t1:= ( (a0*b1) mod 10007 +(a1*b1) mod 10007 + (a1*b0) mod 10007) mod 10007;
push_data(t0,t1);
end
else
begin
t0:= ( (a0*b1) mod 10007 + (a1*b0) mod 10007 + (a0 * b0) mod 10007 ) mod 10007;
t1:= (a1*b1) mod 10007;
push_data(t0,t1);
end;
end;
end;
end;
writeln(stack_data0[top_data]);
close(input); close(output);
end.
[/delphi]