Daily Archives: 8 9 月, 2012

HYSBZ 1616（纯深搜）

Posted on by

题目大意：一张图G，有一些障碍物，求路径长度一定（可环）时的路径总数

果断广搜

Program ttd;
var
   n,m,t,i,j,k,x1,x2,y1,y2:longint;
   s:string;
   b:array[0..101,0..101] of boolean;

   f:array[0..15,0..101,0..101] of longint;
begin
   readln(n,m,t);
   fillchar(b,sizeof(b),true);
   for i:=1 to n do
   begin
      readln(s);
      for j:=1 to m do if s[j]='*' then b[i,j]:=false;
   end;
   readln(x1,y1,x2,y2);
   fillchar(f,sizeof(f),0);
   f[0,x1,y1]:=1;

   for k:=1 to t do
   begin
      for i:=1 to n do
         for j:=1 to m do
            if f[k-1,i,j]>0 then
            begin
               if b[i+1,j] then inc(f[k,i+1,j],f[k-1,i,j]);
               if b[i-1,j] then inc(f[k,i-1,j],f[k-1,i,j]);
               if b[i,j+1] then inc(f[k,i,j+1],f[k-1,i,j]);
               if b[i,j-1] then inc(f[k,i,j-1],f[k-1,i,j]);



            end;


   end;
             {
   for k:=0 to t do
   begin
   for i:=1 to n do
   begin
      for j:=1 to m do
      begin
         write(f[k,i,j],' ');
      end;
      writeln;
      end;
      writeln;
   end;
            }
   writeln(f[t,x2,y2]);


end.

HYSBZ 1601(单点带值的最小生成树）

Posted on by

题目大意：最小生成树

建源点0与各点连线的权为建水库的大小。

Program aa;
var
   n,i,j,p:longint;
   u,v,w:array[0..100000] of longint;
   size,cost:longint;
   father:array[0..300] of longint;
procedure qsort(l,r:longint);
var
   i,j,m,p:longint;
begin
   i:=l;j:=r;m:=w[(l+r) shr 1];
   repeat
      while w[i]<m do inc(i);
      while w[j]>m do dec(j);
      if i<=j then
      begin
         p:=w[i];w[i]:=w[j];w[j]:=p;
         p:=u[i];u[i]:=u[j];u[j]:=p;
         p:=v[i];v[i]:=v[j];v[j]:=p;
         inc(i);dec(j);
      end;
   until i>j;
   if l<j then qsort(l,j);
   if i<r then qsort(i,r);
end;
function getfather(x:longint):longint;
begin
   if father[x]=x then exit(x);
   father[x]:=getfather(father[x]);
   exit(father[x]);
end;
begin
   read(n);
   for i:=1 to n do
   begin
      read(w[i]);
      u[i]:=0;v[i]:=i;
   end;
   size:=n;
   for i:=1 to n do
      for j:=1 to n do
      begin
        read(p);
        if i=j then continue;
        inc(size);
        u[size]:=i;v[size]:=j;w[size]:=p;
      end;


   qsort(1,size);

   cost:=0;
   for i:=0 to n do father[i]:=i;
   for i:=1 to size do
   begin
      if (getfather(u[i])<>getfather(v[i])) then
      begin
         inc(cost,w[i]);
         father[getfather(u[i])]:=father[getfather(v[i])];
      end;
   end;


   writeln(cost);


end.

HYSBZ 1599(狂枚举）

Posted on by

Description

贝西喜欢棋盘游戏和角色扮演类游戏所以她说服Farmer John把她带到玩具店，在那里，她购买了三个不同的骰子，这三个质量均匀的骰子，分别有S1,S2,S3个面。(2 <= S1 <= 20; 2 <= S2 <= 20; 2 <= S3 <= 40). 贝西掷啊掷啊掷啊，想要知道出现几率最大的和是多少。 问题给出三个骰子的面数，让你求出出现几率最大的和是多少。如果有很多种和出现的几率相同，那么就输出小的那一个。

Input

*第一行：三个由空格隔开的整数：s1,s2,s3

Output

*第一行：所要求的解

Sample Input

3 2 3

Sample Output

5





输出详解:





这里是所有可能的情况.



1 1 1 -> 3 1 2 1 -> 4 2 1 1 -> 4 2 2 1 -> 5 3 1 1 -> 5 3 2 1 -> 6



1 1 2 -> 4 1 2 2 -> 5 2 1 2 -> 5 2 2 2 -> 6 3 1 2 -> 6 3 2 2 -> 7



1 1 3 -> 5 1 2 3 -> 6 2 1 3 -> 6 2 2 3 -> 7 3 1 3 -> 7 3 2 3 -> 8



5和6出现的几率都是最大的，所以输出5.

这题枚水过……

var
   s1,s2,s3:longint;
   i,j,k:longint;
   f:array[0..100] of longint;
begin
   read(s1,s2,s3);
   fillchar(f,sizeof(f),0);
   for i:=1 to s1 do
      for j:=1 to s2 do
         for k:=1 to s3 do
         begin
            inc(f[i+j+k]);
         end;
   j:=1;
   for i:=1 to 100 do
      if f[i]>f[j] then j:=i;
   writeln(j);

end.