A题：模拟题，仔细点就好
B题：DP
给你一个数字矩阵，要求从左上角走到右下角的一条路径，这条路径上的数乘起来后末尾的0的个数最少
末尾的0是由2、5产生的，于是联想一下是不是走2最少的一条路或者5最少的一条路就ok了呢？
嗯，就是ok的.*_*
假设从左上角走到右下角走过的数含因子2的最小的个数是x，5的最小的个数是y，则答案是min(x,y)，即最优解x、y的个数中有一项是最少的
证明：用反证法，假设最优解经过的数含a个2，b个5，a>x,b>y,易得答案肯定大于
min(x,y),所以最优解的x、y肯定有一项是最小的
View Code
#include<cstdio> #include<cmath> #include<string> #include<cstdlib> #include<vector> #include<map> #include<set> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int inf = ~0u>>2; const int M = 1010; int dp[M][M][2]; int min(int a,int b){ return a<b?a:b; } int main() { int n,i,j,k,x,y,pos; while(scanf("%d",&n)!=EOF) { pos=-1; memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&x);y=x; if(x==0) { pos=i; continue; } while(y%2==0){dp[i][j][0]++;y/=2;} while(x%5==0){dp[i][j][1]++,x/=5;} } } for(i=2;i<=n;i++) { dp[i][1][0]+=dp[i-1][1][0]; dp[i][1][1]+=dp[i-1][1][1]; dp[1][i][0]+=dp[1][i-1][0]; dp[1][i][1]+=dp[1][i-1][1]; } for(i=2;i<=n;i++) { for(j=2;j<=n;j++) { dp[i][j][0]+=min(dp[i-1][j][0],dp[i][j-1][0]); dp[i][j][1]+=min(dp[i-1][j][1],dp[i][j-1][1]); } } // printf("%d %d\n",dp[n][n][1],dp[n][n][0]); string ans; k=dp[n][n][0]>dp[n][n][1]; if(pos!=-1&&dp[n][n][k]) { printf("1\n"); for(i=1;i<pos;i++) printf("D"); for(i=1;i<n;i++) printf("R"); for(i=pos;i<n;i++) printf("D"); continue; }i=n;j=n; while(1) { if(dp[i-1][j][k]<dp[i][j-1][k]) { i--; ans+="D"; } else { j--; ans+="R"; } if(i==1) { for(i=1;i<j;i++) ans+="R"; break; } if(j==1) { for(j=1;j<i;j++) ans+="D"; break; } } int len=ans.length(); printf("%d\n",dp[n][n][k]); for(i=len-1;i>=0;i--) { cout<<ans[i]; } cout<<endl; } return 0; }
C题：给你三个圆，求一个点到三个圆的张角相等，如果有多个，选张角最大的那个点
用了爬山算法（模拟退火），不过调了好久的参数才过的
评估函数是当前点到三个圆的张角的方差，每次如果不能获得更优解，就逐渐缩小步长，如果获得了更优解，则始终允许该移动
在走的时候我是往上下左右四个方向走的，可能这也是答案不够准确的原因吧
View Code
#include<cstdio> #include<cmath> const double eps = 1e-6; int dir[4][2]={1,0,0,1,-1,0,0,-1}; struct point { double x,y,r; }p[10]; int sgn(double x){ return fabs(x)<eps?0:(x>0?1:-1); } double dist(point a,point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double judge(point tmp){ int i; double sum=0; double ang[5]; for(i=0;i<3;i++){ ang[i]=dist(p[i],tmp)/p[i].r; sum+=ang[i]; } sum/=3; double vir=0; for(i=0;i<3;i++) vir+=(ang[i]-sum)*(ang[i]-sum); return vir; } int main(){ int i,j,k; double x=0,y=0; for(i=0;i<3;i++){ scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r); x+=p[i].x; y+=p[i].y; } x/=3; y/=3; point s,t; s.x=x;s.y=y; double delta=1,vir1,vir2; while(delta>eps){ vir1=judge(s); for(i=0;i<4;i++){ t.x=s.x+delta*dir[i][0]; t.y=s.y+delta*dir[i][1]; vir2=judge(t); if(vir2<vir1) break; } if(i==4) delta*=0.82;//从0.88一直调到了0.82才摆脱TLE的阴影 else { s.x+=delta*dir[i][0]; s.y+=delta*dir[i][1]; } } if(judge(s)<eps) printf("%.8lf %.8lf\n",s.x,s.y); return 0; }