[关闭]
@CQUPTacm 2018-11-14T06:01:46.000000Z 字数 9003 阅读 3264

重庆市第九届大学生程序设计大赛重邮赛区初赛 题解

题解

写在前面的话：虽然你们当中的很多人并不会接触到acm相关的赛事，但是我还是觉得参加这些校级比赛以及接受协会的培训对你们是有好处的。我不希望当你们找工作或者读研的时候，面试被问到“你这个做法的复杂度是多少？”、“有没有更好的方法？”，你们反问一句“额，什么叫复杂度？”或者说出“我只用了一个循环，应该没有更好的方法了……”。

考虑到大部分同学的水平不适合做H和I(主要是写题解的人太菜了，他不会H和I)，只提供了A到G的题解。java代码多数由c++代码翻译而来，可能会有点丑，见谅见谅。

A 平方和

    按照题意的描述把数列的每个数的平方加起来就行了。善良的出题人保证了答案在int的表示范围之内。
    时间复杂度o(T*N)，空间复杂度o(N)。

代码

  1. //C++
  2. #include<iostream>
  3. #include<cstdio>
  4. using namespace std;
  5. int num[1005];
  6. int main()
  7. {
  8.     int t,n,ans;
  9.     scanf("%d",&t);
  10.     while(t--)
  11.     {
  12.         scanf("%d",&n);
  13.         ans=0;
  14.         for(int i=1;i<=n;i++)
  15.         {
  16.             scanf("%d",&num[i]);
  17.             ans+=num[i]*num[i];
  18.         }
  19.         printf("%d\n",ans);
  20.     }
  21.     return 0;
  22. }
  1. //Java
  2. import java.util.*;
  3. import java.io.*;
  4. public class Main {
  5.     public static void main(String[] args){
  6.         Scanner cin = new Scanner(System.in);
  7.         int t=cin.nextInt();
  8.         int n,ans;
  9.         int[] num=new int[1005];
  10.         while(t>0){
  11.             t--;
  12.             n=cin.nextInt();
  13.             ans=0;
  14.             for(int i=1;i<=n;i++){
  15.                 num[i]=cin.nextInt();
  16.                 ans+=num[i]*num[i];
  17.             }
  18.             System.out.println(ans);
  19.         }
  20.     }
  21. }

B 寻找中位数(1)

    根据中位数的定义，如果我们先把数列排序，那么当N为奇数时，中位数就是数列中间位置的那个数，当N为偶数时，中位数就是数列中间位置的那两个数的平均值。
    对于N<=1000的数据规模，我们可以采取冒泡排序或者选择排序等时间复杂度为o(N^2)的方法。这里提供的是选择排序的版本。
    时间复杂度o(T*N^2)，空间复杂度o(N)。

代码

  1. //C++
  2. #include<iostream>
  3. #include<cstdio>
  4. using namespace std;
  5. int num[1005];
  6. int main()
  7. {
  8.     int t,n,temp;
  9.     double ans;
  10.     scanf("%d",&t);
  11.     while(t--)
  12.     {
  13.         scanf("%d",&n);
  14.         for(int i=1;i<=n;i++)
  15.             scanf("%d",&num[i]);
  16.         for(int i=1;i<n;i++)
  17.             for(int j=i+1;j<=n;j++)
  18.             {
  19.                 if(num[j]<num[i])
  20.                 {
  21.                     temp=num[i];
  22.                     num[i]=num[j];
  23.                     num[j]=temp;
  24.                 }
  25.             }
  26.         if(n%2==1)
  27.             ans=num[(n+1)/2];
  28.         else
  29.             ans=(num[n/2]+num[n/2+1])*0.5;
  30.         printf("%.2f\n",ans);
  31.     }
  32.     return 0;
  33. }
  1. //Java
  2. import java.util.*;
  3. import java.io.*;
  4. public class Main {
  5.     public static void main(String[] args){
  6.         Scanner cin = new Scanner(System.in);
  7.         int t=cin.nextInt();
  8.         int n,temp;
  9.         double ans;
  10.         int[] num=new int[1005];
  11.         while(t>0){
  12.             t--;
  13.             n=cin.nextInt();
  14.             for(int i=1;i<=n;i++)
  15.                 num[i]=cin.nextInt();
  16.             for(int i=1;i<n;i++)
  17.                 for(int j=i+1;j<=n;j++){
  18.                     if(num[j]<num[i]){
  19.                         temp=num[i];
  20.                         num[i]=num[j];
  21.                         num[j]=temp;
  22.                     }
  23.                 }
  24.             if(n%2==1)
  25.                 ans=num[(n+1)/2];
  26.             else
  27.                 ans=(num[n/2]+num[n/2+1])*0.5;
  28.             System.out.println(String.format("%.2f", ans));
  29.         }
  30.     }
  31. }

C 安排数(1)

    枚举从(a，b]中的每个数，如果这个数满足题目的两个条件，那么安排数的个数加一。最后输出有多少个安排数即可。
    时间复杂度o(T*(b-a))，空间复杂度o(1)。

代码

  1. //C++
  2. #include<iostream>
  3. #include<cstdio>
  4. using namespace std;
  5. bool have7(int x)
  6. {
  7.     while(x!=0)
  8.     {
  9.         if(x%10==7)
  10.             return 1;
  11.         x=x/10;
  12.     }
  13.     return 0;
  14. }
  15. int main()
  16. {
  17.     int t,a,b,ans;
  18.     scanf("%d",&t);
  19.     while(t--)
  20.     {
  21.         scanf("%d%d",&a,&b);
  22.         ans=0;
  23.         for(int i=a+1;i<=b;i++)
  24.         {
  25.             if(i%7==0 && have7(i))
  26.                 ans++;
  27.         }
  28.         printf("%d\n",ans);
  29.     }
  30.     return 0;
  31. }
  1. //Java
  2. import java.util.*;
  3. import java.io.*;
  4. public class Main {
  5.     public static boolean have7(int x){
  6.         while(x!=0){
  7.             if(x%10==7)
  8.                 return true;
  9.             x=x/10;
  10.         }
  11.         return false;
  12.     }
  13.     public static void main(String[] args){
  14.         Scanner cin = new Scanner(System.in);
  15.         int t=cin.nextInt();
  16.         int a,b,ans;
  17.         while(t>0){
  18.             t--;
  19.             ans=0;
  20.             a=cin.nextInt();
  21.             b=cin.nextInt();
  22.             for(int i=a+1;i<=b;i++){
  23.                 if(i%7==0 && have7(i))
  24.                     ans++;
  25.             }
  26.             System.out.println(ans);
  27.         }
  28.     }
  29. }

D 寻找中位数(2)

    题目和B几乎相同，区别在于数据范围。
    对于N<=100000而且ai<=1000000000的数据规模，我们可以采取快速排序、归并排序或者堆排序等时间复杂度为o(N*log(N))的方法。这里提供的是库函数排序的版本。
    这里给出一个三种常见o(N*log(N))排序方法的伪代码版本(java)，有兴趣的同学可以查看，并自行进行更深入的了解。blog.csdn.net/wkyworkuno/article/details/66091709
    时间复杂度o(T*N*log(N))，空间复杂度o(N)。

代码

  1. //C++
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<algorithm>
  5. using namespace std;
  6. int num[100005];
  7. int main()
  8. {
  9.     int t,n,temp;
  10.     double ans;
  11.     scanf("%d",&t);
  12.     while(t--)
  13.     {
  14.         scanf("%d",&n);
  15.         ans=0;
  16.         for(int i=1;i<=n;i++)
  17.             scanf("%d",&num[i]);
  18.         sort(num+1,num+1+n);
  19.         if(n%2==1)
  20.             ans=num[(n+1)/2];
  21.         else
  22.             ans=(num[n/2]+num[n/2+1])*0.5;
  23.         printf("%.2f\n",ans);
  24.     }
  25.     return 0;
  26. }
  1. //Java
  2. import java.util.*;
  3. import java.io.*;
  4. public class Main {
  5.     public static void main(String[] args){
  6.         Scanner cin = new Scanner(System.in);
  7.         int t=cin.nextInt();
  8.         int n,temp;
  9.         double ans;
  10.         int[] num=new int[100005];
  11.         while(t>0){
  12.             t--;
  13.             n=cin.nextInt();
  14.             for(int i=1;i<=n;i++)
  15.                 num[i]=cin.nextInt();
  16.             Arrays.sort(num,1,1+n);
  17.             if(n%2==1)
  18.                 ans=num[(n+1)/2];
  19.             else
  20.                 ans=(num[n/2]+num[n/2+1])*0.5;
  21.             System.out.println(String.format("%.2f", ans));
  22.         }
  23.     }
  24. }

E 安排数(2)

    题目和C几乎相同，区别在于数据范围。
    对于T<=100000的数据范围，如果时间复杂度还是o(T*(b-a))，那么肯定会超时。
    这里我们要用到一个小技巧：区间和等于两个前缀和的差。
    具体来说，如果S[i]表示a[1]+a[2]+……+a[i]的和，那么a[l+1]+a[l+2]+……+a[r]就可以用S[r]-S[l]来表示。所以我们只需要求出S数组即可。
    时间复杂度o(max(b)+T)，空间复杂度o(max(b)+T)。

代码

  1. //C++
  2. #include<iostream>
  3. #include<cstdio>
  4. using namespace std;
  5. int ans[1000005];
  6. bool have7(int x)
  7. {
  8.     while(x!=0)
  9.     {
  10.         if(x%10==7)
  11.             return 1;
  12.         x=x/10;
  13.     }
  14.     return 0;
  15. }
  16. int main()
  17. {
  18.     int t,a,b;
  19.     scanf("%d",&t);
  20.     for(int i=1;i<=1000000;i++)
  21.     {
  22.         ans[i]=ans[i-1];
  23.         if(i%7==0 && have7(i))
  24.             ans[i]++;
  25.     }
  26.     while(t--)
  27.     {
  28.         scanf("%d%d",&a,&b);
  29.         printf("%d\n",ans[b]-ans[a]);
  30.     }
  31.     return 0;
  32. }
  1. //Java
  2. import java.util.*;
  3. import java.io.*;
  4. public class Main {
  5.     public static boolean have7(int x){
  6.         while(x!=0){
  7.             if(x%10==7)
  8.                 return true;
  9.             x=x/10;
  10.         }
  11.         return false;
  12.     }
  13.     public static void main(String[] args){
  14.         Scanner cin = new Scanner(System.in);
  15.         int t=cin.nextInt();
  16.         int[] ans=new int[1000005];
  17.         int a,b;
  18.         for(int i=1;i<=1000000;i++){
  19.             ans[i]=ans[i-1];
  20.             if(i%7==0 && have7(i))
  21.                 ans[i]++;
  22.         }
  23.         while(t>0){
  24.             t--;
  25.             a=cin.nextInt();
  26.             b=cin.nextInt();
  27.             System.out.println(ans[b]-ans[a]);
  28.         }
  29.     }
  30. }

F 最大公因数之和

    朴素的想法是枚举数列中的任何一对数，求出他们的最大公因数加到答案中。这样计算一组数据的时间复杂度o(f*N^2)，这里的f指的是求两个数的gcd所耗费的时间。即使这个f非常小，光是N^2已经很大了，而且还要乘上组数T，所以这样肯定会超时。
    我们换个思路：如果x和y都是z的倍数，那么gcd(x,y)肯定是z的倍数。如果有k个数都是z的倍数，那么在这k个数中任意选择一对，他们的gcd肯定也是z的倍数，所以我们只需要求出对于每个z数列中有多少个数是z的倍数即可。如果对于每个z，我们知道数列中有多少对数字的gcd恰好等于z，那么我们把对数和z相乘，就是这个值对答案的贡献，枚举z把贡献算出来全加上，就是答案。
    我们注意到，之前我们说的是gcd是z的倍数，但是我们要求的是gcd恰好为z的。所以我们要将gcd是z的倍数(包括z)的数字有多少对，减去gcd是z的倍数(不包括z)的数字有多少对，剩下的就是gcd恰好为z的。举个例子：我们用gcd=5的倍数对数减去gcd恰好为10、gcd恰好为15、……剩下的就是gcd恰好为5的。
    关于如何计算每个z在数列中有多少个倍数，我们可以反过来，对于数列中每个数，把它的因数的出现次数加一。枚举x的因数的时间复杂度是o(sqrt(x))。
    同样，我们也不必枚举每个z的倍数再减去。我们可以从大到小枚举z，当前z的每个因数(除了z本身)，都要减去gcd恰好为z的，我们用另外一个数组储存。同样，对于每个z，枚举因数的时间复杂度是o(sqrt(z))。
    这样我们可以从大到小算出gcd恰好等于每个z的数字的对数，乘上z再加起来，就是最终答案。因为两个正整数的gcd肯定小于等于他们当中较小的那个，所以z不会超过数列数字的上限。
    时间复杂度o(T*(max(a)+N)*sqrt(max(a)))，空间复杂度o(max(a)+N)。

代码

  1. //C++
  2. #include<iostream>
  3. #include<cstdio>
  4. using namespace std;
  5. int a[10005];
  6. long long del[10005];
  7. long long nums[10005];
  8. long long ans[10005];
  9. int main()
  10. {
  11.     int t,n;
  12.     long long sumans;
  13.     scanf("%d",&t);
  14.     while(t--)
  15.     {
  16.         scanf("%d",&n);
  17.         sumans=0;
  18.         for(int i=1;i<=10000;i++)
  19.             nums[i]=0;
  20.         for(int i=1;i<=n;i++)
  21.         {
  22.             scanf("%d",&a[i]);
  23.             for(int j=1;j*j<=a[i];j++)
  24.             {
  25.                 if(a[i]%j==0)
  26.                 {
  27.                     nums[j]++;
  28.                     if(a[i]/j!=j)
  29.                         nums[a[i]/j]++;
  30.                 }
  31.             }
  32.         }
  33.         for(int i=1;i<=10000;i++)
  34.             del[i]=0;
  35.         for(int i=10000;i>1;i--)
  36.         {
  37.             ans[i]=(nums[i]*(nums[i]-1))/2-del[i];
  38.             del[1]+=ans[i];
  39.             for(int j=2;j*j<=i;j++)
  40.             {
  41.                 if(i%j==0)
  42.                 {
  43.                     del[j]+=ans[i];
  44.                     if(j!=i/j)
  45.                         del[i/j]+=ans[i];
  46.                 }
  47.             }
  48.         }
  49.         ans[1]=(nums[1]*(nums[1]-1))/2-del[1];
  50.         for(int i=1;i<=10000;i++)
  51.             sumans+=i*ans[i];
  52.         printf("%lld\n",sumans);
  53.     }
  54.     return 0;
  55. }
  1. //Java
  2. import java.util.*;
  3. import java.io.*;
  5. public class Main {
  6.     public static void main(String[] args){
  7.         Scanner cin = new Scanner(System.in);
  8.         int t=cin.nextInt();
  9.         int[] a=new int[10005];
  10.         long [] nums=new long[10005];
  11.         long [] ans=new long[10005];
  12.         long [] del=new long[10005];
  13.         long sumans;
  14.         int n;
  15.         while(t>0){
  16.             t--;
  17.             sumans=0;
  18.             n=cin.nextInt();
  19.             for(int i=1;i<=10000;i++)
  20.                 nums[i]=0;
  21.             for(int i=1;i<=n;i++){
  22.                 a[i]=cin.nextInt();
  23.                 for(int j=1;j*j<=a[i];j++){
  24.                     if(a[i]%j==0){
  25.                         nums[j]++;
  26.                         if(a[i]/j!=j)
  27.                             nums[a[i]/j]++;
  28.                     }
  29.                 }
  30.             }
  31.             for(int i=1;i<=10000;i++)
  32.                 del[i]=0;
  33.             for(int i=10000;i>1;i--){
  34.                 ans[i]=(nums[i]*(nums[i]-1))/2-del[i];
  35.                 del[1]+=ans[i];
  36.                 for(int j=2;j*j<=i;j++){
  37.                     if(i%j==0){
  38.                         del[j]+=ans[i];
  39.                         if(j!=i/j)
  40.                             del[i/j]+=ans[i];
  41.                     }
  42.                 }
  43.             }
  44.             ans[1]=(nums[1]*(nums[1]-1))/2-del[1];
  45.             for(int i=1;i<=10000;i++)
  46.                 sumans+=i*ans[i];
  47.             System.out.println(sumans);
  48.         }
  49.     }
  50. }

G 超级斐波那契数列

    F(i+1)=F(i)+F(i-1)。
    我们构造一个2*1的矩阵M[i]={{F(i-1)},{F(i)}}，再构造一个2*2的矩阵A={{0,1},{1,1}}，根据矩阵乘法如果M[i]左乘上A，结果是一个2*1的矩阵{{F[i]},{F[i]+F[i-1]}}即{{F[i]},{F[i+1]}}，我们记为矩阵M[i+1]。很明显，M[i]左乘j次A，结果就是M[i+j]。
    S1(i+1)=S1(i)+F(i+1)=S1(i)+F(i)+F(i-1)。
    S2(i+1)=S2(i)+S1(i+1)=S2(i)+S1(i)+F(i+1)=S2(i)+S1(i)+F(i)+F(i-1)。
    以此类推。
    可以想象，如果我们构造一个10*1的矩阵M[i]={{F(i-1)},{F(i)},{S1(i)},{S2(i)},{S3(i)},{S4(i)},{S5(i)},{S6(i)},{S7(i)},{S8(i)}}，也会存在一个10*10的矩阵A令A*M[i]=M[i+1]。
    这样我们可以通过构造M[1]和A，让M[1]左乘N-1次A求得M[N]，M[N]的最后一行就是S8(N)。这样做的时间复杂度是o(100*N)，不用我说你们也知道会超时了，这甚至比暴力计算还满。
    但是矩阵乘法是满足结合律的(圈起来，这个要考)。我们可以将A的N-1次方进行二进制分解，比如A^7=A^4*A^2*A，如果我们事先求得矩阵A的1次方(即A本身)、2次方、4次方、8次方、16次方……我们就可以通过将这些矩阵中的一部分相乘求出A^(N-1)。很容易看出来N最多分解为log2(N)项。所以时间复杂度就变成了o(1000*log2(N))。这里的1000表示的是10*10的两个方阵相乘的复杂度，而之前的100指的是10*1的矩阵左乘10*10的矩阵。
    时间复杂度o(T*1000*log2(N))，空间复杂度o(100)。

代码

  1. //C++
  2. #include<iostream>
  3. #include<cstdio>
  4. using namespace std;
  5. #define mod 1000000007
  6. struct Node
  7. {
  8.     long long num[10][10];
  9.     friend Node operator *(Node x1,Node x2)
  10.     {
  11.         Node x3;
  12.         for(int i=0;i<10;i++)
  13.             for(int j=0;j<10;j++)
  14.                 x3.num[i][j]=0;
  15.         for(int i=0;i<10;i++)
  16.             for(int k=0;k<10;k++)
  17.                 for(int j=0;j<10;j++)
  18.                     x3.num[i][j]=(x3.num[i][j]+x1.num[i][k]*x2.num[k][j])%mod;
  19.         return x3;
  20.     }
  21. }A,E;
  22. Node ksm(long long y)
  23. {
  24.     Node nowans=E,x=A;
  25.     while(y)
  26.     {
  27.         if(y%2)
  28.             nowans=x*nowans;
  29.         x=x*x;
  30.         y=y/2;
  31.     }
  32.     return nowans;
  33. }
  34. int main()
  35. {
  36.     for(int i=0;i<10;i++)
  37.         E.num[i][i]=1;
  38.     A.num[0][1]=1;
  39.     for(int i=1;i<10;i++)
  40.         for(int j=0;j<=i;j++)
  41.             A.num[i][j]=1;
  42.     int t;
  43.     long long n,ans;
  44.     scanf("%d",&t);
  45.     while(t--)
  46.     {
  47.         scanf("%lld",&n);
  48.         ans=0;
  49.         Node now=ksm(n-1);
  50.         for(int i=1;i<10;i++)
  51.             ans=(ans+now.num[9][i])%mod;
  52.         printf("%lld\n",ans);
  53.     }
  54.     return 0;
  55. }
  1. //Java
  2. import java.util.*;
  3. import java.io.*;
  4. class Node{
  5.     long[][] num=new long[10][10];
  6.     Node mul(Node x2){
  7.         Node x3=new Node();
  8.         for(int i=0;i<10;i++)
  9.             for(int k=0;k<10;k++)
  10.                 for(int j=0;j<10;j++)
  11.                     x3.num[i][j]=(x3.num[i][j]+num[i][k]*x2.num[k][j])%1000000007;
  12.         return x3;
  13.     }
  14. }
  15. public class Main {
  16.     static Node E=new Node(),A=new Node();
  17.     static Node ksm(long y){
  18.         Node nowans=E,x=A;
  19.         while(y!=0){
  20.             if(y%2==1)
  21.                 nowans=nowans.mul(x);
  22.             x=x.mul(x);
  23.             y=y/2;
  24.         }
  25.         return nowans;
  26.     }
  27.     public static void main(String[] args){
  28.         Scanner cin = new Scanner(System.in);
  29.         for(int i=0;i<10;i++)
  30.             E.num[i][i]=1;
  31.         A.num[0][1]=1;
  32.         for(int i=1;i<10;i++)
  33.             for(int j=0;j<=i;j++)
  34.                 A.num[i][j]=1;
  35.         int t;
  36.         long n,ans;
  37.         t=cin.nextInt();
  38.         while(t>0)
  39.         {
  40.             t--;
  41.             n=cin.nextLong();
  42.             ans=0;
  43.             Node now=ksm(n-1);
  44.             for(int i=1;i<10;i++)
  45.                 ans=(ans+now.num[9][i])%1000000007;
  46.             System.out.println(ans);
  47.         }
  48.     }
  49. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注