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;
}