[关闭]
@CQUPTacm 2018-04-20T22:00:03.000000Z 字数 16188 阅读 2183

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

题解

先恭喜各位成功晋级决赛的同学，具体晋级名单将在查重结束后发布。同时也为本次比赛过程中我们的各种准备不周向各位选手道个歉。

A 后山的宝藏

    本题的关键之处在于“当前方向”。解释一下样例也许各位就明白了：
    初始：位于(0,0)，面向北方。
    第一步：向后转，前进100。此时位于(0,-100)，面向南方。
    第二步：向右转。此时位于(0,-100)，面向西方。
    第三步：前进10。此时位于(-10,-100)，面向西方。
    第四步：找到宝藏。输出-10 -100。
    另外有一个值得注意的地方，每次移动的距离最多是100000，最多行动的次数是100000，也就是说，如果一直向前移动100000，移动100000次，最后的位置是(0,100000*100000)，而int的上限是2^31-1。你们可以按一下计算器，比较一下。所以本题的位置要用long long来储存。
    ps：首页提示的第一条就提到了“爆int”的情况。
    时间复杂度o(行动数)，空间复杂度o(1)。

代码

  1. //C++
  2. #include<iostream>
  3. #include<stdio.h>
  4. using namespace std;
  6. int dic[4][2]={0,1,1,0,0,-1,-1,0}; //四个方向的位移影响
  7. char s[6];
  9. int main()
  10. {
  11.     long long nx=0,ny=0; //当前位置
  12.     int d=0,x; //d是当前方向的编号
  13.     while(scanf("%s",s))
  14.     {
  15.         if(s[0]=='F')
  16.             break;
  17.         if(s[0]=='W')
  18.         {
  19.             scanf("%d",&x);
  20.             nx+=dic[d][0]*x;
  21.             ny+=dic[d][1]*x;
  22.         }
  23.         if(s[0]=='S')
  24.         {
  25.             d=(d+2)%4;
  26.             scanf("%d",&x);
  27.             nx+=dic[d][0]*x;
  28.             ny+=dic[d][1]*x;
  29.         }
  30.         if(s[0]=='D')
  31.             d=(d+1)%4;
  32.         if(s[0]=='A')
  33.             d=(d-1+4)%4;
  34.     }
  35.     printf("%lld %lld\n",nx,ny);
  36.     return 0;
  37. }
  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[][] dic={{0,1},{1,0},{0,-1},{-1,0}}; //四个方向的位移影响
  8.         long nx=0,ny=0; //当前位置
  9.         int d=0,x; //d是当前方向的编号
  10.         String s;
  11.         while(true){
  12.             s=cin.next();
  13.             if(s.equals("Find!"))
  14.                 break;
  15.             if(s.equals("W")){
  16.                 x=cin.nextInt();
  17.                 nx+=dic[d][0]*x;
  18.                 ny+=dic[d][1]*x;
  19.             }
  20.             if(s.equals("S")){
  21.                 d=(d+2)%4;
  22.                 x=cin.nextInt();
  23.                 nx+=dic[d][0]*x;
  24.                 ny+=dic[d][1]*x;
  25.             }
  26.             if(s.equals("D"))
  27.                 d=(d+1)%4;
  28.             if(s.equals("A"))
  29.                 d=(d-1+4)%4;
  30.         }
  31.         System.out.println(nx+" "+ny);
  32.     }
  33. }

B 抢修水管

    很多同学对题目的理解有误，所以我们先来理一下题目。
    首先我们输出数字的前提，是“能找到是哪一米的水管出问题了”。换句话说，只剩一米水管有嫌疑的情况下，我们才能确定，是这一米水管出问题了。
    反过来，如果不止一米水管有嫌疑，那么我们就不能确定答案，应该输出“No response!”。
    许多同学对“数据保证有且仅有一处水管断裂，并且断裂不出现在整数米处。”这句话产生了误解。这句话表达的含义其实是：至少剩一米水管有嫌疑，不可能出现所有水管都是完好的。
    所以我们把水管分成L段1米长的。对于每次检查，把提到的那些段水管的嫌疑都去掉，最后计算还有几段水管有嫌疑，如果只有一段，就输出答案，否则输出“No response!”。
    时间复杂度o(L*M)，空间复杂度o(L)。

  1. //C++
  2. #include<iostream>
  3. #include<stdio.h>
  4. using namespace std;
  6. bool life[1005]; //life为0代表有嫌疑
  8. int main()
  9. {
  10.     int l,m,x,y,ans,flag=0; //flag是有嫌疑的段数，ans是有嫌疑的段左边的位置
  11.     scanf("%d%d",&l,&m);
  12.     while(m--)
  13.     {
  14.         scanf("%d%d",&x,&y);
  15.         for(int i=x;i<y;i++)
  16.             life[i]=1;
  17.     }
  18.     for(int i=0;i<l;i++)
  19.     {
  20.         if(!life[i])
  21.         {
  22.             ans=i;
  23.             flag++;
  24.         }
  25.     }
  26.     if(flag>1)
  27.         printf("No response!\n");
  28.     else
  29.         printf("%d\n",ans);
  30.     return 0;
  31. }
  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 l,m,x,y,ans=-1,flag=0; //flag是有嫌疑的段数，ans是有嫌疑的段左边的位置
  8.         boolean[] life=new boolean[1005]; //life为false代表有嫌疑
  9.         l=cin.nextInt();
  10.         m=cin.nextInt();
  11.         while(m>0){
  12.             m--;
  13.             x=cin.nextInt();
  14.             y=cin.nextInt();
  15.             for(int i=x;i<y;i++)
  16.                 life[i]=true;
  17.         }
  18.         for(int i=0;i<l;i++){
  19.             if(!life[i]){
  20.                 ans=i;
  21.                 flag++;
  22.             }
  23.         }
  24.         if(flag>1)
  25.             System.out.println("No response!");
  26.         else
  27.             System.out.println(ans);
  28.     }
  29. }

C 破解密码

    这题其实是一道难度偏高的题，但是有很多同学去进行了尝试。
    ps：首页提示的第五条就是“题目难度与顺序无关”。
    先解释一下题目中的“密码”。
    密码=满足（由N位数字组成，且每连续M个数字之和都是质数）这一条件的数字串个数。以N=5，M=2为例，数字串应该满足：1.由5位数字组成；2.每连续2位数字的和是质数。即：第1位+第2位，第2位+第3位，第3位+第4位，第4位+第5位的和都是质数。
    大部分过题的同学采取的是打表的方法，因为输入一共只有12*4=48种。
    标程的解法是动态规划：
    dp[i][j]表示只考虑前i位组成的满足每连续M位的和都是质数，并且最后M位组成的数字是j的数字串的个数。
    那么我们枚举当前也就是第i+1位的数字k，可以知道加上第i+1位的k，新的数字串的结尾M个数字组成的数应该是(j*10)%(10^M)+k，所以dp[i+1][(j*10)%(10^M)+k]应该加上dp[i][j]这么多种情况。
    怎么保证每连续M位的和都是质数呢？从i=M开始，我们每次都对最后M位进行审查，如果j的每个位子上的数的和不是质数，就让dp[i][j]=0。所以没清零的那些数字串，都可以保证每连续M位的和都是质数。
    时间复杂度o(N*(10^M)*10)，空间复杂度o(N*(10^M))。

  1. //C++
  2. #include<iostream>
  3. #include<stdio.h>
  5. using namespace std;
  7. int n,m;
  8. int m10; //m10=10^m
  9. long long dp[15][10005]; //dp[i][j]表示只考虑前i位组成的满足每连续M位的和都是质数，并且最后M位组成的数字是j的数字串的个数
  10. bool prime[105]; //prime[i]=1代表i是质数
  12. int sum(int x) //求x各个位置上的数的和
  13. {
  14.     int now=0;
  15.     for(int i=1;i<=m;i++)
  16.     {
  17.         now+=x%10;
  18.         x=x/10;
  19.     }
  20.     return now;
  21. }
  22. long long solve()
  23. {
  24.     long long ans=0;
  25.     if(n<m)
  26.         return 0;
  27.     for(int i=0;i<=n;i++)
  28.         for(int j=0;j<m10;j++)
  29.             dp[i][j]=0;
  30.     dp[0][0]=1;
  31.     for(int i=1;i<=n;i++) //考虑前i个数字
  32.     {
  33.         for(int j=0;j<m10;j++) //考虑前i-1位组成的数字串的末尾M位数字
  34.         {
  35.             for(int k=0;k<10;k++) //考虑当前位的数字
  36.                 dp[i][(j*10)%m10+k]+=dp[i-1][j];
  37.         }
  38.         if(i>=m) //当i大于等于M时，清空不符合要求的数字串
  39.         {
  40.             for(int j=0;j<m10;j++)
  41.             {
  42.                 if(!prime[sum(j)])
  43.                     dp[i][j]=0;
  44.             }
  45.         }
  46.     }
  47.     for(int i=0;i<m10;i++) //计算答案
  48.         ans+=dp[n][i];
  49.     return ans;
  50. }
  52. int main()
  53. {
  54.     for(int i=2;i<=36;i++) //最多4个9相加只有36，判断36以内的质数有哪些
  55.     {
  56.         bool flag=0;
  57.         for(int j=2;j<i;j++)
  58.         {
  59.             if(i%j==0)
  60.             {
  61.                 flag=1;
  62.             }
  63.         }
  64.         if(flag==0)
  65.             prime[i]=1;
  66.     }
  67.     scanf("%d%d",&n,&m);
  68.     m10=1;
  69.     for(int i=1;i<=m;i++)
  70.         m10*=10; //求10的m次方
  71.     printf("%lld\n",solve());
  72.     return 0;
  73. }
  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 n,m;
  8.         n=cin.nextInt();
  9.         m=cin.nextInt();
  10.         long[][] dp=new long[15][10005]; //dp[i][j]表示只考虑前i位组成的满足每连续M位的和都是质数，并且最后M位组成的数字是j的数字串的个数
  11.         boolean[] prime=new boolean[105]; //prime[i]=1代表i是质数
  12.         int m10; //m10=10^m
  13.         m10=1;
  14.         for(int i=1;i<=m;i++)
  15.             m10*=10; //求10的m次方
  16.         for(int i=2;i<=36;i++){ //最多4个9相加只有36，判断36以内的质数有哪些
  17.             boolean flag=false;
  18.             for(int j=2;j<i;j++){
  19.                 if(i%j==0){
  20.                     flag=true;
  21.                 }
  22.             }
  23.             if(flag==false)
  24.                 prime[i]=true;
  25.         }
  26.         long ans=0;
  27.         if(n>=m){
  28.             for(int i=0;i<=n;i++)
  29.                 for(int j=0;j<m10;j++)
  30.                     dp[i][j]=0;
  31.             dp[0][0]=1;
  32.             for(int i=1;i<=n;i++){ //考虑前i个数字
  33.                 for(int j=0;j<m10;j++){ //考虑前i-1位组成的数字串的末尾M位数字
  34.                     for(int k=0;k<10;k++) //考虑当前位的数字
  35.                         dp[i][(j*10)%m10+k]+=dp[i-1][j];
  36.                 }
  37.                 if(i>=m){ //当i大于等于M时，清空不符合要求的数字串
  38.                     for(int j=0;j<m10;j++){
  39.                         int now=0,temp=j; //now是j各个位置上的数的和
  40.                         for(int tempi=1;tempi<=m;tempi++){
  41.                             now+=temp%10;
  42.                             temp=temp/10;
  43.                         }
  44.                         if(!prime[now])
  45.                             dp[i][j]=0;
  46.                     }
  47.                 }
  48.             }
  49.             for(int i=0;i<m10;i++) //计算答案
  50.                 ans+=dp[n][i];
  51.         }
  52.         System.out.println(ans);
  53.     }
  54. }

D 熄灯的工作

    设bi为1表示按下第i个开关，p(j，i)为1表示第i个开关能控制第j个灯，那么题目就变为，求对于每个j，(p[j，1]&b1)^((p[j，2]&b2))^...(p[j，M]&bM)=1的N个M元方程组成的线性方程组是否有解。其中^表示异或，&表示与。
    其中，p[j,i]是一个N行M列的系数矩阵，它的增广矩阵是在右边加一列1。增广矩阵的秩如果和系数矩阵相同，则有解。剩下的就是矩阵求秩的问题了，标程用到的方法是高斯消元。标程写的丑，同学们可以去网上找高斯消元的代码看。
    时间复杂度o(M*N*M)，空间复杂度o(N*M)。

  1. //C++
  2. #include<iostream>
  3. #include<stdio.h>
  4. using namespace std;
  6. bool mat[105][105]; //矩阵
  8. bool gg(int x,int y) //判断第x行的前y个数字是不是都是0
  9. {
  10.     for(int i=1;i<=y;i++)
  11.     {
  12.         if(mat[x][i])
  13.             return 0;
  14.     }
  15.     return 1;
  16. }
  18. int main()
  19. {
  20.     int n,m,x,t;
  21.     bool flag=0,temp;
  22.     scanf("%d%d",&n,&m);
  23.     for(int i=1;i<=m;i++) //根据输入生成系数矩阵
  24.     {
  25.         scanf("%d",&x);
  26.         while(x--)
  27.         {
  28.             scanf("%d",&t);
  29.             mat[t][i]=1;
  30.         }
  31.     }
  32.     for(int i=1;i<=n;i++) //变系数矩阵为增广矩阵
  33.         mat[i][m+1]=1;
  34.     for(int i=1;i<=m;i++) //高斯消元
  35.     {
  36.         for(int j=1;j<=n;j++)
  37.         {
  38.             if(mat[j][i] && gg(j,i-1))
  39.             {
  40.                 for(int k=1;k<=n;k++)
  41.                 {
  42.                     if(k!=j && mat[k][i])
  43.                     {
  44.                         for(int g=i;g<=m+1;g++)
  45.                             mat[k][g]^=mat[j][g];
  46.                     }
  47.                 }
  48.                 break;
  49.             }
  50.         }
  51.     }
  52.     for(int i=1;i<=n;i++) //判断系数矩阵和增广矩阵的秩是否相同
  53.     {
  54.         temp=0;
  55.         for(int j=1;j<=m;j++)
  56.         {
  57.             if(mat[i][j])
  58.             {
  59.                 temp=1;
  60.                 break;
  61.             }
  62.         }
  63.         if(!temp && mat[i][m+1])
  64.         {
  65.             flag=1;
  66.             break;
  67.         }
  68.     }
  69.     if(!flag)
  70.         printf("YES\n");
  71.     else
  72.         printf("NO\n");
  73.     return 0;
  74. }
  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.         boolean[][] mat=new boolean[105][105]; //矩阵
  8.         int n,m,x,t;
  9.         boolean flag=false,temp;
  10.         n=cin.nextInt();
  11.         m=cin.nextInt();
  12.         for(int i=1;i<=m;i++){ //根据输入生成系数矩阵
  13.             x=cin.nextInt();
  14.             while(x>0){
  15.                 x--;
  16.                 t=cin.nextInt();
  17.                 mat[t][i]=true;
  18.             }
  19.         }
  20.         for(int i=1;i<=n;i++) //变系数矩阵为增广矩阵
  21.             mat[i][m+1]=true;
  22.         for(int i=1;i<=m;i++){ //高斯消元
  23.             for(int j=1;j<=n;j++){
  24.                 boolean gg=true; //gg表示第j行的前i-1个数是不是都是0
  25.                 for(int tempi=1;tempi<=i-1;tempi++){
  26.                     if(mat[j][tempi])
  27.                         gg=false;
  28.                 }
  29.                 if(mat[j][i] && gg){
  30.                     for(int k=1;k<=n;k++){
  31.                         if(k!=j && mat[k][i]){
  32.                             for(int g=i;g<=m+1;g++)
  33.                                 mat[k][g]^=mat[j][g];
  34.                         }
  35.                     }
  36.                     break;
  37.                 }
  38.             }
  39.         }
  40.         for(int i=1;i<=n;i++){ //判断系数矩阵和增广矩阵的秩是否相同
  41.             temp=false;
  42.             for(int j=1;j<=m;j++){
  43.                 if(mat[i][j]){
  44.                     temp=true;
  45.                     break;
  46.                 }
  47.             }
  48.             if(!temp && mat[i][m+1]){
  49.                 flag=true;
  50.                 break;
  51.             }
  52.         }
  53.         if(!flag)
  54.             System.out.println("YES");
  55.         else
  56.             System.out.println("NO");
  57.     }
  58. }

E 饭点的食堂

    题意抽象出来，其实就是做一个支持插队功能的队列。(插队是万恶之源。。。没有插队这题太简单了)实现插队功能我们很容易想到链表。所以我们用链表做一个队列。还剩下最后一个问题，怎么查找插队的位置呢？如果按照链表查找某个节点的方法，从头一个一个查的话，时间和链表长度成正比，而插队次数又很可能是和变动数一个级别的，这会导致超时。
    所以我们把链表的地址和同学的编号绑定起来，即x号同学就放在地址x，这样我们就可以根据编号查询插队位置。所以我们的链表的next指针本质上是维护后面那个同学的编号。
    为了实现排队功能，我们还需要记录队尾那个人的序号。同样为了实现打饭功能，我们要记录队首那个人的序号。
    至于查询同学状态，我们在一开始将所有的同学设置成“coming”，在同学排队或者插队的时候把他的状态改为“waiting”，在他打饭的时候把他的状态设置成“eating”就可以了。
    时间复杂度o(变动数)，空间复杂度o(编号范围)。

  1. //C++
  2. #include<iostream>
  3. #include<stdio.h>
  5. using namespace std;
  7. int nex[500005]; //相当于next指针
  8. int status[500005]; //记录状态，0表示coming，1表示waiting，2表示eating
  9. char s[6];
  11. int main()
  12. {
  13.     int n,x,y,tail; //tail记录队尾同学的编号，为0表示队伍为空
  14.     scanf("%d",&n);
  15.     tail=0;
  16.     while(n--)
  17.     {
  18.         scanf("%s",s);
  19.         if(s[0]=='p')
  20.         {
  21.             scanf("%d",&x);
  22.             status[x]=1;
  23.             nex[tail]=x;
  24.             tail=x;
  25.         }
  26.         if(s[0]=='d')
  27.         {
  28.             x=nex[0];
  29.             status[x]=2;
  30.             nex[0]=nex[x];
  31.             if(tail==x) //如果队伍里只剩一个人，此时要把队伍排空，要更改tail
  32.                 tail=nex[x];
  33.         }
  34.         if(s[0]=='c')
  35.         {
  36.             scanf("%d %d",&x,&y);
  37.             status[x]=1;
  38.             nex[x]=nex[y];
  39.             nex[y]=x;
  40.             if(tail==y) //如果y是原本队伍的最后一个，此时x就变成队伍最后了，要更改tail
  41.                 tail=nex[tail];
  42.         }
  43.         if(s[0]=='x')
  44.         {
  45.             scanf("%d",&x);
  46.             if(status[x]==0)
  47.                 printf("coming\n");
  48.             if(status[x]==1)
  49.                 printf("waiting\n");
  50.             if(status[x]==2)
  51.                 printf("eating\n");
  52.         }
  53.     }
  54.     return 0;
  55. }
  1. //Java
  2. import java.util.*;
  3. import java.io.OutputStream;
  4. import java.io.IOException;
  5. import java.io.InputStream;
  6. import java.io.PrintWriter;
  7. import java.util.Arrays;
  8. import java.util.StringTokenizer;
  9. import java.io.IOException;
  10. import java.io.BufferedReader;
  11. import java.io.InputStreamReader;
  12. import java.io.InputStream;
  13. public class Main {
  14.     public static void main(String[] args) {
  15.         InputStream inputStream = System.in;
  16.         OutputStream outputStream = System.out;
  17.         InputReader in = new InputReader(inputStream);
  18.         PrintWriter out = new PrintWriter(outputStream);
  19.         int[]  nex=new int[500005]; //相当于next指针
  20.         int[] status=new int[500005]; //记录状态，0表示coming，1表示waiting，2表示eating
  21.         String s;
  22.         int n,x,y,tail; //tail记录队尾同学的编号，为0表示队伍为空
  23.         n=in.nextInt();
  24.         tail=0;
  25.         while(n!=0){
  26.             n--;
  27.             s=in.next();
  28.             if(s.equals("pd")){
  29.                 x=in.nextInt();
  30.                 status[x]=1;
  31.                 nex[tail]=x;
  32.                 tail=x;
  33.             }
  34.             if(s.equals("df")){
  35.                 x=nex[0];
  36.                 status[x]=2;
  37.                 nex[0]=nex[x];
  38.                 if(tail==x) //如果队伍里只剩一个人，此时要把队伍排空，要更改tail
  39.                     tail=nex[x];
  40.             }
  41.             if(s.equals("cd")){
  42.                 x=in.nextInt();
  43.                 y=in.nextInt();
  44.                 status[x]=1;
  45.                 nex[x]=nex[y];
  46.                 nex[y]=x;
  47.                 if(tail==y) //如果y是原本队伍的最后一个，此时x就变成队伍最后了，要更改tail
  48.                     tail=nex[tail];
  49.             }
  50.             if(s.equals("xw")){
  51.                 x=in.nextInt();
  52.                 if(status[x]==0)
  53.                     System.out.println("coming");
  54.                 if(status[x]==1)
  55.                     System.out.println("waiting");
  56.                 if(status[x]==2)
  57.                     System.out.println("eating");
  58.             }
  59.         }
  60.     }
  61.     //java的输入太慢，对于这道题而言需要加速
  62.     static class InputReader {
  63.         public BufferedReader reader;
  64.         public StringTokenizer tokenizer;
  66.         public InputReader(InputStream stream) {
  67.             reader = new BufferedReader(new InputStreamReader(stream), 32768);
  68.             tokenizer = null;
  69.         }
  70.         public String next() {
  71.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  72.                 try {
  73.                     tokenizer = new StringTokenizer(reader.readLine());
  74.                 } catch (IOException e) {
  75.                     throw new RuntimeException(e);
  76.                 }
  77.             }
  78.             return tokenizer.nextToken();
  79.         }
  81.         public int nextInt() {
  82.             return Integer.parseInt(next());
  83.         }
  84.     }
  85. }

F 组队难题

    本题难度也偏高。
    队伍一共有三种：一大佬一端茶一倒水/两大佬一端茶(倒水)/三大佬。
    为了最大化队伍的数量，优先组成第一种队伍，再考虑第二种队伍，最后剩下的大佬每三个人组成一个队伍。
    于是问题转化为，最多能同时组成多少对一个端茶一个倒水的双人组，并且每组的两个人都不冲突。
    我们可以借助二分图匹配的模型，考虑在任意一对个不冲突且一端茶一倒水的组合之间连一条边，然后求最大匹配。
    最后根据最大匹配的数量、多余的端茶(倒水)的人的数量、和多余大佬的数量算出答案。
    时间复杂度o(N^3)，空间复杂度o(N^2)。

  1. //C++
  2. #include<iostream>
  3. #include<stdio.h>
  4. using namespace std;
  6. char s[305][5]; //记录每个人的属性
  7. bool ok[305][305]; //记录两个人是否冲突的邻接矩阵
  8. int root[305]; 
  9. int n;
  10. bool life[305];
  12. bool solve(int x) //找增广路函数
  13. {
  14.     life[x]=1;
  15.     for(int i=1;i<=n;i++)
  16.     {
  17.         if(s[i][1]=='S' && ok[x][i]==0) //判断两人是否一个端茶一个倒水并且没冲突
  18.         {
  19.             if(life[i])
  20.                 continue;
  21.             else
  22.                 life[i]=1;
  23.             if(!root[i] || solve(root[i]))
  24.             {
  25.                 root[i]=x;
  26.                 return 1;
  27.             }
  28.         }
  29.     }
  30.     return 0;
  31. }
  33. int main()
  34. {
  35.     int m,u,v;
  36.     int numdl=0,numdc=0,numds=0,ans=0; //numdl是大佬数量，numdc是端茶同学数量，numds是倒水数量，ans是一个端茶一个倒水而且不冲突的双人组的最大数量
  37.     scanf("%d%d",&n,&m);
  38.     for(int i=1;i<=n;i++)
  39.         scanf("%s",s[i]);
  40.     for(int i=1;i<=m;i++) //根据输入得到邻接矩阵
  41.     {
  42.         scanf("%d%d",&u,&v);
  43.         ok[u][v]=1;
  44.         ok[v][u]=1;
  45.     }
  46.     for(int i=1;i<=n;i++) //统计每种选手的数量
  47.     {
  48.         if(s[i][1]=='C')
  49.             numdc++;
  50.         if(s[i][1]=='L')
  51.             numdl++;
  52.         if(s[i][1]=='S')
  53.             numds++;
  54.     }
  55.     for(int i=1;i<=n;i++) //二分图匹配
  56.     {
  57.         for(int j=1;j<=n;j++)
  58.             life[j]=0;
  59.         if(s[i][1]=='C' && solve(i))
  60.             ans++;
  61.     }
  62.     if(ans>=numdl) //计算答案
  63.         printf("%d\n",numdl);
  64.     else
  65.     {
  66.         if((numdl-ans)/2>=(numdc+numds-ans*2))
  67.             printf("%d\n",numdc+numds-ans+(numdl-ans-(numdc+numds-ans*2)*2)/3);
  68.         else
  69.             printf("%d\n",ans+(numdl-ans)/2);
  70.     }
  71.     return 0;
  72. }
  1. //Java
  2. import java.util.*;
  3. import java.io.*;
  4. public class Main {
  5.     static String[] s=new String[305]; //记录每个人的属性
  6.     static boolean[][] ok=new boolean[305][305]; //记录两个人是否冲突的邻接矩阵
  7.     static int[] root=new int[305]; 
  8.     static int n;
  9.     static boolean[] life=new boolean[305];
  10.     static boolean solve(int x){ //找增广路函数
  11.         life[x]=true;
  12.         for(int i=1;i<=n;i++){
  13.             if(s[i].equals("DS") && ok[x][i]==false){ //判断两人是否一个端茶一个倒水并且没冲突
  14.                 if(life[i])
  15.                     continue;
  16.                 else
  17.                     life[i]=true;
  18.                 if(root[i]==0 || solve(root[i])){
  19.                     root[i]=x;
  20.                     return true;
  21.                 }
  22.             }
  23.         }
  24.         return false;
  25.     }
  26.     public static void main(String[] args) {
  27.         Scanner cin = new Scanner(System.in);
  28.         int m,u,v;
  29.         int numdl=0,numdc=0,numds=0,ans=0; //numdl是大佬数量，numdc是端茶同学数量，numds是倒水数量，ans是一个端茶一个倒水而且不冲突的双人组的最大数量
  30.         n=cin.nextInt();
  31.         m=cin.nextInt();
  32.         for(int i=1;i<=n;i++)
  33.             s[i]=cin.next();
  34.         for(int i=1;i<=m;i++){ //根据输入得到邻接矩阵
  35.             u=cin.nextInt();
  36.             v=cin.nextInt();
  37.             ok[u][v]=true;
  38.             ok[v][u]=true;
  39.         }
  40.         for(int i=1;i<=n;i++){ //统计每种选手的数量
  41.             if(s[i].equals("DC"))
  42.                 numdc++;
  43.             if(s[i].equals("DL"))
  44.                 numdl++;
  45.             if(s[i].equals("DS"))
  46.                 numds++;
  47.         }
  48.         for(int i=1;i<=n;i++){ //二分图匹配
  49.             for(int j=1;j<=n;j++)
  50.                 life[j]=false;
  51.             if(s[i].equals("DC") && solve(i))
  52.                 ans++;
  53.         }
  54.         if(ans>=numdl) //计算答案
  55.             System.out.println(numdl);
  56.         else{
  57.             if((numdl-ans)/2>=(numdc+numds-ans*2))
  58.                 System.out.println(numdc+numds-ans+(numdl-ans-(numdc+numds-ans*2)*2)/3);
  59.             else
  60.                 System.out.println(ans+(numdl-ans)/2);
  61.         }
  62.     }
  63. }

G 早自习打卡

    这个题的第一个难点在于h:m格式的输入，解决方法有很多，在这里不展开说，标程提供了一种方法。第二个难点在于没有给数据行数的情况下如何判断输入结束，C/C++的同学可以使用EOF机制解决这个问题，1000题就用到了这个机制，同学们可以去FAQ中查看参考代码。
    题目实际上是要求我们把记录按照学号分类，同一个学号下的记录再按时间排序，检查每个人的记录1和纪录2、记录3和纪录4、记录5和记录6...是否有满足前一条记录在7:20之前(包括7:20)，后一条记录在7:40之后(包括7:40)的情况，如果有，那么答案加上这个人。
    我们可以把按照记录时间排序，然后处理每一条记录，考虑对应学号的上一条记录是奇数条还是偶数条，如果是奇数条，判断上一条的时间和这一条的时间是不是满足条件，满足则更新答案，同时更新当前学号记录条数的奇偶性和最后一条记录时间。因为学号有10位数字，开不了那么大的数组，但是学号种类最多只会等于记录条数，所以我们要对学号进行离散化，标程给出的是用map进行的方式。
    另一种做法是在排序的时候，优先考虑对学号进行排序，学号相同再考虑时间，这样可以保证学号相同的记录都连在一起，处理答案的时候判断一下即可。
    本题对排序的时间复杂度要求不超过记录条数*log(记录条数)。所以冒泡、选择等排序方法的性能是达不到要求的。标程给的是调用系统库的sort()函数。
    时间复杂度o(记录条数*log(记录条数))，空间复杂度o(记录条数)。

  1. //C++
  2. #include<iostream>
  3. #include<stdio.h>
  4. #include<map>
  5. #include<algorithm>
  6. using namespace std;
  8. struct Node
  9. {
  10.     int t; //时间，h:m把转化成h*60+m储存
  11.     long long s; //学号
  12.     bool friend operator <(Node x1,Node x2) //定义Node结构体的大小比较为时间小的在前
  13.     {
  14.         return x1.t<x2.t;
  15.     }
  16. }rec[100005]; //记录
  17. map <long long,int> mp; //储存每个学号的上一次记录时间，为0说明上一次记录是偶数次
  19. int main()
  20. {
  21.     int ans=0,hh,mm; //ans为符合条件的人数
  22.     int l=7*60+20,r=7*60+40; //l对应7:20，r对应7:40
  23.     int n=0;
  24.     while(~scanf("%d:%d",&hh,&mm))
  25.     {
  26.         rec[n].t=hh*60+mm;
  27.         scanf("%lld",&rec[n].s);
  28.         n++;
  29.     }
  30.     sort(rec,rec+n); //把记录排序
  31.     for(int i=0;i<n;i++)
  32.     {
  33.         if(mp[rec[i].s]) //如果不为0说明上次是奇数次
  34.         {
  35.             if(rec[i].t>=r && mp[rec[i].s]<=l) //判断是否满足条件
  36.                 ans++;
  37.             mp[rec[i].s]=0;
  38.         }
  39.         else
  40.             mp[rec[i].s]=rec[i].t;
  41.     }
  42.     printf("%d\n",ans);
  43.     return 0;
  44. }
  1. //Java
  2. import java.util.*;
  3. import java.io.*;
  4. public class Main {
  5.     static class Node implements Comparable<Node>{
  6.         public int t; //时间，h:m把转化成h*60+m储存
  7.         public long s; //学号
  8.         Node(){
  9.             t=0;
  10.             s=0;
  11.         }
  12.         public int compareTo(Node o){ //定义Node结构体的大小比较为优先考虑学号小的在前，学号相同情况下时间小的在前
  13.             if(s==o.s){
  14.                 if(t==o.t)
  15.                     return 0;
  16.                 else{
  17.                     if(t<o.t)
  18.                         return -1;
  19.                     else
  20.                         return 1;
  21.                 }
  22.             }
  23.             else{
  24.                 if(s<o.s)
  25.                     return -1;
  26.                 else
  27.                     return 1;
  28.             }
  29.         }
  30.     }
  31.     public static void main(String[] args) {
  32.         Scanner cin = new Scanner(System.in);
  33.         long[] s=new long[100005];
  34.         int[] h=new int[100005];
  35.         int[] m=new int[100005];
  36.         String c;
  37.         int n=0;
  38.         while(cin.hasNext()){
  39.             c=cin.next();
  40.             if(c.charAt(1)==':'){
  41.                 h[n]=(c.charAt(0)-'0');
  42.                 if(c.length()==4)
  43.                     m[n]=(c.charAt(2)-'0')*10+(c.charAt(3)-'0');
  44.                 else
  45.                     m[n]=(c.charAt(2)-'0');
  47.             }
  48.             else{
  49.                 h[n]=(c.charAt(0)-'0')*10+(c.charAt(1)-'0');
  50.                 if(c.length()==5)
  51.                     m[n]=(c.charAt(3)-'0')*10+(c.charAt(4)-'0');
  52.                 else
  53.                     m[n]=(c.charAt(3)-'0');
  54.             }
  55.             s[n]=cin.nextLong();
  56.             n++;
  57.         }
  58.         Node[] rec=new Node[n]; //记录
  59.         for(int i=0;i<n;i++){
  60.             rec[i]=new Node();
  61.             rec[i].t=h[i]*60+m[i];
  62.             rec[i].s=s[i];
  63.         }
  64.         Arrays.sort(rec); //把记录排序
  65.         int ans=0; //ans为符合条件的人数
  66.         int nextt; //上次记录时间
  67.         int l=7*60+20,r=7*60+40; //l对应7:20，r对应7:40
  68.         long nexts; //上次记录学号
  69.         nextt=0;
  70.         nexts=-1;
  71.         for(int i=0;i<n;i++){
  72.             if(nexts==rec[i].s && nextt!=0){ //说明上次是同一个人的奇数次记录
  73.                 if(nextt<=l && rec[i].t>=r) //判断是否满足条件
  74.                     ans++;
  75.                 nextt=0;
  76.             }
  77.             else{
  78.                 nextt=rec[i].t;
  79.                 nexts=rec[i].s;
  80.             }
  81.         }
  82.         System.out.println(ans);
  83.     }
  84. }

H 网络连接中断

    先向4.14惨案、4.15惨案中遇难的同学们表示哀悼。
    如果没有断网时间的限制，这道题其实就是一个深度优先搜索(dfs)或广度优先搜索(bfs)从u出发能不能到达v的问题。加上断网时间之后，我们只需要在考虑两个楼栋是否连接的时候，把当前时间和断网时间考虑进去。注意：和i楼栋有关的网络全部失效意味着，如果消息要从楼栋a到楼栋b，不仅当前时间+1要小于等于楼栋b的断网时间，还要小于楼栋a的断网时间。
    因为网是从某个时间之后开始断的，所以对于到达同一栋楼的方案，时间越早越好。所以推荐使用bfs。
    时间复杂度o(N+M)，空间复杂度o(N+M)。

  1. //C++
  2. #include<iostream>
  3. #include<stdio.h>
  4. #include<queue>
  5. using namespace std;
  7. int t[1005]; //断网时间
  8. int life[1005]; //到达该楼栋的时间，-1表示没到达
  9. bool ok[1005][1005]; //两个楼栋是否直接相连
  10. queue <int> q;
  12. int main()
  13. {
  14.     int n,m,u,v,x;
  15.     scanf("%d%d",&n,&m);
  16.     for(int i=1;i<=n;i++)
  17.     {
  18.         life[i]=-1; //初始状态都为没到达
  19.         scanf("%d",&t[i]); //得到断网时间
  20.     }
  21.     while(m--) //得到邻接矩阵
  22.     {
  23.         scanf("%d%d",&u,&v);
  24.         ok[u][v]=ok[v][u]=1;
  25.     }
  26.     scanf("%d%d",&u,&v); //这里开始，u表示起点，v表示终点
  27.     life[u]=0;
  28.     q.push(u);
  29.     while(q.size()) //bfs
  30.     {
  31.         x=q.front();
  32.         q.pop();
  33.         for(int i=1;i<=n;i++)
  34.         {
  35.             if(ok[x][i] && life[x]+1<=t[i] && life[x]+1<=t[x] && life[i]==-1) //判断x能不能到i，包括断网的情况也要考虑
  36.             {
  37.                 life[i]=life[x]+1;
  38.                 q.push(i);
  39.             }
  40.         }
  41.     }
  42.     if(life[v]==-1)
  43.         printf("GG\n");
  44.     else
  45.         printf("Nice!\n");
  46.     return 0;
  47. }
  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=new int[1005]; //断网时间
  8.         int[] life=new int[1005]; //到达该楼栋的时间，-1表示没到达
  9.         boolean[][] ok=new boolean[1005][1005]; //两个楼栋是否直接相连
  10.         int[] q=new int[1005]; //q是用数组实现的队列
  11.         int head=0,tail=0; //head是队列的头指针，tail是队列的尾指针
  12.         int n,m,u,v,x;
  13.         n=cin.nextInt();
  14.         m=cin.nextInt();
  15.         for(int i=1;i<=n;i++){
  16.             life[i]=-1; //初始状态都为没到达
  17.             t[i]=cin.nextInt(); //得到断网时间
  18.         }
  19.         while(m>0){ //得到邻接矩阵
  20.             m--;
  21.             u=cin.nextInt();
  22.             v=cin.nextInt();
  23.             ok[u][v]=ok[v][u]=true;
  24.         }
  25.         u=cin.nextInt();
  26.         v=cin.nextInt();//这里开始，u表示起点，v表示终点
  27.         life[u]=0;
  28.         q[tail]=u;
  29.         tail++;
  30.         while(tail>head){ //bfs
  31.             x=q[head];
  32.             head++;
  33.             for(int i=1;i<=n;i++){
  34.                 if(ok[x][i] && life[x]+1<=t[i] && life[x]+1<=t[x] && life[i]==-1){ //判断x能不能到i，包括断网的情况也要考虑
  35.                     life[i]=life[x]+1;
  36.                     q[tail]=i;
  37.                     tail++;
  38.                 }
  39.             }
  40.         }
  41.         if(life[v]==-1)
  42.             System.out.println("GG");
  43.         else
  44.             System.out.println("Nice!");
  45.     }
  46. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注