Monthly Archives: 9 月 2012

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.