Codeforces Beta Round #2

A题，神题意题。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;
vector<string> ve;
map<string,int>mp;
map<string,int>mz;
int p[1001];
int main()
{
    int n,maxz,i;
    string str;
    cin>>n;
    for(i = 0;i < n;i ++)
    {
        cin>>str>>p[i];
        mp[str] = 0;
        mz[str] = 0;
        ve.push_back(str);
    }
    for(i = 0;i < n;i ++)
    {
        mp[ve[i]] += p[i];
    }
    for(map<string,int>::iterator it = mp.begin();it != mp.end();it ++)
    {
        maxz = max(maxz,it->second);
    }
    for(i = 0;i < n;i ++)
    {
        mz[ve[i]] += p[i];
        if(mz[ve[i]] >= maxz&&mp[ve[i]] == maxz)
        {
            cout<<ve[i]<<endl;
            break;
        }
    }
    return 0;
}

B题，以前做过，经典的DP。链接

C题，模拟退火，水过，改了很多几下参数...正解，是解方程 什么的。

#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;
#define eps 1e-10
int a[4] = {0,0,1,-1};
int b[4] = {1,-1,0,0};
struct point
{
    double x,y;
};
point p[3];
double r[3];
double dis(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
point Rotate(point p,double angle)
{
    point res;
    res.x = p.x*cos(angle) - p.y*sin(angle);
    res.y = p.x*sin(angle) + p.y*cos(angle);
    return res;
}
double CirPoint(point a,point b,double r)
{
    double line = sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
    return line/r;
}
int main()
{
    double x,y;
    int i,j;
    srand(time(NULL));
    x = y = 0;
    for(i = 0;i < 3;i ++)
    {
        scanf("%lf%lf%lf",&p[i].x,&p[i].y,&r[i]);
        x += p[i].x;
        y += p[i].y;
    }
    x = x/2;
    y = y/2;
    double temp[3],avg,tsqs;
    double sqs = 1000000000;
    point ans,t;
    ans.x = 1000000;
    ans.y = 1000000;
    int T = 50000,key,k,flag = 0;
    key = 10;//key步长,T是温度
    while(T --)
    {
        for(i = 0;i < 4;i ++)
        {
            k = rand()%key;
            t.x = x + k*a[i]*T/100000.0;
            t.y = y + k*b[i]*T/100000.0;
            avg = 0;
            //利用 点到圆心距离 与 半径之比 表示这个角度
            for(j = 0;j < 3;j ++)
            {
                temp[j] = CirPoint(t,p[j],r[j]);
                avg += temp[j];
            }
            avg = avg/3;
            tsqs = 0;
            for(j = 0;j < 3;j ++)//方差
            {
                tsqs += (temp[j]-avg)*(temp[j]-avg);
            }
            if(sqs > tsqs)
            {
                sqs = tsqs;
                x = t.x;
                y = t.y;
            }
            if(tsqs < eps&&tsqs > -eps)
            {
                flag = 1;
                if(dis(p[0],t) < dis(p[0],ans))
                ans = t;
            }
        }
    }
    if(flag)
    printf("%lf %lf
",ans.x+eps,ans.y+eps);
    return 0;
}