Codeforces Round#2

A. Winner

　　题目大意：一些人在玩游戏，给出n次某人获得的分数，现在请计算出胜者，如果不止一个最高分，则取最先达到该分数的人。

　　题解：模拟得分过程，首先计算出最高分，然后获取先到达或超过最高分的人。

#include <iostream>

#include <algorithm>

#include <string>

#include <vector>

#include <cstdio>

#include <map>

using namespace std;

vector<string> name;

vector<int> score;

map<string,int> sum,sum1;

int Max=0,x;

string s;

int main(int n){

    scanf("%d",&n);

    for(int i=0;i<n;i++){

        cin>>s>>x;

        name.push_back(s);

        score.push_back(x);

        sum[name[i]]+=score[i];

    }for(int i=0;i<n;i++){if(sum[name[i]]>Max)Max=sum[name[i]];}

    for(int i=0;i<n;i++){

        if(sum[name[i]]<Max||(sum1[name[i]]+=score[i])<Max)continue;

        cout<<name[i]<<endl; break;

    }

}

B. The least round way　

　　题目大意：找一条从给出的数字矩阵左上角到右下角的道路，使得该路上所有数字的乘积后面的0最少。求出路径和最小的0数目。

　　题解：首先如果路径中有0，那么答案就是1，否则就是道路中数字中因子2和因子5的最小值（因为2和5配对才可以产生0），计算2和5的个数的过程用记忆化搜索，路径记录则由已知的DP值倒推获得。

#include <cstdio>

#include <cstring>

#include <string>

#include <iostream>

#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

const int N=1005;

const int inf=~0U>>2;

int dp[N][N],M[N][N],b[N][N],ans=inf,n;

string road;

void dfs(int x,int y){

    if(x&&dp[x][y]==b[x][y]+dp[x-1][y]){dfs(x-1,y);road.push_back('D');}

    else if(y){dfs(x,y-1);road.push_back('R');}

}

void solve(int c){

    rep(i,n)rep(j,n){int x=0;while(M[i][j]&&M[i][j]%c==0)M[i][j]/=c,x++;b[i][j]=x;}

    rep(i,n)rep(j,n){

        if(i)dp[i][j]=b[i][j]+dp[i-1][j];

        else if(j)dp[i][j]=b[i][j]+dp[i][j-1];

        else dp[i][j]=b[i][j];

        if(i)dp[i][j]=min(dp[i][j],b[i][j]+dp[i-1][j]);

        if(j)dp[i][j]=min(dp[i][j],b[i][j]+dp[i][j-1]);

    }

    if(ans>dp[n-1][n-1]){

        ans=dp[n-1][n-1];

        road=""; dfs(n-1,n-1);

    }

}

int main(){

    scanf("%d",&n);

    rep(i,n)rep(j,n)scanf("%d",&M[i][j]);

    solve(2);solve(5);

    rep(i,n)rep(j,n)if(M[i][j]==0&&ans>1){

        ans=1;road="";

        rep(k,i)road.push_back('D');

        rep(k,j)road.push_back('R');

        rep(k,n-i-1)road.push_back('D');

        rep(k,n-j-1)road.push_back('R');

    }cout<<ans<<endl<<road<<endl;

    return 0;

}

C. Commentator problem

　　题目大意：给出三个圆（坐标，半径），求一个点，使得它与三个圆切线所形成的角相等，如果无法找到，则不输出

　　题解：首先将起点定位在三个点形成的三角形的重心，然后模拟退火，以1为起步长，不断重新调整选取点的位置，使得其最终符合要求。如果达到精度后无法满足，则不输出。

#include <cstdio>

#include <cmath>

using namespace std;

const double EPS=1e-6;

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

struct C{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 f(double x,double y){

    double u[3],ans=0;

    for(int i=0;i<3;i++)u[i]=dist(x,y,c[i].x,c[i].y)/c[i].r;

    for(int i=0;i<3;i++)ans+=(u[i]-u[(i+1)%3])*(u[i]-u[(i+1)%3]);

    return ans;

}

int main(){

    double x=0,y=0,step=2;

    for(int i=0;i<3;i++){scanf("%lf%lf%lf",&c[i].x,&c[i].y,&c[i].r);x+=c[i].x/3;y+=c[i].y/3;}

    while(step>EPS){

        double tmp=f(x,y);

        int flag=-1;

        for(int i=0;i<4;i++){

            double tmp1=f(x+d[i][0]*step,y+d[i][1]*step);

            if(tmp1<tmp){tmp=tmp1;flag=i;}

        }if(flag==-1)step/=2;

        else{x=x+d[flag][0]*step;y=y+d[flag][1]*step;}

    }if(f(x,y)<EPS)printf("%.5lf %.5lf\n",x,y);

    return 0;

}

巴特西

Codeforces Round#2

最新文章

热门文章