Codeforces Beta Round #2 解题报告

A

简单模拟题。

游戏的最大值是指游戏结束时各玩家得分的最大值，如果有多人获得最大值，则求游戏过程中最先达到或超过最大值的人。map一遍得到最大值，再map一遍就得到结果。

B

DP。

数字金字塔类型的DP。

给定一个矩阵，矩阵中的元素为非负整数，从左上角走到右下角，每次只能向下或向右走，求走过的格子中的数的乘积末尾的0的个数最少，并输出路径。

dp过程比较简单，dp[i][j][0]和dp[i][j][1]分别记录格子中的数的2、5的因子个数，每次选择小的那个格子走即可。

要注意的一点是，如果矩阵中有0，那么结果至少为1，需要特别判断一下。

dp部分代码如下：

memset(dp,0,sizeof(dp));
for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    {
        int val=mat[i][j];
        while(val%2==0)
        {
            dp[i][j][0]++;
            val/=2;
        }
        while(val%5==0)
        {
            dp[i][j][1]++;
            val/=5;
        }
        if(i || j)
        {
            dp[i][j][0]+=min(get(i-1,j,0),get(i,j-1,0));
            dp[i][j][1]+=min(get(i-1,j,1),get(i,j-1,1));
        }
    }

C

计算几何。

给定平面上的三个圆，求一点与这三个圆的视角相等，视角即该点与圆的两切线的夹角。如果存在多点，则输出视角最大的点，如不存在，则输出空行。

这题的做法可以用几何的方法硬解，套模板就行了。

我用的方法是参考Qinz大神的模拟退火法。关键在于构造一个评估函数，然后用评估函数来模拟，最终退火到最优值。这里我的评估函数是点到圆的视角的方差，模拟的起始点为三圆圆心的中心点。

#include <iostream>
#include <cmath>
using namespace std;

const double eps=1e-6;

const int dir[4][2]={{0,-1},{1,0},{0,1},{-1,0}};

struct circle
{
    double x,y,r;
}c[3];

double dist(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

double assess(double x,double y)
{
    double dif,ang[3];
    int i,j;
    for(i=0;i<3;i++)
        ang[i]=dist(x,y,c[i].x,c[i].y)/c[i].r;
    dif=0;
    for(i=0;i<3;i++)
        for(j=i+1;j<3;j++)
            dif+=(ang[i]-ang[j])*(ang[i]-ang[j]);
    return dif;
}

int main()
{
    double x,y;
    int i;
    double delta,curv,newv;
    x=y=0;
    for(i=0;i<3;i++)
    {
        scanf("%lf%lf%lf",&c[i].x,&c[i].y,&c[i].r);
        x+=c[i].x;
        y+=c[i].y;
    }
    x/=3;
    y/=3;
    delta=1;
    while(delta>eps)
    {
        curv=assess(x,y);
        for(i=0;i<4;i++)
        {
            newv=assess(x+delta*dir[i][0],y+delta*dir[i][1]);
            if(curv>newv)
            {
                curv=newv;
                break;
            }
        }
        if(i==4)
            delta*=0.85;
        else
        {
            x+=delta*dir[i][0];
            y+=delta*dir[i][1];
        }
    }
    if(assess(x,y)<eps)
        printf("%.5lf %.5lf\n",x,y);
    return 0;
}