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;
}
原文：http://www.cnblogs.com/forever97/p/Codeforces2.html