[关闭]
@TryMyEdge 2017-01-30T08:01:17.000000Z 字数 3866 阅读 845

第二次作业

题解

题目

A Game with Pearls

题目大意：

    M（M<=500）组数据。有N（1<=N<=100）个管子，给出每个管子内的珍珠数目a，你可以让其中任意一个管子增加K（1<=K<=N）个，该操作可进行任意次，问是否能让珍珠数目为1到N的管子各存在一个。

解题思路：

    用一个从小到大的优先队列维护所有的管子，当队首的管子的珍珠数大于当前要求的珍珠数时，说明不可行；当正好相等，说明这个管子是当前要求的，把珍珠数加一，直到珍珠数超过N；如果小于，就把管子内加K个珍珠重新加入队列。
    时间复杂度o（M*N^2/K*logn），空间复杂度o（N）。

AC代码：

  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. #define pq priority_queue
  4. using namespace std;
  5. int main()
  6. {
  7.     int t,n,k,now;
  8.     bool flag;
  9.     scanf("%d",&t);
  10.     while(t--)
  11.     {
  12.         pq <int,vector<int>,greater<int> > q;
  13.         scanf("%d%d",&n,&k);
  14.         for(int i=0;i<n;i++)
  15.         {
  16.             scanf("%d",&now);
  17.             q.push(now);
  18.         }
  19.         flag=0;
  20.         for(int i=1;i<=n;i++)
  21.         {
  22.             do
  23.             {
  24.                 now=q.top();
  25.                 q.pop();
  26.                 if(now<i)
  27.                     q.push(now+k);
  28.             }while(now<i);
  29.             if(now>i)
  30.             {
  31.                 flag=1;
  32.                 break;
  33.             }
  34.         }
  35.         if(flag)
  36.             printf("Tom\n");
  37.         else
  38.             printf("Jerry\n");
  39.     }
  40.     return 0;
  41. }

C Seam Carving

题目大意：

    T（0<T<=30）组数据。给出个m*n（0<m,n<=100）的矩阵G，每个点可以往左下、右下或者正下方走，求和最小的路径。如果有多条路径，输出最右（字典序最大）的路径。

解题思路：

    让人联想起很经典的金字塔最优路径的dp题。记录到每个位置位置，最小的路径和，不断更新即可。
    因为要求输出最右（字典序最大）路径，所以从最后一行倒着dp。
    状态转移方程：dp[i][j]表示到第i行的第j列为止的最小路径和。
    dp[i][j]=min（dp[i=1][j-1]，dp[i=1][j]，dp[i=1][j+1]）+G[i][j]。
    用一个nex数组记录每个点的前一步，在第一行中找最优答案然后通过nex数组一行一行输出即可。
    注意边界的处理。
    时间复杂度o（T*n*m），空间复杂度o（n*m）。

AC代码：

  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. #define pq priority_queue
  4. using namespace std;
  5. long long num[105][105];
  6. long long dp[105][105];
  7. int pre[105][105];
  8. int main()
  9. {
  10.     long long minn;
  11.     int T,n,m,ans;
  12.     scanf("%d",&T);
  13.     for(int t=1;t<=T;t++)
  14.     {
  15.         scanf("%d%d",&n,&m);
  16.         for(int i=1;i<=n;i++)
  17.             for(int j=1;j<=m;j++)
  18.                 scanf("%lld",&num[i][j]);
  19.         printf("Case %d\n",t);
  20.         if(m==1)
  21.         {
  22.             for(int i=1;i<=n;i++)
  23.             {
  24.                 if(i>1)
  25.                     printf(" ");
  26.                 printf("1");
  27.             }
  28.             printf("\n");
  29.         }
  30.         else
  31.         {
  32.             for(int i=1;i<=m;i++)
  33.                 dp[n][i]=num[n][i];
  34.             for(int i=n-1;i;i--)
  35.                 for(int j=1;j<=m;j++)
  36.                 {
  37.                     if(j==1)
  38.                     {
  39.                         dp[i][j]=num[i][j]+dp[i+1][j];
  40.                         pre[i][j]=j;
  41.                         if(num[i][j]+dp[i+1][j+1]<=dp[i][j])
  42.                         {
  43.                             dp[i][j]=num[i][j]+dp[i+1][j+1];
  44.                             pre[i][j]=j+1;
  45.                         }
  46.                     }
  47.                     else
  48.                     {
  49.                         if(j==m)
  50.                         {
  51.                             dp[i][j]=num[i][j]+dp[i+1][j-1];
  52.                             pre[i][j]=j-1;
  53.                             if(num[i][j]+dp[i+1][j]<=dp[i][j])
  54.                             {
  55.                                 dp[i][j]=num[i][j]+dp[i+1][j];
  56.                                 pre[i][j]=j;
  57.                             }
  58.                         }
  59.                         else
  60.                         {
  61.                             dp[i][j]=num[i][j]+dp[i+1][j-1];
  62.                             pre[i][j]=j-1;
  63.                             if(num[i][j]+dp[i+1][j]<=dp[i][j])
  64.                             {
  65.                                 dp[i][j]=num[i][j]+dp[i+1][j];
  66.                                 pre[i][j]=j;
  67.                             }
  68.                             if(num[i][j]+dp[i+1][j+1]<=dp[i][j])
  69.                             {
  70.                                 dp[i][j]=num[i][j]+dp[i+1][j+1];
  71.                                 pre[i][j]=j+1;
  72.                             }
  73.                         }
  74.                     }
  75.                 }
  76.             minn=2000000000000;
  77.             for(int i=1;i<=m;i++)
  78.             {
  79.                 if(dp[1][i]<=minn)
  80.                 {
  81.                     minn=dp[1][i];
  82.                     ans=i;
  83.                 }
  84.             }
  85.             for(int i=1;i<n;i++)
  86.             {
  87.                 printf("%d ",ans);
  88.                 ans=pre[i][ans];
  89.             }
  90.             printf("%d\n",ans);
  91.         }
  92.     }
  93.     return 0;
  94. }

F Linearization of the kernel functions in SVM

题目大意：

    T（T<120）组数据。给定10个系数描述了一个多项式，输出这个多项式。

解题思路：

    题目太长而且都是符号，所以我是对着样例写的，然后就WA了一发。。。
    按要求模拟，注意系数是0的情况，第一个输出的系数如果是正数不需要'+'，系数是1和-1的时候隐藏数字只保留符号，还有最后一个常数项是0等情况。
    时间复杂度o（T），空间复杂度o（1）。

AC代码：

  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. #define pq priority_queue
  4. using namespace std;
  5. char s[]={'p','q','r','u','v','w','x','y','z'};
  6. int main()
  7. {
  8.     int t,now;
  9.     bool flag;
  10.     cin>>t;
  11.     while(t--)
  12.     {
  13.         flag=0;
  14.         for(int i=0;i<9;i++)
  15.         {
  16.             scanf("%d",&now);
  17.             if(now!=0)
  18.             {
  19.                 if(now>0 && flag)
  20.                     printf("+");
  21.                 if(abs(now)!=1)
  22.                     printf("%d",now);
  23.                 else
  24.                 {
  25.                     if(now<0)
  26.                         printf("-");
  27.                 }
  28.                 printf("%c",s[i]);
  29.                 flag=1;
  30.             }
  31.         }
  32.         scanf("%d",&now);
  33.         if(now!=0)
  34.         {
  35.             if(now>0 && flag)
  36.                 printf("+");
  37.             printf("%d",now);
  38.         }
  39.         printf("\n");
  40.     }
  41.     return 0;
  42. }

H Page Rank

题目大意：

    多组数据，处理到文件结尾。给出一个N*N（N<=3000）的0/1矩阵S，根据题目的公式转化为一个N*N的实数矩阵G。然后求|qGq|<10^-10的时候的q。

解题思路：

    按题目给出的方法求出G，然后q初始值为全1的N阶向量，然后模拟向量乘法直到满足要求就行了。
    = =然而并不知道复杂度如何证明。。。查到的题解也没给出复杂度。
    时间复杂度o（?*N^2），空间复杂度o（N^2）。

AC代码：

  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. #define pq priority_queue
  4. using namespace std;
  5. double G[3005][3005];
  6. double q[2][3005];
  7. bool flag;
  8. int num[3005];
  9. char s[3005][3005];
  10. int n;
  11. bool ok()
  12. {
  13.     double ans=0;
  14.     for(int i=1;i<=n;i++)
  15.         ans+=(q[flag][i]-q[!flag][i])*(q[flag][i]-q[!flag][i]);
  16.     return ans>0.0000000001;
  17. }
  18. void getq()
  19. {
  20.     for(int i=1;i<=n;i++)
  21.         for(int j=1;j<=n;j++)
  22.             q[flag][i]+=G[i][j]*q[!flag][j];
  23. }
  24. int main()
  25. {
  26.     while(~scanf("%d",&n))
  27.     {
  28.         memset(num,0,sizeof(num));
  29.         for(int i=1;i<=n;i++)
  30.         {
  31.             scanf("%s",s[i]+1);
  32.             for(int j=1;j<=n;j++)
  33.             {
  34.                 num[i]+=s[i][j]-'0';
  35.             }
  36.         }
  37.         for(int i=1;i<=n;i++)
  38.             for(int j=1;j<=n;j++)
  39.             {
  40.                 G[i][j]=0.15/n;
  41.                 if(s[j][i]-'0')
  42.                     G[i][j]+=0.85/num[j];
  43.             }
  44.         memset(q[1],0,sizeof(q[1]));
  45.         for(int i=1;i<=n;i++)
  46.             q[0][i]=1;
  47.         flag=0;
  48.         while(ok())
  49.         {
  50.             flag=!flag;
  51.             memset(q[flag],0,sizeof(q[flag]));
  52.             getq();
  53.         }
  54.         for(int i=1;i<=n;i++)
  55.         {
  56.             if(i>1)
  57.                 printf(" ");
  58.             printf("%.2f",q[flag][i]);
  59.         }
  60.         printf("\n");
  61.     }
  62.     return 0;
  63. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注