Author Archives: nike0good

HYSBZ 1050(队列-大小边比值最大的路径）

Posted on by

已知边，判断2点连通性

要用并查集……千万别搜啊~

Program ee;
var
   edge:array[1..10000,1..3] of longint;
   s,t,n,m,i,j,pmax,pmin:longint;
   father:array[1..1000] of longint;

procedure swap(var a,b:longint);
var
   p:longint;
begin
   p:=a;
   a:=b;
   b:=p;
end;
procedure qsort(l,r:longint);
var
   i,j,m,p:longint;
begin
   i:=l;
   j:=r;
   m:=edge[(l+r) shr 1,3];
   repeat
      while edge[i,3]<m do inc(i);
      while edge[j,3]>m do dec(j);
      if i<=j then
      begin
         swap(edge[i,1],edge[j,1]);
         swap(edge[i,2],edge[j,2]);
         swap(edge[i,3],edge[j,3]);
         inc(i);dec(j);
      end;
   until i>j;
   if l<j then qsort(l,j);
   if i<r then qsort(i,r);

end;
function gcd(a,b:longint):longint;
begin
   if b=0 then exit(a) else exit(gcd(b,a mod b));
end;
function getfather(x:longint):longint;
begin
   if father[x]=x then exit(x) else father[x]:=getfather(father[x]);
   exit(father[x]);
end;
begin
   pmax:=50000000;pmin:=1;
   read(n,m);
   for i:=1 to m do read(edge[i,1],edge[i,2],edge[i,3]);
   read(s,t);
   qsort(1,m);
   i:=1;

   for i:=1 to m do
   begin
      for j:=1 to n do father[j]:=j;
      j:=i;
      while (getfather(s)<>getfather(t)) and (j<=m) do
      begin
         if getfather(edge[j,2])<>getfather(edge[j,1]) then father[father[edge[j,2]]]:=father[father[edge[j,1]]];
         inc(j);
      end;
      if getfather(s)=getfather(t) then
      begin
         dec(j);
         if (pmax/pmin>edge[j,3]/edge[i,3]) then
         begin
            pmax:=edge[j,3];
            pmin:=edge[i,3];
         end;
      end;

   end;



   if pmax=50000000 then writeln('IMPOSSIBLE')
   else if (pmax mod pmin=0) then writeln(pmax div pmin)
   else
   begin
      i:=gcd(pmax,pmin);
      pmax:=pmax div i;pmin:=pmin div i;
      writeln(pmax,'/',pmin);
   end;

end.

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.

POJ 2388(中位数）

Posted on by

求一组数的中位数

巨羡慕C党有sort用

Program P2388;
var
   n,i,j:longint;
   a:array[1..10010] of longint;
Procedure qsort(l,r:longint);
var
   i,j,m,p:longint;
begin
   i:=l;
   j:=r;
   m:=a[(l+r) shr 1];
   repeat
      while a[i]<m do inc(i);
      while a[j]>m do dec(j);
      if i<=j then
      begin
         p:=a[i];a[i]:=a[j];a[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;
begin
   read(n);
   for i:=1 to n do read(a[i]);
   qsort(1,n);
   writeln(a[(1+n) shr 1]);
end.

POJ 2299(逆序对数）

Posted on by

水题 裸的求逆序对数

Program P2299;
const
   maxn=500100;
Var
   tt,i,j,k,n:longint;
   a,le,re:array[1..maxn] of longint;
   ans:int64;
procedure mergesort(l,r:longint);
var
   i,j,k,mid:longint;

begin
   if l=r then exit;
   mid:=(l+r) shr 1;
   mergesort(l,mid);
   mergesort(mid+1,r);
   for i:=l to mid do le[i-l+1]:=a[i];
   le[mid+2-l]:=maxlongint;
   for i:=mid+1 to r do re[i-mid]:=a[i];
   re[r+1-mid]:=maxlongint;
   i:=1;j:=1;
   for k:=l to r do
   begin
      if (le[i]<=re[j]) then
      begin
         a[k]:=le[i];
         inc(i);
      end
      else
      begin
         a[k]:=re[j];
         inc(j);
         ans:=mid-l+1-(i-1)+ans;
      end;
   end;
end;
Begin
   while not eof do
   begin
      read(n);
      if n=0 then break;
      for i:=1 to n do read(a[i]);
      ans:=0;
      mergesort(1,n);
      writeln(ans);

   end;
end.

POJ 1804（最小相邻数移动）

Posted on by

题目大意：对乱序列相邻2数移动，使得用最小步数使其有序

解法：归并排序

定理：

一个乱序序列的逆序数 = 在只允许相邻两个元素交换的条件下,得到有序序列的交换次数

Program P1804;
const
   maxn=1000;
Var
   tt,i,j,k,n,ans:longint;
   a,le,re:array[1..maxn] of longint;

procedure mergesort(l,r:longint);
var
   i,j,k,mid:longint;

begin
   if l=r then exit;
   mid:=(l+r) shr 1;
   mergesort(l,mid);
   mergesort(mid+1,r);
   for i:=l to mid do le[i-l+1]:=a[i];
   le[mid+2-l]:=maxlongint;
   for i:=mid+1 to r do re[i-mid]:=a[i];
   re[r+1-mid]:=maxlongint;
   i:=1;j:=1;
   for k:=l to r do
   begin
      if (le[i]<=re[j]) then
      begin
         a[k]:=le[i];
         inc(i);
      end
      else
      begin
         a[k]:=re[j];
         inc(j);
         inc(ans,mid-l+1-(i-1));
      end;
   end;
end;
Begin
   readln(tt);
   for k:=1 to tt do
   begin
      writeln('Scenario #',k,':');
      read(n);
      for i:=1 to n do read(a[i]);
      ans:=0;
      mergesort(1,n);
      writeln(ans);



      writeln;
   end;
end.

POJ 1868(等差数列）

Posted on by

暴力模拟无算法

Program P1868;
Var
   c:char;
   n,i,j,k:longint;
   a:array[0..10000] of longint;
function is_ant:boolean;
var
   i,j,k:longint;
begin
   for k:=1 to n shr 2 do
      for i:=1 to n-k shl 1-1 do
         if ((a[i]<a[i+k]) and (a[i+k]<a[i+2*k])) or ((a[i]>a[i+k]) and (a[i+k]>a[i+2*k])) then exit(false);




   exit(true);
end;
Begin
   while true do
   begin
      read(c);
      if c='0' then break;
      val(c,n);
      repeat
         read(c);
         if c=':' then break;
         n:=n*10+ord(c)-48;
      until false;
      for i:=1 to n do
      begin
         read(j);
         a[j]:=i;
      end;

      if is_ant then writeln('yes') else writeln('no');

      readln;

   end;
end.

POJ 1088（滑雪）

Posted on by

标准记忆化搜索 模板题

Program P1088;
var
   ans,n,m,i,j:longint;
   a,f:array[0..101,0..101] of longint;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;
function dfs(x,y:longint):longint;
var
   i,j:longint;
begin
   if f[x,y]>0 then exit(f[x,y]);
   dfs:=0;
   if a[x-1,y]<a[x,y] then dfs:=max(dfs,dfs(x-1,y)+1);
   if a[x+1,y]<a[x,y] then dfs:=max(dfs,dfs(x+1,y)+1);
   if a[x,y-1]<a[x,y] then dfs:=max(dfs,dfs(x,y-1)+1);
   if a[x,y+1]<a[x,y] then dfs:=max(dfs,dfs(x,y+1)+1);
   f[x,y]:=dfs;
end;
begin
   read(n,m);
   fillchar(a,sizeof(a),127);
   for i:=1 to n do
      for j:=1 to m do
         read(a[i,j]);
   fillchar(f,sizeof(f),0);
   ans:=0;

   for i:=1 to n do
      for j:=1 to m do
      begin
         if f[i,j]=0 then ans:=max(ans,dfs(i,j));
      end;
   writeln(ans+1);
end.

POJ 1830（位运算+双向DFS）

Posted on by

此题也可用GE做，可是我不会矩阵乘法……

Program P1830;
const
   maxn=28;
   maxf=100007;
   none=-2139062144;
var
   ans,tt,n,i,j,s,t,mid:longint;
   b:array[1..29] of longint;
   h,num:array[0..maxf] of longint;

function hash(x:longint):longint;
var
   i,j:longint;
begin
   hash:=x mod maxf;
   while (num[hash]<>x) and (num[hash]<>none) do
   begin
      hash:=(hash+1) mod maxf;
   end;
   num[hash]:=x;
   exit(hash);
end;
procedure dfs(x,l:longint);
var
   i,j:longint;
begin
   if l=mid+1 then
   begin
      inc(h[hash(x)]);
      exit;
   end;
   for i:=l to mid do
      dfs(x xor b[i],i+1);
   dfs(x,mid+1);

end;
procedure find(x,l:longint);
var
   i,j:longint;
begin
   if l=n+1 then
   begin
      inc(ans,h[hash(x)]);
      exit;
   end;
   for i:=l to n do
      find(x xor b[i],i+1);
   find(x,n+1);

end;

begin
   read(tt);
   while (tt>0) do
   begin
      ans:=0;
      fillchar(b,sizeof(b),0);
      fillchar(num,sizeof(num),128);
      fillchar(h,sizeof(h),0);

      read(n);
      s:=0;
      for i:=1 to n do
      begin
         read(j);
         if j=1 then inc(s,1 shl (i-1));
      end;
      t:=0;
      for i:=1 to n do
      begin
         read(j);
         if j=1 then inc(t,1 shl (i-1));
      end;
      while (true) do
      begin
         read(i,j);
         if (i=0) and (j=0) then break;
         inc(b[i],1 shl (j-1));
      end;
      for i:=1 to n do inc(b[i],1 shl (i-1));
      mid:=n shr 1;
      dfs(s,1);
      find(t,mid+1);
      if ans=0 then writeln('Oh,it''s impossible~!!') else
      writeln(ans);
      dec(tt);
   end;
end.