用户:Shmetrofans/OI

NOIP 2012 解题报告

质因数分解

program prime;
var
 i,n,k,ans:longint;
begin
 assign(input,'prime.in');
 reset(input);
 assign(output,'prime.out');
 rewrite(output);
 read(n);
 i:=3;
 if n mod 2=0 then i:=2
 else while n mod i<>0 do i:=i+2;
 write(n div i);
 close(input);
 close(output);
end.

寻宝

program treasure;
var
 f,p:array [1..10005,0..105] of longint;
 n,m,i,j,k,start,ans:longint;
function getpos(c,x,k:longint):longint;
var
 i,j,all:longint;
begin
 all:=0;
 for i:= 0 to m-1 do
  if f[c,i]=1 then inc(all);
 k:= k mod all;
 if k=0 then k:=all;
 j:=0;
 i:=x;
 while true do
  begin
   if f[c,i]=1 then inc(j);
   if j=k then exit(i);
   i:= (i+1) mod m;
  end;
end;
begin
 assign(input,'treasure.in');
 reset(input);
 assign(output,'treasure.out');
 rewrite(output);
 readln(n,m);
 for i:= 1 to n do
  for j:= 0 to m-1 do
   readln(f[i,j],p[i,j]);
 read(start);
 ans:=0;
 for i:=1 to n do
  begin
   ans:=(ans+p[i,start]) mod 20123;
   start:=getpos(i,start,p[i,start]);
  end;
 write(ans);
 close(input);
 close(output);
end.

摆花

program flower;
var
 f:array[0..105,0..105] of longint;
 n,m,k,c,i,j:longint;
begin
 assign(input,'flower.in');
 reset(input);
 assign(output,'flower.out');
 rewrite(output);
 readln(n,m);
 fillchar(f,sizeof(f),0);
 f[0,0]:=1;
 for i:= 1 to n do
  begin
   read(k);
   for j:= 0 to k do
    for c:= 0 to m do
     begin
      if c<j then continue;
      f[i,c]:=(f[i,c]+f[i-1,c-j]) mod 1000007;
     end;
  end;
 write(f[n,m]);
 close(input);
 close(output);
end.

文化之旅

program culture;
type
 edge= record
 p,cost,next:longint;
 end;
var
 e:array[1..20005] of edge;
 n,k,m,s,t:longint;
 dist,wh,map:array[1..105] of longint;
 f:array[1..100,1..100]  of longint;
 vist:array[1..100] of boolean;
 eq:array[1..100] of longint;
 h,r,count,now,next,p:longint;
 i,j,all,x,y,z:longint;
 atk:array[1..100,1..100] of longint;
 flag:boolean;
procedure insert(x,y,c:longint);
begin
 all:=all+1;
 e[all].p:=y;
 e[all].next:=map[x];
 e[all].cost:=c;
 map[x]:=all;
end;
function find(k,x:longint):longint;
begin
 if f[k,x]=x then exit(x);
 exit(find(k,f[k,x]));
end;
procedure union(k,x,y:longint);
var
 a,b:longint;
begin
 a:=find(k,x);
 b:=find(k,y);
 if a<>b then f[a]:=f[b];
end;
begin
 assign(input,'culture.in');
 reset(input);
 assign(output,'culture.out');
 rewrite(output);
 readln(n,k,m,s,t);
 for i:= 1 to n do read(wh[i]);
 readln;
 for i:= 1 to k do
  begin
   for j:= 1 to k do read(atk[i,j]);
   readln;
  end;
 all:=0;
 fillchar(map,sizeof(map),0);
 for i:= 1 to m do
  begin
   readln(x,y,z);
   insert(x,y,z);
   insert(y,x,z);
  end;
 for i:= 1 to k do f[s,i]:=i;
 fillchar(dist,sizeof(dist),$1f);
 dist[s]:=0;
 fillchar(vist,sizeof(vist),false);
 h:=1;
 r:=1;
 count:=1;
 eq[1]:=s;
 vist[s]:=true;
 while count<>0 do
  begin
   now:=eq[h];
   h:=h+1;
   if h>n then h:=1;
   count:=count-1;
   vist[now]:=false;
   next:=map[now];
   while next<>0 do
    begin
     p:=e[next].p;
     flag:=true;
     for i:= 1 to k do
      if atk[wh[p],i]=1 then
       if find(now,wh[i]) = find(now,wh[s]) then
        begin
         flag:=false;
         break;
        end;
     if flag then
      begin
       if dist[p]>dist[now]+e[next].cost then
        begin
         dist[p]:=dist[now]+e[next].cost;
         f[p]:=f[now];
         union(p,wh[s],wh[p]);
         if not vist[p] then
          begin
           inc(r);
           if r>n then r:=1;
           count:=count+1;
           eq[r]:=p;
           vist[p]:=true;
          end;
        end;
      end;
     next:=e[next].next;
    end;
  end;
 if dist[t]=522133279 then write(-1)
 else write(dist[t]);
 close(input);
 close(output);
end.