T1统计数字

排个序扫一遍就没了吧......

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 int a[200005]; 7 int read() 8 { 9     char c=getchar();int ans=0,f=1;10     while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}11     while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();}12     return ans*f;13 }14 int main()15 {16     int n=read(),m=0;17     for(int i=1;i<=n;i++)a[i]=read();18     sort(a+1,a+1+n);19     for(int i=1;i<=n;i++)20     {21         if(a[i]==a[i+1])m++;22         else23         {24             printf("%d %d\n",a[i],m+1);25             m=0;26         }27     }28     return 0;29 }
         
        
       
      

 

T2字符串的展开

超级大分类的模拟题，没什么好讲的......

 

1 #include
      
        2 #include
       
         3 #include
        
          4 const int N=1e5+10; 5 using namespace std; 6 char c[N]; 7 int p1,p2,p3; 8 int main() 9 {10     scanf("%d %d %d",&p1,&p2,&p3);11     scanf("%s",c+1);12     int len=strlen(c+1);13     for(int i=1;i<=len;i++){14         if(c[i]!='-'){15             printf("%c",c[i]);continue;16         }17         if(i==1){printf("-");continue;}18         if(c[i+1]=='-'||c[i-1]=='-'){printf("-");continue;}19         if(c[i+1]<=c[i-1]||(c[i+1]>='a'&&c[i-1]<='9')){printf("-");continue;}20         if(c[i+1]==c[i-1]+1)continue;21         if(p1==3){22             for(int j=1;j<=p2*(c[i+1]-c[i-1]-1);j++)printf("*");23             continue;24         }25         if(p3==1){26                 if(p1==1||(c[i-1]>='0'&&c[i-1]<='9')){27                     for(int j=c[i-1]+1;j<=c[i+1]-1;j++){28                         for(int k=1;k<=p2;k++)printf("%c",j);29                     }30                 }31                 else{32                     for(int j=c[i-1]+1;j<=c[i+1]-1;j++){33                         for(int k=1;k<=p2;k++)printf("%c",j-('a'-'A'));34                     }35                 }36         }37         else{38             if(p1==1||(c[i-1]>='0'&&c[i-1]<='9')){39                     for(int j=c[i+1]-1;j>=c[i-1]+1;j--){40                         for(int k=1;k<=p2;k++)printf("%c",j);41                     }42                 }43                 else{44                     for(int j=c[i+1]-1;j>=c[i-1]+1;j--){45                         for(int k=1;k<=p2;k++)printf("%c",j-('a'-'A'));46                     }47                 }48         }49     }50     return 0;51 }
        
       
      

 

T3树网的核

n³跑一遍floyd预处理出两两之间最短路，n²枚举两个在直径上的点统计答案就好了。

1 #include
      
        2 #include
       
         3 #include
        
          4 const int inf=0x3f3f3f3f; 5 using namespace std; 6 int n,s,a,b,c,maxx=0,mxi,mxj; 7 int dis[305][305]; 8 int read() 9 {10     int ans=0,f=1;char c=getchar();11     while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}12     while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();}13     return ans*f;14 } 15 int main()16 {17     n=read();s=read();18     for(int i=1;i<=n;i++)19         for(int j=1;j<=n;j++)20             if(i!=j)dis[i][j]=inf;21     for(int i=1;i<=n-1;i++){22         a=read();b=read();c=read();dis[a][b]=dis[b][a]=c;23     }24     for(int k=1;k<=n;k++)25         for(int i=1;i<=n;i++)26             for(int j=1;j<=n;j++){27                 if(dis[i][k]>=inf||dis[k][j]>=inf)continue;28                 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);29                 if(dis[i][j]>maxx){30                     maxx=dis[i][j];31                     mxi=i;mxj=j;32                 }33             }34     int ans=inf;35     for(int i=1;i<=n;i++){36         if(dis[mxi][i]+dis[i][mxj]!=dis[mxi][mxj])continue;37         for(int j=1;j<=n;j++){38             if(dis[mxi][j]+dis[j][mxj]!=dis[mxi][mxj]||dis[i][j]>s)continue;39             int ecc=0;40             ecc=max(min(dis[mxi][i],dis[mxi][j]),min(dis[mxj][i],dis[mxj][j]));41             ans=min(ans,ecc);42         }43     }44     printf("%d",ans);45     return 0;46 }
        
       
      

T4矩阵取数游戏

这题要是没有高精就是一道简单dp了，不过加上高精乘之后就很不好写了。然而我们可以把状态转移方程化为:

f[i][j]=2*max(f[i+1][j]+mp[i]+mp[i][j],f[i][j-1]+mp[j]);

这样我们就只用写两个高精加就行了（然而还是很不好写）......

1 #include
      
        2 #include
       
         3 #include
        
          4 #define mem(a,p) memset(a,p,sizeof(a)) 5 #include
         
           6 const int N=85; 7 int n,m; 8 int read(){ 9     int ans=0,f=1;char c=getchar();10     while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}11     while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();}12     return ans*f;13 }14 int f[N][N][100],data[N][N],ans[100],kk[100],pp[100],dd[100];15 int mxa(int x,int y){
    return x>y?x:y;}16 void plus0(int x[],int y[]){17     x[0]=mxa(x[0],y[0]);18     for(int i=1;i<=x[0];i++){19         x[i]+=y[i];20         x[i+1]+=x[i]/10;21         x[i]%=10;22     }23     if(x[x[0]+1]>0)x[0]++;24 }25 void max(int x[],int y[],int z[]){26     if(y[0]>z[0]){plus0(x,y);return;}27     if(z[0]>y[0]){plus0(x,z);return;}28     for(int i=y[0];i>=1;i--){29         if(y[i]>z[i]){plus0(x,y);return;}30         if(y[i]
          
           0)x[0]++;42 }43 int main(){44     n=read();m=read();45     for(int i=1;i<=n;i++)46         for(int j=1;j<=m;j++)47             data[i][j]=read();48     for(int r=1;r<=n;r++){49         mem(f,0);50         for(int i=m;i>=1;i--){51             for(int j=i;j<=m;j++){52                 mem(kk,0);mem(pp,0);53                 plus1(kk,data[r][j],f[i][j-1]);54                 for(int k=0;k<=kk[0];k++)pp[k]=kk[k];55                 plus0(kk,pp);mem(dd,0);mem(pp,0);56                 plus1(pp,data[r][i],f[i+1][j]);57                 for(int k=0;k<=pp[0];k++)dd[k]=pp[k];58                 plus0(pp,dd);59                 max(f[i][j],pp,kk);60             }61         }62         plus0(ans,f[1][m]);63     }64     if(ans[0]==0)return printf("0"),0;65     for(int i=ans[0];i>=1;i--)printf("%d",ans[i]);66     return 0;67 }