2010年10月25日 總結

額...昨天有事，今早更新

今天是星期一，嗯嗯，為什麼昨天沒有呢？

答客曰：星期天休息...XD（衆人：CF！！！）

好，今天的呢，有7道題：

誰拿了最多獎學金

過河

拔河比賽

數的計算

過河卒

不高興的津津

FBI樹

誰拿了最多獎學金：基本的字元串處理。分析略...

var

s:string;

n,i,p,q,total,max,maxi,code:longint;

node:array[1..100]of

record

name:string;

qm,py,lw,mo:longint;

gb,xb:char;

end;

begin

readln(n);

total:=0;max:=0;

for i:=1 to n do

with node[i] do

begin

readln(s);

p:=pos(' ',s);

name:=copy(s,1,p-1);

inc(p);

q:=p;

while s[q]<>' ' do inc(q);

val(copy(s,p,q-p),qm,code);

inc(q);

p:=q;

while s[q]<>' ' do inc(q);

val(copy(s,p,q-p),py,code);

gb:=s[q+1];xb:=s[q+3];

q:=q+5;

val(copy(s,q,length(s)-q+1),lw,code);

mo:=0;

if (qm>80)and(lw>=1)then inc(mo,8000);

if (qm>85)and(py>80)then inc(mo,4000);

if qm>90 then inc(mo,2000);

if (qm>85)and(xb='Y')then inc(mo,1000);

if (py>80)and(gb='Y')then inc(mo,850);

if mo>max then begin max:=mo;maxi:=i;end;

inc(total,mo);

end;

writeln(node[maxi].name);

writeln(node[maxi].mo);

writeln(total);

end. 

過河：比較經典的一道壓縮狀态的DP，石子是很稀疏的，每次跳的最大距離又很小，是以把大于100的空隙合并就好了，其餘的都是些調試了。

var

l:longint;

s,t,m:integer;

stone:array[0..100]of longint;

st:array[0..100]of longint;

a:array[1..10000]of shortint;

f:array[0..10000]of longint;

i,j,k,min:longint;

begin

readln(l);

readln(s,t,m);

for i:=1 to m do read(stone[i]);

if s=t then

begin

k:=0;

for i:=1 to m do

if stone[i] mod s=0 then inc(k);

writeln(k);

halt;

end;

for i:=1 to m-1 do

for j:=i to m do

if stone[i]>stone[j] then

begin

k:=stone[i];

stone[i]:=stone[j];

stone[j]:=k;

end;

stone[0]:=0;st[0]:=0;

for i:=1 to m do

if stone[i]-stone[i-1]>=100 then

st[i]:=st[i-1]+100

else

st[i]:=st[i-1]+stone[i]-stone[i-1];

fillchar(a,sizeof(a),0);

for i:=1 to m do

a[st[i]]:=1;

l:=st[m];

f[0]:=0;

for i:=1 to l+t do

if i>=s then

begin

min:=maxlongint;

for j:=i-t to i-s do

if j>=0 then

if f[j]<min then min:=f[j];

f[i]:=min+a[i];

end

else f[i]:=10000;

min:=f[l];

for i:=1 to t do

if f[i+l]<min then min:=f[i+l];

writeln(min);

end.

拔河比賽：灰常強大的01背包...一般人看不出來，當然我也是看了題解之後才幡然醒悟...

把總的體重分成兩半，然後把體重看作是重量的價值，去裝填那個背包，剩下的再乘以2就是最終的結果了。

program rq72;

var

c:array[1..100]of integer;

f:array[0..10000]of integer;

i,j,n,sum,sum2,ans:integer;

begin

sum:=0;

fillchar(f,sizeof(f),0);

readln(n);

for i:=1 to n do

begin

readln(c[i]);

inc(sum,c[i]);

end;

sum2:=sum div 2;

for i:=1 to n do

for j:=sum2 downto c[i] do

if f[j]<f[j-c[i]]+c[i] then

f[j]:=f[j-c[i]]+c[i];

writeln(sum-f[sum2]*2);

end. 

數的計算：兩種方法。

解法一：枚舉暴搜，反正在我現在用的這台電腦上是A不掉的，不過交到RQ上AC了。

program rq153;

var

n,i,ans:longint;

procedure dfs(x:longint);

var i:longint;

begin

inc(ans);

for i:=1 to x div 2 do

dfs(i);

end;

begin

readln(n);

ans:=1;

for i:=1 to n div 2 do

dfs(i);

writeln(ans);

end. 

解法二：DP，這樣才行嘛...

program rq153_2;

var

n,i,j:longint;

f:array[1..1000]of longint;

begin

f[1]:=1;

readln(n);

for i:=2 to n do

begin

for j:=1 to i div 2 do

inc(f[i],f[j]);

inc(f[i]);

end;

writeln(f[n]);

end. 

過河卒：典型的DP，不解釋。

program rq69;

var

map:array[-2..22,-2..22]of integer;

s:array[-1..20,-1..20]of extended;

i,j,m,n,x,y:longint;

begin

readln(n,m,x,y);

fillchar(map,sizeof(map),0);

map[x,y]:=-1;

map[x+2,y+1]:=-1;

map[x+1,y+2]:=-1;

map[x-1,y+2]:=-1;

map[x-2,y+1]:=-1;

map[x-2,y-1]:=-1;

map[x-1,y-2]:=-1;

map[x+1,y-2]:=-1;

map[x+2,y-1]:=-1;

map[0,0]:=-1;

s[0,0]:=1;

for i:=0 to n do

for j:=0 to m do

if map[i,j]<>-1 then

s[i,j]:=s[i-1,j]+s[i,j-1];

writeln(s[n,m]:0:0);

end.

不高興的津津：不解釋。

program rq20;

var

a,b,i,k:longint;

begin

for i:=1 to 7 do

begin

readln(a,b);

if a+b>8 then begin writeln(i);halt;end;

end;

writeln(0);

end.

FBI樹：遞歸啦。

program rq21;

var

n,i:longint;

s:ansiansistring;

function f(s:ansistring):char;

var i:longint;

begin

i:=1;

while (s[i]=s[1])and(i<=length(s)) do inc(i);

if i>length(s) then

begin

if s[1]='0'then exit('B');

if s[1]='1'then exit('I');

end;

exit('F');

end;

function work(s:ansistring):ansistring;

begin

if length(s)=1 then exit(f(s));

exit(work(copy(s,1,length(s)div 2))+work(copy(s,length(s)div 2+1,length(s)div 2))+f(s));

end;

begin

readln(n);

readln(s);

writeln(work(s));

end.

2010年10月26日11:31:46