posts - 64, comments - 4, trackbacks - 0, articles - 0

codeforces36#

Posted on 2010-10-19 23:21 acronix 阅读(249) 评论(0)  编辑 收藏 引用 所属分类: hzshuai解题报告hzshuai的codeforces
problem A
      水题不解释.
problem B
     题意还是见:http://codeforces.com/contest/36/problem/B
    做法是不断递归白色的区域,直到此区域的len == n。
cpp代码:
#include <cstdio>
#include 
<stdlib.h>

char a[5][5],mp[300][300];
int
 n,k;

void Orig(int x,int
 y)
{
   
//  printf("Orig: x = %d,y = %d\n",x,y);

     for (int i = 0; i < n; i++)
     {
         
for (int j = 0; j <  n; j++
)
         {
            mp[x
+i][y+j] =
 a[i][j]; 
           
// printf("%d,%d--%c",x+i,y+j,a[i][j]);

         } 
        
// printf("\n");

     }
         
}

void Black(int len,int x,int
 y)
{
    
// printf("Black:len = %d,x = %d,y = %d\n",len,x,y);

     for (int i = x; i < len + x; i++)
         
for (int j = y; j < len + y; j++
)
             mp[i][j] 
= '*'
;
}

void paint(int len,int i,int
 j)
{
     
if (len ==
 n)
        Orig(i,j);
     
else
 {
             
int cnt = len /
 n;
             
for (int x = 0; x < n; x++
)
                 
for (int y = 0; y < n; y++
)
                     
if (a[x][y] == '*'
)
                        Black(cnt,i
+cnt*x,j+cnt*
y);
                     
else paint(cnt,i+cnt*x,j+cnt*
y);
          }
}

int myPow(int n,int
 k)
{
    
int m = 1
;
    
while (k > 0
)
    {
          m 
*=
 n;
          k
--
;
    }      
    
return
 m;
}

int
 main()
{
    
int
 i,j;
    freopen(
"input.txt","r"
,stdin);
    freopen(
"output.txt","w"
,stdout);
    
while (scanf("%d %d",&n,&k) !=
 EOF)
    {
          
int len =
 myPow(n,k);
          
          
for (i = 0; i < n; i++
)
              scanf(
"%s"
,a[i]);
          paint(myPow(n,k),
1,1
);
          
for (i = 1; i <= len; i++
)
          {
              
for (j = 1; j <= len; j++
)
                  printf(
"%c"
,mp[i][j]);
              printf(
"\n"
);
          }
         
// /*********/printf("----------------\n\n");

    }
    
    
return 0
;
}

problem C
      题见:http://codeforces.com/contest/36/problem/C
     我觉得这是一个比较好的题。首先,需要必要的数学知识就是相似三角形各边的比例关系。然后,就是判断每来一个碗时它会在哪个碗之上?比赛时我没时间想明白后来看了xpree的代码后猛然发觉,其实可以枚举前面放过的碗中每个碗可以使来的碗  i 有一个 上升的高度up[i],求up[i] + h[j]最大值即可。枚举O(n*n)的。这给我的收获就是:在不确定的情况下,枚举是最好的方法,类似动态规划很多时候都是用这个思想,然后得到下一个最优子结构。
     接下来的问题就是求两碗之间的碗底高度差了,这里 i 代表放过的碗,j 代表要放的碗,情况就是三类:1、r[j] >= R[i] 就是j 在 i 的顶部:2、j 能完全i内,高度差为0:2、j 卡在 i 中间或 i 内部。具体的情况自己画画图就明白了;
  CPP代码:
#include <cstdio>
#include 
<cstdio>
#include 
<algorithm>
using namespace std;

const double eps = 1e-8
;
const int MAX = 3005
;
double  r[3005],R[3005],h[3005],up[3005],k[3005
];

double cmp(int i,int
 j)
{
       
if (R[i] <= r[j])// j 在 i 顶部 

          return h[i];
          
       
if (r[i] > r[j]) // j 完全在 i 内部,两者碗底的高度差为 0 

       {
           
if (k[j] <
 k[i] )
              
return 0
;
           
if (h[i] <= h[j] && (h[i]*(R[j]-r[j])/h[j] + r[j]) <=
 R[i])
              
return 0
;
           
if (h[i] >= h[j] && (h[j]*(R[i]-r[i])/h[i] + r[i]) >=
 R[j])
              
return 0
;
       }
       
if (k[j] > k[i]) // j 卡在 i 中 

          {
                 
if (R[j] >=
 R[i])
                    
return h[i] - (R[i]-r[j])*h[j]/(R[j] -
 r[j]);
                 
else return (R[j]-r[i])*h[i]/(R[i]-r[i]) -
 h[j];
            }
       
else return h[i]*(r[j]-r[i])/(R[i]-
r[i]);
}

int
 main()
{
    freopen(
"input.txt","r"
,stdin);
    freopen(
"output.txt","w"
,stdout);
    
    
int
 n,i,j;
    
double
 ans,d;
    
while (scanf("%d",&n) !=
 EOF)
    {
          
for (i = 1; i <= n; i++
)
          {
              up[i] 
= 0
;
              scanf(
"%lf %lf %lf",&h[i],&r[i],&
R[i]);
              k[i] 
= (R[i] - r[i]) /
 h[i];
          }
          ans 
= 0
;
          
for (i = 1; i <= n; i++
)
          {
              
//枚举 i 之前的碗,看 i 会在 那个上面 

              for (j = 1; j < i ; j++)
              {
                  d 
=
 cmp(j,i);
               
//   printf("i = %d,j = %d,d = %lf\n",i,j,d);

                  up[i] = max(up[i],up[j]+d);     
              }
//printf("ans = %lf\n",ans);

              ans = max(ans,up[i]+h[i]);
              
          }
          printf(
"%.8lf\n"
,ans);
              
    }
    
return 0
;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理