noip2011普及组复赛解题思路

noip2011普及组复赛解题思路
要标准程序与基本思路,最好带注释,（第一题可以不讲）,

第二题：program stat;
var wz,wz1,tot,i:longint;
s,s1:string;
st:char;
procedure openfile;
begin
assign(input,'stat.in');
assign(output,'stat.out');
reset(input);
rewrite(output);
end;
procedure closefile;
begin
close(input);
close(output);
end;
function upp(ss:char):char;
begin
upp:=chr(ord(ss)-32);
end;
procedure init;
begin
readln(s);
for i:=1 to length(s) do
if ord(s[i])>96 then
s[i]:=upp(s[i]);
end;
procedure main;
begin
s1:='';
wz:=-1;
wz1:=0;
tot:=0;
while not eof do
begin
read(st);
if st=' ' then begin
if s1=s then begin
inc(tot);
if wz=-1 then wz:=wz1;
end;
inc(wz1,length(s1)+1);
s1:='';
end
else begin
if ord(st)>96 then st:=upp(st);
s1:=s1+st;
end;
end;
if s1=s then begin
inc(tot);
if wz=-1 then wz:=wz1;
inc(wz1,length(s1)+1);
s1:='';
end;
if tot>0 then writeln(tot,' ',wz)
else writeln('-1');
end;
begin
openfile;
init;
main;
closefile;
end.
第三题：题目分析：
首先,由于每轮比赛的次序都是由上一轮比赛完后的比分决定的,因此对于普及组的同学来说仅能使用模拟的方法来解决.容易想到的是每一轮模拟完以后快排一次,用这样的方法,时间复杂度为O((2n)*log 2n*R),根据数据范围可知这种思路仅能解决50%的数据.因此我们需要一种更有效的方式.
分析题意后可以发现,对于每一轮比赛过后,每一位选手都会有一种状态,赢了或者输了,而每一位选手比赛前都是有序的,那么对于所有在该轮比赛中赢了或者是输了的选手,都是有序的.即每轮比赛后,我们可以以O(N)的效率获得胜负选手的有序队列,对于两组有序序列,容易想到将两组数列归并,归并的效率为O(N),这样,完成一轮比赛的效率从O((2n)*log 2n*R)缩减至O(NR),根据数据范围,这样的程序是能够在1秒内出解的.
第四题：转后缀表达式＋dp,个人认为递推