[Offer收割]编程练习赛13 解题报告

http://hihocoder.com/contest/offers13/problems

题目1 : 风格不统一如何写程序

首先：输入保证组成变量名的单词只包含小写字母。

做法：只要对不同的部分进行修改即可

注意：只有一个单词，两个方法的单词都一样

 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <stdbool.h>

 int main()
 {
     long n,i,k,len;
     char s[];
     bool vis;
     scanf("%ld",&n);
     for (k=;k<=n;k++)
     {
         scanf("%s",s);
         len=strlen(s);
         vis=false;
         for (i=;i<len;i++)
             if (s[i]=='_')
             {
                 vis=true;
                 break;
             }
         if (vis)
         {
             for (i=;i<len;i++)
                 if (s[i]=='_')
                 {
                     printf("%c",s[i+]-);
                     i++;
                 }
                 else
                     printf("%c",s[i]);
         }
         else
         {
             for (i=;i<len;i++)
                 if (s[i]<)
                 {
                     printf("_");
                     printf("%c",s[i]+);
                 }
                 else
                     printf("%c",s[i]);
         }
         printf("\n");
     }

     return ;
 }

最大子矩阵

注意：满足条件最大的子矩阵所包含的元素数目。如果没有子矩阵满足条件，输出-1。

与求最大子矩阵题目(hdu1559子矩阵的元素之和最大)方法类似。

设row[x][y]：第x行中前y个数的和

则row[x][q]-row[x][p]：第x行中第p+1~第q个数的和

行x~y列u~v的矩形的元素之和：row[x][v]-row[x][u-1]+row[x+1][v]-row[x+1][u-1]+…+row[y][v]-row[y][u-1]

按照列固定：u~v (第u个数到第v个数)， 进行行的探索。

假设从行第p个数开始向下边2递增(每次p加1),假设到第q个数数值和第一次超过设定值，计算矩形面积(q-p)*(v-u+1)，

然后从第p个数开始向下边1递增(每次p+1)，直到数值和第一次小于设定值。

然后继续操作，直到v=n+1，结束。

而对于每个列固定：x~y，共m*m次。而对于每次行的探索，每个数最多加入一次，每个数最多减去一次，共2*n次。

时间复杂度O(m*m*n)。当然如果m>n，可以把行固定，进行列的探索，时间复杂度O(m*n*n)。

即时间复杂度O(m*n*min(m,n))。

参见程序，比较巧妙。

 #include <stdio.h>
 #include <stdlib.h>

 long max(long a,long b)
 {
     if (a>b)
         return a;
     else
         return b;
 }

 int main()
 {
     long n,m,f[][],row[][];
     long i,j,s,t,maxg=,maxvalue,ans=,bian,x,y;
     scanf("%ld%ld%ld",&n,&m,&maxvalue);
     for (i=;i<=n;i++)
     {
         //single row
         row[i][]=;
         for (j=;j<=m;j++)
         {
             scanf("%ld",&f[i][j]);
             row[i][j]=row[i][j-]+f[i][j];
         }
     }
     //s+1~t
     for (s=;s<m;s++)
         for (t=s+;t<=m;t++)
         {
             bian=t-s;
             ans=;
             x=;
             y=;
             i=;
             while (i!=n+)
             {
                 for (i=y;i<=n;i++)
                 {
                     ans=ans+row[i][t]-row[i][s];
                     if (ans>maxvalue)
                         break;
                 }
                 //x~i-1
                 maxg=max(maxg,(i-x)*bian);
                 //使x~i <=maxvalue
                 //最终的可能性是减为0
                 while (ans>=maxvalue)
                 {
                     ans=ans-row[x][t]+row[x][s];
                     x++;
                 }
                 //使下一次从i+1的位置开始加
                 y=i+;

             }
         }
     if (maxg==)
         printf("-1\n");
     else
         printf("%ld\n",maxg);
     return ;
 }
 /*
 5 5 3
 1 2 3 2 1
 2 3 1 2 3
 1 2 1 3 1
 1 2 1 3 1
 1 2 3 3 3
 */
 /*
 20 20 31
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 */

题目3 : 一人麻将

注意：无法胡牌输出-1。

方法：可以cheat！！！经测试，输出-1，可得10分。那时我去参加zoj的网赛，没有时间了，就果断cheat！(noip及其有效，对一些特殊且容易写的部分)

参见程序，程序长，但时间消耗比较短

 #include <stdio.h>
 #include <stdlib.h>
 #include <stdbool.h>

 struct rec
 {
     long posu,posv;
 };

 struct node
 {
     long posu,posv,posw;
 };

 bool vis[];
 struct node s[];
 long ts,ee,minpos=;

 int cmp(const void *a,const void *b)
 {
     //posu<posv。对a,b中最大的牌(posv)进行升序排序(先拿到，先胡牌)
     //a,b中最大的牌(posv)都不相同
     return (*(struct rec *)a).posv - (*(struct rec *)b).posv;
 }

 int cmp1(const void *a,const void *b)
 {
     return (*(struct node *)a).posw - (*(struct node *)b).posw;
 }

 long max(long a,long b)
 {
     if (a>b)
         return a;
     else
         return b;
 }

 long min(long a,long b)
 {
     if (a>b)
         return b;
     else
         return a;
 }

 void dfs(long b,long step)
 {
     long i;
     for (i=b;i<ts-step && s[i].posw<minpos;i++)
         if (vis[s[i].posu] && vis[s[i].posv] && vis[s[i].posw])
         {
             if (step==)
             {
                 //minpos=min(minpos,s[i].posw);
                 minpos=max(ee,s[i].posw);
                 break;
             }
             //else if (s[i].posw<minpos)
             else
             {
                 vis[s[i].posu]=false;
                 vis[s[i].posv]=false;
                 vis[s[i].posw]=false;
                 dfs(i+,step-);
                 vis[s[i].posu]=true;
                 vis[s[i].posv]=true;
                 vis[s[i].posw]=true;
             }
         }
 }

 int main()
 {
     char str[];
     //一张牌最多4个:2对,9*2=18种牌
     //3:
     //数字相连：(1,2,3)~(7,8,9) 每张牌有4种选择 4*4*4*8=502
     //同数字：若有四张牌 1,2,3;2,3,4(若1,2,3与其它冲突,用2,3,4) 2*9=18
     struct rec er[][],e[];
     struct node san[][];
     long ge[],gs[],te;
     //pai[i][j]:i:对应a,b,c j:对应1~9，最多有4张牌
     long n,x,y,t,pai[][][],ans[][];
     long i,j,k,l,m;
     for (i=;i<;i++)
         for (j=;j<;j++)
             ans[i][j]=;
     scanf("%ld",&n);

     for (i=;i<;i++)
     {
         scanf("%s",str);
         x=str[]-;
         //-'1'
         y=str[]-;
         pai[x][y][ans[x][y]]=i;
         ans[x][y]++;
     }
     for (i=;i<+n;i++)
     {
         scanf("%s",str);
         x=str[]-;
         y=str[]-;
         pai[x][y][ans[x][y]]=i;
         ans[x][y]++;
     }

     //对子
     for (i=;i<;i++)
     {
         ge[i]=;
         for (j=;j<;j++)
         {
             //找最前面的配对
             if (ans[i][j]>=)
             {
                 er[i][ge[i]].posu=pai[i][j][];
                 er[i][ge[i]].posv=pai[i][j][];
                 ge[i]++;
             }
             //两个对子
             if (ans[i][j]==)
             {
                 er[i][ge[i]].posu=pai[i][j][];
                 er[i][ge[i]].posv=pai[i][j][];
                 ge[i]++;
             }
         }
         qsort(er[i],ge[i],sizeof(struct rec),cmp);
     }

     //至少拥有7个对子胡牌
     //手中14张牌最多只能属于两个花色
     //each 对子 没有相互影响
     for (i=;i<;i++)
         for (j=i+;j<;j++)
             if (ge[i]+ge[j]>=)
             {
                 x=;
                 y=;
                 t=;
                 while (x<ge[i] && y<ge[j] && t<)
                 {
                     t++;
                     if (er[i][x].posv<er[j][y].posv)
                         x++;
                     else
                         y++;
                 }
                 if (t==)
                 {
                     //use j
                     if (x==ge[i])
                         minpos=min(minpos,er[j][y].posv);
                     //use i
                     else if (y==ge[j])
                         minpos=min(minpos,er[i][x].posv);
                     else
                         minpos=min(minpos,min(er[i][x].posv,er[j][y].posv));
                 }
                 //use j
                 else if (x==ge[i])
                     minpos=min(minpos,er[j][y+-t].posv);
                 //use i
                 else
                     minpos=min(minpos,er[i][x+-t].posv);
             }

     //三张牌
     for (i=;i<;i++)
     {
         gs[i]=;
         //同数字
         for (j=;j<;j++)
         {
             if (ans[i][j]>=)
             {
                 san[i][gs[i]].posu=pai[i][j][];
                 san[i][gs[i]].posv=pai[i][j][];
                 san[i][gs[i]].posw=pai[i][j][];
                 gs[i]++;
             }
             if (ans[i][j]==)
             {
                 //相同的牌先给别人用了
                 san[i][gs[i]].posu=pai[i][j][];
                 san[i][gs[i]].posv=pai[i][j][];
                 san[i][gs[i]].posw=pai[i][j][];
                 gs[i]++;
             }
         }
         //数字相连
         for (j=;j<;j++)
             for (k=;k<ans[i][j];k++)
                 for (l=;l<ans[i][j+];l++)
                     for (m=;m<ans[i][j+];m++)
                     {
                         san[i][gs[i]].posu=pai[i][j][k];
                         san[i][gs[i]].posv=pai[i][j+][l];
                         san[i][gs[i]].posw=pai[i][j+][m];
                         //posw存放最大值
                         if (san[i][gs[i]].posu>san[i][gs[i]].posw)
                         {
                             if (san[i][gs[i]].posu>san[i][gs[i]].posv)
                             {
                                 t=san[i][gs[i]].posu;
                                 san[i][gs[i]].posu=san[i][gs[i]].posw;
                                 san[i][gs[i]].posw=t;
                             }
                             else
                             {
                                 t=san[i][gs[i]].posv;
                                 san[i][gs[i]].posv=san[i][gs[i]].posw;
                                 san[i][gs[i]].posw=t;
                             }
                         }
                         else if (san[i][gs[i]].posv>san[i][gs[i]].posw)
                         {
                             t=san[i][gs[i]].posv;
                             san[i][gs[i]].posv=san[i][gs[i]].posw;
                             san[i][gs[i]].posw=t;
                         }
                         gs[i]++;
                     }
         qsort(san[i],gs[i],sizeof(struct node),cmp1);
     }

     //4*3+2
     for (i=;i<;i++)
         for (j=i+;j<;j++)
         {
             for (k=;k<;k++)
                 vis[k]=true;

             te=;
             for (k=;k<ge[i];k++)
                 if (er[i][k].posv<minpos)
                 {
                     e[te]=er[i][k];
                     te++;
                 }
                 else
                     break;
             for (k=;k<ge[j];k++)
                 if (er[j][k].posv<minpos)
                 {
                     e[te]=er[j][k];
                     te++;
                 }
                 else
                     break;

             ts=;
             for (k=;k<gs[i];k++)
                 if (san[i][k].posw<minpos)
                 {
                     s[ts]=san[i][k];
                     ts++;
                 }
                 else
                     break;
             for (k=;k<gs[j];k++)
                 if (san[j][k].posw<minpos)
                 {
                     s[ts]=san[j][k];
                     ts++;
                 }

             qsort(e,te,sizeof(struct rec),cmp);
             qsort(s,ts,sizeof(struct node),cmp1);

             for (k=;k<te;k++)
             {
                 if (e[k].posv<minpos)
                 {
                     ee=e[k].posv;
                     vis[e[k].posu]=false;
                     vis[e[k].posv]=false;
                     dfs(,);
                     vis[e[k].posu]=true;
                     vis[e[k].posv]=true;
                 }
                 else
                     break;
             }
         }
     //No Solution: output -1
     if (minpos==)
         printf("-1\n");
     else
         printf("%ld\n",minpos-);
     return ;
 }

题目拓展：

有n个人，参加一个活动

每一个人有一个不和谐值

每三个人一个队伍

有若干组队伍

每一个队伍的不和谐值为三人的不和谐值的最大值
而不和谐值越小，完成一个活动越快

要求从n个人从选出m个队伍，
其中不同队伍里不能有相同的人

使不和谐值最大的队伍的不和谐值最小，
从而使得所有队伍完成时间最短

当三个人
变为两个人
变为k个人

结果如何？？？

题目4 : 骑士游历

一个通俗的想法：f[k][i][j]，第k步可以到达(i,j)的步法总数。
f[k+1][i][j]是在第k步的基础上走1步到达(i,j)的步法总数。

 #include <stdio.h>
 #include <stdlib.h>
 #define yu 1000000007

 int main()
 {
     long dx[]={-,-,-,-,,,,};
     long dy[]={-,,-,,-,,-,};
     long long f[][][];
     long n,r,c,i,j,k,step,pre,cur,x,y;
     long long ans;
     scanf("%ld%ld%ld",&n,&r,&c);
     for (i=;i<=;i++)
         for (j=;j<=;j++)
             f[][i][j]=;
     f[][r][c]=;
     pre=;
     cur=;
     for (step=;step<=n;step++)
     {
         for (i=;i<=;i++)
             for (j=;j<=;j++)
                 f[cur][i][j]=;
         for (i=;i<=;i++)
             for (j=;j<=;j++)
                 for (k=;k<;k++)
                 {
                     x=i+dx[k];
                     y=j+dy[k];
                     if (x>= && x<= && y>= && y<=)
                         f[cur][x][y]=(f[cur][x][y]+f[pre][i][j])%yu;
                 }

         pre=pre ^ ;
         cur=cur ^ ;
     }
     ans=;
     for (i=;i<=;i++)
         for (j=;j<=;j++)
             ans=(ans+f[pre][i][j])%yu;
     printf("%lld\n",ans);
     return ;
 }

满分做法：

二分思想，类似快速幂思想

f[k][x][y][u][v]：从(x,y)开始走k步到(u,v)总的走法

1.第k步到达第k+1步

f[k+1][x][y][u][v]=sum(f[k][x][y][p][q]+f[1][p][q][u][v])

2.第k步到达第2*k步

f[2*k][x][y][u][v]=sum(f[k][x][y][p][q],f[k][p][q][u][v])

快速幂：1->k，如10101=(((*2+)*2+)*2+)*2+1。(乘4次，加5次)

初始化f[1]，只要创建四维数组即可。

时间复杂度：

1.第k步到达第2*k步：x,y,p,q,u,v可以取1~8：8*8*8*8*8*8=262144

最多执行log2(1000000000)<=30（向下取整）

262144*30=7864320

2.第k步到达第k+1步：f[k+1][x][y][u][v]=sum(f[k][x][y][p][q]+f[1][p][q][u][v])：计算每个x,y：8*8*8(走马，8种操作)=512

最多执行log2(1000000000)<=30（向下取整）

时间复杂度可以忽略不计

总的时间复杂度小于1000万，不会超时。

参见程序

 #include <stdio.h>
 #include <stdlib.h>
 #include <math.h>
 #define yu 1000000007

 int main()
 {
     long dx[]={-,-,-,-,,,,};
     long dy[]={-,,-,,-,,-,};
     long long f[][][][],t[][][][],ans;
     long n,r,c,m,ch[];
     long x,y,p,q,u,v,k,i;

     scanf("%ld%ld%ld",&n,&r,&c);
     for (x=;x<=;x++)
         for (y=;y<=;y++)
             for (u=;u<=;u++)
                 for (v=;v<=;v++)
                     f[x][y][u][v]=;
     for (u=;u<=;u++)
         for (v=;v<=;v++)
             for (k=;k<;k++)
             {
                 p=u-dx[k];
                 q=v-dy[k];
                 if (p>= && p<= && q>= && q<=)
                     f[p][q][u][v]=;
             }

     m=(long)(log(n)/log(2.0));
     ch[]=;
     for (i=;i<=m;i++)
         ch[i]=ch[i-]<<;
     n-=ch[m];
     for (i=m-;i>=;i--)
     {
         //*2
         for (x=;x<=;x++)
             for (y=;y<=;y++)
                 for (u=;u<=;u++)
                     for (v=;v<=;v++)
                     {
                         t[x][y][u][v]=f[x][y][u][v];
                         f[x][y][u][v]=;
                     }

         for (x=;x<=;x++)
             for (y=;y<=;y++)
                 for (u=;u<=;u++)
                     for (v=;v<=;v++)
                     {
                         f[x][y][u][v]=;
                         for (p=;p<=;p++)
                             for (q=;q<=;q++)
                 f[x][y][u][v]=(f[x][y][u][v]+t[x][y][p][q]*t[p][q][u][v])%yu;
                     }
         //+1
         if (n>=ch[i])
         {
             for (x=;x<=;x++)
                 for (y=;y<=;y++)
                     for (u=;u<=;u++)
                         for (v=;v<=;v++)
                         {
                             t[x][y][u][v]=f[x][y][u][v];
                             f[x][y][u][v]=;
                         }

             for (u=;u<=;u++)
                 for (v=;v<=;v++)
                     for (k=;k<;k++)
                     {
                         p=u-dx[k];
                         q=v-dy[k];
                         if (p>= && p<= && q>= && q<=)
                         {
                             for (x=;x<=;x++)
                                 for (y=;y<=;y++)
                             f[x][y][u][v]=(f[x][y][u][v]+t[x][y][p][q])%yu;
                         }
                     }
             n-=ch[i];
         }
     }
     ans=;
     for (u=;u<=;u++)
         for (v=;v<=;v++)
             ans=(ans+f[r][c][u][v])%yu;
     printf("%lld",ans);
     return ;
 }