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

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

题解


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

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;
  5. int dic[4][2]={0,1,1,0,0,-1,-1,0}; //四个方向的位移影响
  6. char s[6];
  7. int main()
  8. {
  9. long long nx=0,ny=0; //当前位置
  10. int d=0,x; //d是当前方向的编号
  11. while(scanf("%s",s))
  12. {
  13. if(s[0]=='F')
  14. break;
  15. if(s[0]=='W')
  16. {
  17. scanf("%d",&x);
  18. nx+=dic[d][0]*x;
  19. ny+=dic[d][1]*x;
  20. }
  21. if(s[0]=='S')
  22. {
  23. d=(d+2)%4;
  24. scanf("%d",&x);
  25. nx+=dic[d][0]*x;
  26. ny+=dic[d][1]*x;
  27. }
  28. if(s[0]=='D')
  29. d=(d+1)%4;
  30. if(s[0]=='A')
  31. d=(d-1+4)%4;
  32. }
  33. printf("%lld %lld\n",nx,ny);
  34. return 0;
  35. }
  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;
  5. bool life[1005]; //life为0代表有嫌疑
  6. int main()
  7. {
  8. int l,m,x,y,ans,flag=0; //flag是有嫌疑的段数,ans是有嫌疑的段左边的位置
  9. scanf("%d%d",&l,&m);
  10. while(m--)
  11. {
  12. scanf("%d%d",&x,&y);
  13. for(int i=x;i<y;i++)
  14. life[i]=1;
  15. }
  16. for(int i=0;i<l;i++)
  17. {
  18. if(!life[i])
  19. {
  20. ans=i;
  21. flag++;
  22. }
  23. }
  24. if(flag>1)
  25. printf("No response!\n");
  26. else
  27. printf("%d\n",ans);
  28. return 0;
  29. }
  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>
  4. using namespace std;
  5. int n,m;
  6. int m10; //m10=10^m
  7. long long dp[15][10005]; //dp[i][j]表示只考虑前i位组成的满足每连续M位的和都是质数,并且最后M位组成的数字是j的数字串的个数
  8. bool prime[105]; //prime[i]=1代表i是质数
  9. int sum(int x) //求x各个位置上的数的和
  10. {
  11. int now=0;
  12. for(int i=1;i<=m;i++)
  13. {
  14. now+=x%10;
  15. x=x/10;
  16. }
  17. return now;
  18. }
  19. long long solve()
  20. {
  21. long long ans=0;
  22. if(n<m)
  23. return 0;
  24. for(int i=0;i<=n;i++)
  25. for(int j=0;j<m10;j++)
  26. dp[i][j]=0;
  27. dp[0][0]=1;
  28. for(int i=1;i<=n;i++) //考虑前i个数字
  29. {
  30. for(int j=0;j<m10;j++) //考虑前i-1位组成的数字串的末尾M位数字
  31. {
  32. for(int k=0;k<10;k++) //考虑当前位的数字
  33. dp[i][(j*10)%m10+k]+=dp[i-1][j];
  34. }
  35. if(i>=m) //当i大于等于M时,清空不符合要求的数字串
  36. {
  37. for(int j=0;j<m10;j++)
  38. {
  39. if(!prime[sum(j)])
  40. dp[i][j]=0;
  41. }
  42. }
  43. }
  44. for(int i=0;i<m10;i++) //计算答案
  45. ans+=dp[n][i];
  46. return ans;
  47. }
  48. int main()
  49. {
  50. for(int i=2;i<=36;i++) //最多4个9相加只有36,判断36以内的质数有哪些
  51. {
  52. bool flag=0;
  53. for(int j=2;j<i;j++)
  54. {
  55. if(i%j==0)
  56. {
  57. flag=1;
  58. }
  59. }
  60. if(flag==0)
  61. prime[i]=1;
  62. }
  63. scanf("%d%d",&n,&m);
  64. m10=1;
  65. for(int i=1;i<=m;i++)
  66. m10*=10; //求10的m次方
  67. printf("%lld\n",solve());
  68. return 0;
  69. }
  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;
  5. bool mat[105][105]; //矩阵
  6. bool gg(int x,int y) //判断第x行的前y个数字是不是都是0
  7. {
  8. for(int i=1;i<=y;i++)
  9. {
  10. if(mat[x][i])
  11. return 0;
  12. }
  13. return 1;
  14. }
  15. int main()
  16. {
  17. int n,m,x,t;
  18. bool flag=0,temp;
  19. scanf("%d%d",&n,&m);
  20. for(int i=1;i<=m;i++) //根据输入生成系数矩阵
  21. {
  22. scanf("%d",&x);
  23. while(x--)
  24. {
  25. scanf("%d",&t);
  26. mat[t][i]=1;
  27. }
  28. }
  29. for(int i=1;i<=n;i++) //变系数矩阵为增广矩阵
  30. mat[i][m+1]=1;
  31. for(int i=1;i<=m;i++) //高斯消元
  32. {
  33. for(int j=1;j<=n;j++)
  34. {
  35. if(mat[j][i] && gg(j,i-1))
  36. {
  37. for(int k=1;k<=n;k++)
  38. {
  39. if(k!=j && mat[k][i])
  40. {
  41. for(int g=i;g<=m+1;g++)
  42. mat[k][g]^=mat[j][g];
  43. }
  44. }
  45. break;
  46. }
  47. }
  48. }
  49. for(int i=1;i<=n;i++) //判断系数矩阵和增广矩阵的秩是否相同
  50. {
  51. temp=0;
  52. for(int j=1;j<=m;j++)
  53. {
  54. if(mat[i][j])
  55. {
  56. temp=1;
  57. break;
  58. }
  59. }
  60. if(!temp && mat[i][m+1])
  61. {
  62. flag=1;
  63. break;
  64. }
  65. }
  66. if(!flag)
  67. printf("YES\n");
  68. else
  69. printf("NO\n");
  70. return 0;
  71. }
  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>
  4. using namespace std;
  5. int nex[500005]; //相当于next指针
  6. int status[500005]; //记录状态,0表示coming,1表示waiting,2表示eating
  7. char s[6];
  8. int main()
  9. {
  10. int n,x,y,tail; //tail记录队尾同学的编号,为0表示队伍为空
  11. scanf("%d",&n);
  12. tail=0;
  13. while(n--)
  14. {
  15. scanf("%s",s);
  16. if(s[0]=='p')
  17. {
  18. scanf("%d",&x);
  19. status[x]=1;
  20. nex[tail]=x;
  21. tail=x;
  22. }
  23. if(s[0]=='d')
  24. {
  25. x=nex[0];
  26. status[x]=2;
  27. nex[0]=nex[x];
  28. if(tail==x) //如果队伍里只剩一个人,此时要把队伍排空,要更改tail
  29. tail=nex[x];
  30. }
  31. if(s[0]=='c')
  32. {
  33. scanf("%d %d",&x,&y);
  34. status[x]=1;
  35. nex[x]=nex[y];
  36. nex[y]=x;
  37. if(tail==y) //如果y是原本队伍的最后一个,此时x就变成队伍最后了,要更改tail
  38. tail=nex[tail];
  39. }
  40. if(s[0]=='x')
  41. {
  42. scanf("%d",&x);
  43. if(status[x]==0)
  44. printf("coming\n");
  45. if(status[x]==1)
  46. printf("waiting\n");
  47. if(status[x]==2)
  48. printf("eating\n");
  49. }
  50. }
  51. return 0;
  52. }
  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;
  65. public InputReader(InputStream stream) {
  66. reader = new BufferedReader(new InputStreamReader(stream), 32768);
  67. tokenizer = null;
  68. }
  69. public String next() {
  70. while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  71. try {
  72. tokenizer = new StringTokenizer(reader.readLine());
  73. } catch (IOException e) {
  74. throw new RuntimeException(e);
  75. }
  76. }
  77. return tokenizer.nextToken();
  78. }
  79. public int nextInt() {
  80. return Integer.parseInt(next());
  81. }
  82. }
  83. }

F 组队难题

    本题难度也偏高。
    队伍一共有三种:一大佬一端茶一倒水/两大佬一端茶(倒水)/三大佬。
    为了最大化队伍的数量,优先组成第一种队伍,再考虑第二种队伍,最后剩下的大佬每三个人组成一个队伍。
    于是问题转化为,最多能同时组成多少对一个端茶一个倒水的双人组,并且每组的两个人都不冲突。
    我们可以借助二分图匹配的模型,考虑在任意一对个不冲突且一端茶一倒水的组合之间连一条边,然后求最大匹配。
    最后根据最大匹配的数量、多余的端茶(倒水)的人的数量、和多余大佬的数量算出答案。
    时间复杂度o(N^3),空间复杂度o(N^2)。
  1. //C++
  2. #include<iostream>
  3. #include<stdio.h>
  4. using namespace std;
  5. char s[305][5]; //记录每个人的属性
  6. bool ok[305][305]; //记录两个人是否冲突的邻接矩阵
  7. int root[305];
  8. int n;
  9. bool life[305];
  10. bool solve(int x) //找增广路函数
  11. {
  12. life[x]=1;
  13. for(int i=1;i<=n;i++)
  14. {
  15. if(s[i][1]=='S' && ok[x][i]==0) //判断两人是否一个端茶一个倒水并且没冲突
  16. {
  17. if(life[i])
  18. continue;
  19. else
  20. life[i]=1;
  21. if(!root[i] || solve(root[i]))
  22. {
  23. root[i]=x;
  24. return 1;
  25. }
  26. }
  27. }
  28. return 0;
  29. }
  30. int main()
  31. {
  32. int m,u,v;
  33. int numdl=0,numdc=0,numds=0,ans=0; //numdl是大佬数量,numdc是端茶同学数量,numds是倒水数量,ans是一个端茶一个倒水而且不冲突的双人组的最大数量
  34. scanf("%d%d",&n,&m);
  35. for(int i=1;i<=n;i++)
  36. scanf("%s",s[i]);
  37. for(int i=1;i<=m;i++) //根据输入得到邻接矩阵
  38. {
  39. scanf("%d%d",&u,&v);
  40. ok[u][v]=1;
  41. ok[v][u]=1;
  42. }
  43. for(int i=1;i<=n;i++) //统计每种选手的数量
  44. {
  45. if(s[i][1]=='C')
  46. numdc++;
  47. if(s[i][1]=='L')
  48. numdl++;
  49. if(s[i][1]=='S')
  50. numds++;
  51. }
  52. for(int i=1;i<=n;i++) //二分图匹配
  53. {
  54. for(int j=1;j<=n;j++)
  55. life[j]=0;
  56. if(s[i][1]=='C' && solve(i))
  57. ans++;
  58. }
  59. if(ans>=numdl) //计算答案
  60. printf("%d\n",numdl);
  61. else
  62. {
  63. if((numdl-ans)/2>=(numdc+numds-ans*2))
  64. printf("%d\n",numdc+numds-ans+(numdl-ans-(numdc+numds-ans*2)*2)/3);
  65. else
  66. printf("%d\n",ans+(numdl-ans)/2);
  67. }
  68. return 0;
  69. }
  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;
  7. struct Node
  8. {
  9. int t; //时间,h:m把转化成h*60+m储存
  10. long long s; //学号
  11. bool friend operator <(Node x1,Node x2) //定义Node结构体的大小比较为时间小的在前
  12. {
  13. return x1.t<x2.t;
  14. }
  15. }rec[100005]; //记录
  16. map <long long,int> mp; //储存每个学号的上一次记录时间,为0说明上一次记录是偶数次
  17. int main()
  18. {
  19. int ans=0,hh,mm; //ans为符合条件的人数
  20. int l=7*60+20,r=7*60+40; //l对应7:20,r对应7:40
  21. int n=0;
  22. while(~scanf("%d:%d",&hh,&mm))
  23. {
  24. rec[n].t=hh*60+mm;
  25. scanf("%lld",&rec[n].s);
  26. n++;
  27. }
  28. sort(rec,rec+n); //把记录排序
  29. for(int i=0;i<n;i++)
  30. {
  31. if(mp[rec[i].s]) //如果不为0说明上次是奇数次
  32. {
  33. if(rec[i].t>=r && mp[rec[i].s]<=l) //判断是否满足条件
  34. ans++;
  35. mp[rec[i].s]=0;
  36. }
  37. else
  38. mp[rec[i].s]=rec[i].t;
  39. }
  40. printf("%d\n",ans);
  41. return 0;
  42. }
  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');
  46. }
  47. else{
  48. h[n]=(c.charAt(0)-'0')*10+(c.charAt(1)-'0');
  49. if(c.length()==5)
  50. m[n]=(c.charAt(3)-'0')*10+(c.charAt(4)-'0');
  51. else
  52. m[n]=(c.charAt(3)-'0');
  53. }
  54. s[n]=cin.nextLong();
  55. n++;
  56. }
  57. Node[] rec=new Node[n]; //记录
  58. for(int i=0;i<n;i++){
  59. rec[i]=new Node();
  60. rec[i].t=h[i]*60+m[i];
  61. rec[i].s=s[i];
  62. }
  63. Arrays.sort(rec); //把记录排序
  64. int ans=0; //ans为符合条件的人数
  65. int nextt; //上次记录时间
  66. int l=7*60+20,r=7*60+40; //l对应7:20,r对应7:40
  67. long nexts; //上次记录学号
  68. nextt=0;
  69. nexts=-1;
  70. for(int i=0;i<n;i++){
  71. if(nexts==rec[i].s && nextt!=0){ //说明上次是同一个人的奇数次记录
  72. if(nextt<=l && rec[i].t>=r) //判断是否满足条件
  73. ans++;
  74. nextt=0;
  75. }
  76. else{
  77. nextt=rec[i].t;
  78. nexts=rec[i].s;
  79. }
  80. }
  81. System.out.println(ans);
  82. }
  83. }

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