Codeforces Beta Round＃2

A

模拟题

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 map<string,ll>mp;

 struct sair{

     string str;

     int id;

     ll num;

 }a[];

 bool cmp(sair a,sair b){

     if(a.num==b.num) return a.id<b.id;

     return a.num>b.num;

 }

 int main(){

     int n;

     cin>>n;

     string ans;

     ll Max=-0x3f3f3f3f;

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

         cin>>a[i].str>>a[i].num;

         a[i].id=i;

     }

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

         mp[a[i].str]+=a[i].num;

         a[i].num=mp[a[i].str];

     }

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

         if(mp[a[i].str]>Max){

             Max=mp[a[i].str];

         }

     }

     sort(a+,a+n+,cmp);

     map<string,ll>tmp;

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

         if(mp[a[i].str]==Max){

             tmp[a[i].str]=;

         }

     }

     int idmin=0x3f3f3f3f;

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

         if(tmp[a[i].str]==){

             if(idmin>a[i].id&&a[i].num>=Max){

                 idmin=a[i].id;

                 ans=a[i].str;

             }

         }

     }

     cout<<ans<<endl;

     //system("pause");

 }

B

能让末尾有0的情况是由2的倍数和5的倍数相乘，所以只要预处理出每个数中因子为2的个数和因子为5的个数，取最小值DP即可

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 typedef long long ll;

 int n;

 int dp[][][];///dp[i][j][0] 表示2的数量，dp[i][j][1] 表示5的数量

 int pre[][][];

 void print(int i,int j,int k,int flag){

     if(i==&&j==);

     else if(i==) print(i,j-,k,);

     else if(j==) print(i-,j,k,);

     else{

         if(dp[i][j][k]==dp[i][j-][k]+pre[i][j][k])

             print(i,j-,k,);

         else

             print(i-,j,k,);

     }

     if(flag==) return;

     cout<<(flag?"D":"R");

 }

 int main(){

     #ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

     #endif

     std::ios::sync_with_stdio(false);

     cin>>n;

     int num,tmp;

     int x=-,y=-;

     memset(dp,0x3f,sizeof(dp));

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

         for(int j=;j<=n;j++){

             cin>>num;

             if(!num){

                 pre[i][j][]++;

                 pre[i][j][]++;

                 x=i,y=j;

                 continue;

             }

             tmp=num;

             while(tmp%==){

                 pre[i][j][]++;

                 tmp/=;

             }

             tmp=num;

             while(tmp%==){

                 pre[i][j][]++;

                 tmp/=;

             }

         }

     }

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

         for(int j=;j<=n;j++){

             for(int k=;k<;k++){

                 if(i>){

                     dp[i][j][k]=min(dp[i][j][k],dp[i-][j][k]);

                 }

                 if(j>){

                     dp[i][j][k]=min(dp[i][j][k],dp[i][j-][k]);

                 }

                 if( i== && j== ){

                     dp[i][j][k]=;

                 }

                 dp[i][j][k]+=pre[i][j][k];

             }

         }

     }

     int ans=min(dp[n][n][],dp[n][n][]);

     if(x!=-&&y!=-&&ans>=){

         cout<<<<endl;

         for(int i=;i<x;i++){

             cout<<"D";

         }

         for(int i=;i<y;i++){

             cout<<"R";

         }

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

             cout<<"D";

         }

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

             cout<<"R";

         }

         cout<<endl;

     }

     else{

         cout<<ans<<endl;

         if(dp[n][n][]>dp[n][n][]){

             print(n,n,,);

         }

         else{

             print(n,n,,);

         }

         cout<<endl;

     }

     return ;

 }

C

几何题+模拟退火

题意：找一个点对每个圆切线的角度一样，如果有多个，就找角度最大的点

思路：asin(L/r) 只要L/r一样，它们的角度一定一样，所以用模拟退火枚举就好，感觉和2018icpc南京站的题很像

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 typedef long long ll;

 struct circle{

     double x,y,r;

 }c[];

 double angle[];

 double Check(double x,double y){

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

         angle[i]=sqrt(sqr(x-c[i].x)+sqr(y-c[i].y))/c[i].r;

     }

     double ans=;

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

         ans+=sqr(angle[i]-angle[(i+)%]);

     }

     return ans;

 }

 int main(){

     #ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

     #endif

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

         scanf("%lf %lf %lf",&c[i].x,&c[i].y,&c[i].r);

     }

     double ansx,ansy;

     ansx=(c[].x+c[].x+c[].x)/;

     ansy=(c[].y+c[].y+c[].y)/;

     double step=1.0;

     int flag;

     double tmp;

     while(step>1e-){

         flag=;

         tmp=Check(ansx,ansy);

         if(tmp>Check(ansx+step,ansy)) ansx+=step,flag=;

         else if(tmp>Check(ansx-step,ansy)) ansx-=step,flag=;

         else if(tmp>Check(ansx,ansy+step)) ansy+=step,flag=;

         else if(tmp>Check(ansx,ansy-step)) ansy-=step,flag=;

         if(!flag) step*=0.8;

     }

     if(Check(ansx,ansy)<1e-) printf("%.6f %.6f\n",ansx,ansy);

 }