[关闭]
@CQUPTacm 2018-04-22T11:49:44.000000Z 字数 8336 阅读 918

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

题解


由于时间比较紧,所以本次题解比较简略、代码只提供了c++的而且没有注释。

A 太阳的力量

    计算一下会过热多少次,然后加上这么多次的休息时间即可。
    答案会爆int所以要用long long。
    抵达终点的瞬间如果过热了,那次休息时间不用算入总时间。
    时间复杂度o(T),空间复杂度o(1)。

代码

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. int main()
  5. {
  6. int t;
  7. long long l,e,r;
  8. scanf("%d",&t);
  9. while(t--)
  10. {
  11. scanf("%lld%lld%lld",&l,&e,&r);
  12. printf("%lld\n",l+((l-1)/e)*r);
  13. }
  14. return 0;
  15. }

B 茜女惊魂

    英文题,题意是N+1个人中速度前M快的会被劝退,速度相同的人中你是最后被劝退的。问你不被劝退的最高速度。
    把N个人的速度排序,你的速度最快可以和第M快的人相同。排序要求复杂度为nlogn级别以下。
    注意两种特殊情况:M>N的时候你肯定会被劝退,M=0的时候你可以跑到极速。
    时间复杂度o(T*N*log(N)),空间复杂度o(N)。
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. double v[10005];
  6. int main()
  7. {
  8. int t,n,m;
  9. scanf("%d",&t);
  10. while(t--)
  11. {
  12. scanf("%d%d",&n,&m);
  13. for(int i=0;i<n;i++)
  14. scanf("%lf",&v[i]);
  15. v[n]=2017211799;
  16. sort(v,v+n+1);
  17. if(m>n)
  18. printf("GG\n");
  19. else
  20. printf("%.2f\n",v[n-m]);
  21. }
  22. return 0;
  23. }

C 闪光弹攻击

    英文题,题意为N次攻击,你可以防御其中连续的不超过M次攻击,问剩下的伤害值的和最小是多少。
    求一个长度不超过M的区间,让这个区间内元素的和最大。用总和减去这个区间的和就是最后答案。因为元素都是正数,所以当M<N时,和最大的区间长度一定是M。我们可以枚举区间左端点l,那么区间右端点r是l+M-1。区间l到r的和可以转化为两个前缀和的差,即区间1到r的和减去区间1到l-1的和。
    标程给的是另一种方法:先算出前M个元素的和,然后每次加上新的一个元素,把最早的一个元素去掉,动态维护当前区间和与之前最大区间和的更大值。
    M>=N的时候,所有攻击都被抵御。
    时间复杂度o(T*N),空间复杂度o(N)。
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring>
  5. #include<queue>
  6. using namespace std;
  7. int num[100005];
  8. int main()
  9. {
  10. int t,n,m;
  11. long long ans,temp,maxx;
  12. scanf("%d",&t);
  13. while(t--)
  14. {
  15. scanf("%d%d",&n,&m);
  16. ans=0;
  17. for(int i=1;i<=n;i++)
  18. {
  19. scanf("%d",&num[i]);
  20. ans+=num[i];
  21. }
  22. if(m>=n)
  23. printf("0\n");
  24. else
  25. {
  26. temp=0;
  27. for(int i=1;i<=m;i++)
  28. temp+=num[i];
  29. maxx=temp;
  30. for(int i=m+1;i<=n;i++)
  31. {
  32. temp+=num[i];
  33. temp-=num[i-m];
  34. maxx=max(maxx,temp);
  35. }
  36. printf("%lld\n",ans-maxx);
  37. }
  38. }
  39. return 0;
  40. }

D 严格的唐天神

    这题难度偏高。我们考虑一部分用原有的金币支付,一部分用复制币支付,那么原有金币支付的那部分实际上是多重背包判可行性,而复制币支付的那部分是一个完全背包。完全背包的部分不需要多说,多重背包的部分需要二进制优化。
    注意要先跑两种背包,再枚举用原有金币的部分有多少。
    时间复杂度o(T*N*log(C)*M),空间复杂度o(M+N*log(C))。
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring>
  5. using namespace std;
  6. bool ok[10005];
  7. int ans[10005];
  8. int v[15],c[15],num[105];
  9. int main()
  10. {
  11. int t,n,m,minn,cnt,temp,now;
  12. scanf("%d",&t);
  13. while(t--)
  14. {
  15. scanf("%d%d",&n,&m);
  16. cnt=0;
  17. for(int i=1;i<=n;i++)
  18. {
  19. scanf("%d%d",&v[i],&c[i]);
  20. now=1;
  21. while(c[i])
  22. {
  23. if(c[i]>=now)
  24. {
  25. c[i]-=now;
  26. cnt++;
  27. num[cnt]=now*v[i];
  28. }
  29. else
  30. {
  31. cnt++;
  32. num[cnt]=c[i]*v[i];
  33. c[i]=0;
  34. }
  35. now*=2;
  36. }
  37. }
  38. for(int i=0;i<=m;i++)
  39. {
  40. ok[i]=0;
  41. ans[i]=10086;
  42. }
  43. ok[0]=1;
  44. ans[0]=0;
  45. minn=10086;
  46. for(int i=1;i<=cnt;i++)
  47. for(int j=m;j>=num[i];j--)
  48. ok[j]|=ok[j-num[i]];
  49. for(int i=1;i<=n;i++)
  50. for(int j=v[i];j<=m;j++)
  51. ans[j]=min(ans[j],ans[j-v[i]]+1);
  52. for(int i=0;i<=m;i++)
  53. {
  54. if(ok[i])
  55. minn=min(minn,ans[m-i]);
  56. }
  57. if(minn==10086)
  58. printf("-1\n");
  59. else
  60. printf("%d\n",minn);
  61. }
  62. return 0;
  63. }

E MZ语考试

    这题难度偏高。首先我们可以用单词建一棵字典树,树上的点可以通过加字母的方式走到它的子节点。我们用ok[i][0]为1表示当我们走到i节点的时候想赢就能赢,用ok[i][1]为1表示当我们走到i节点的时候想输就能输。那么,节点的情况分四种:想赢就赢想输就输,想赢能赢想输看对面,想输能输想赢看对面,输赢都看对面。我们能分析出:如果我的对手在i的所有子节点都不能靠自己赢,那么我在i能靠自己赢;如果我的对手在i的所有子节点都不能靠自己输,那么我在i能靠自己输。从没有子节点的点即字典树上各条链的结尾倒推,初始状态为没有子节点的点想输能输想赢看对面。
    如果从空串的情况开始,先手的想赢能赢想输能输,那么他可以先输K-1轮,把先手一直放在自己这,最后一轮取胜。如果先手的想赢能赢想输看对面,那么如果K是奇数,每轮都是先手赢对我有利,那么在我后手的时候我肯定不会让先手的输,反之对手也会在后手的时候故意输给我,所以最终每局都是先手胜利,所以K为奇数我赢反之对面赢。如果先手想输能输想赢看对面,那么对面只要一直让我输,保持我先手,我就输定了。如果先手的输赢都看对面,那么对面同样只要一直让我输,我就输定了。
    时间复杂度o(T*N),空间复杂度o(N)。
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring>
  5. using namespace std;
  6. struct Node
  7. {
  8. bool ok[2];
  9. int son[26];
  10. }p[200005];
  11. int cnt;
  12. char s[200005];
  13. void newnode()
  14. {
  15. cnt++;
  16. p[cnt].ok[0]=0;
  17. p[cnt].ok[1]=0;
  18. for(int i=0;i<26;i++)
  19. p[cnt].son[i]=0;
  20. }
  21. void add(int x,int i)
  22. {
  23. if(!s[i])
  24. return;
  25. s[i]-='a';
  26. if(!p[x].son[s[i]])
  27. {
  28. newnode();
  29. p[x].son[s[i]]=cnt;
  30. }
  31. add(p[x].son[s[i]],i+1);
  32. }
  33. void dfs(int x)
  34. {
  35. bool flag=0;
  36. for(int i=0;i<26;i++)
  37. {
  38. if(p[x].son[i])
  39. {
  40. flag=1;
  41. dfs(p[x].son[i]);
  42. if(!p[p[x].son[i]].ok[1])
  43. p[x].ok[1]=1;
  44. if(!p[p[x].son[i]].ok[0])
  45. p[x].ok[0]=1;
  46. }
  47. }
  48. if(!flag)
  49. p[x].ok[1]=1;
  50. }
  51. int main()
  52. {
  53. int t;
  54. int n,k;
  55. scanf("%d",&t);
  56. while(t--)
  57. {
  58. scanf("%d%d",&n,&k);
  59. cnt=-1;
  60. newnode();
  61. while(n--)
  62. {
  63. scanf("%s",s);
  64. add(0,0);
  65. }
  66. dfs(0);
  67. if((p[0].ok[0] && p[0].ok[1]) || (p[0].ok[0] && (k%2)))
  68. printf("Pass\n");
  69. else
  70. printf("Fail\n");
  71. }
  72. return 0;
  73. }

F 无限键制

    这题难度是最高的。如果没有王の键的设定,那么这道题实际上就是一个最小生成树。加上王の键的设定之后,实际上就变成了求包含指定边的最小生成树。我们考虑最小生成树加上指定边之后,会形成一个环,环上除了指定边之外的边,可以砍掉一条。为了让生成树最小,我们会砍掉环上最大的那条边。于是问题就变成了,在原本的生成树上,从点U到点V的路上最大的那条边是多少。这个可以用LCA解决。
    当指定边在原本的生成树上时,两点之间只有一条边,相当于砍掉和加上同一条边,不影响答案。
    把K次询问的答案加起来就是最后的答案。输出会爆int,要用long long。
    时间复杂度o(T*(M*log(M)+K*log(N))),空间复杂度o(N*log(N)+M)。
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<vector>
  5. using namespace std;
  6. struct Edge
  7. {
  8. int u,v,e;
  9. bool friend operator <(Edge x1,Edge x2)
  10. {
  11. return x1.e<x2.e;
  12. }
  13. }edges[100005];
  14. struct E
  15. {
  16. int to,e;
  17. }temp;
  18. int u[100005],v[100005],e[100005];
  19. int root[10005];
  20. int f[10005],pre[10005][15],maxx[10005][15];
  21. vector <E> vec[10005];
  22. int findr(int x)
  23. {
  24. if(root[x]==x)
  25. return x;
  26. else
  27. return root[x]=findr(root[x]);
  28. }
  29. void dfs(int x,int fa,int nowe)
  30. {
  31. f[x]=f[fa]+1;
  32. pre[x][0]=fa;
  33. maxx[x][0]=nowe;
  34. for(int i=1;i<15;i++)
  35. {
  36. pre[x][i]=pre[pre[x][i-1]][i-1];
  37. maxx[x][i]=max(maxx[x][i-1],maxx[pre[x][i-1]][i-1]);
  38. }
  39. for(int i=0;i<vec[x].size();i++)
  40. {
  41. if(vec[x][i].to!=fa)
  42. dfs(vec[x][i].to,x,vec[x][i].e);
  43. }
  44. }
  45. int lca(int x,int y)
  46. {
  47. while(f[x]>f[y])
  48. {
  49. for(int i=14;i>=0;i--)
  50. {
  51. if(f[pre[x][i]]>f[y])
  52. x=pre[x][i];
  53. }
  54. x=pre[x][0];
  55. }
  56. while(f[y]>f[x])
  57. {
  58. for(int i=14;i>=0;i--)
  59. {
  60. if(f[pre[y][i]]>f[x])
  61. y=pre[y][i];
  62. }
  63. y=pre[y][0];
  64. }
  65. while(x!=y)
  66. {
  67. for(int i=14;i>=0;i--)
  68. {
  69. if(pre[y][i]!=pre[x][i])
  70. {
  71. y=pre[y][i];
  72. x=pre[x][i];
  73. }
  74. }
  75. x=pre[x][0];
  76. y=pre[y][0];
  77. }
  78. return x;
  79. }
  80. int ask(int x,int y)
  81. {
  82. int now=0;
  83. while(f[y]>f[x])
  84. {
  85. for(int i=14;i>=0;i--)
  86. {
  87. if(f[pre[y][i]]>f[x])
  88. {
  89. now=max(now,maxx[y][i]);
  90. y=pre[y][i];
  91. }
  92. }
  93. now=max(now,maxx[y][0]);
  94. y=pre[y][0];
  95. }
  96. return now;
  97. }
  98. int main()
  99. {
  100. int t,n,m,k,x,y,now;
  101. long long ans,sum;
  102. scanf("%d",&t);
  103. while(t--)
  104. {
  105. scanf("%d%d%d",&m,&n,&k);
  106. for(int i=1;i<=n;i++)
  107. {
  108. vec[i].clear();
  109. root[i]=i;
  110. }
  111. for(int i=1;i<=m;i++)
  112. {
  113. scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].e);
  114. u[i]=edges[i].u;
  115. v[i]=edges[i].v;
  116. e[i]=edges[i].e;
  117. }
  118. sort(edges+1,edges+1+m);
  119. ans=0;
  120. sum=0;
  121. for(int i=1;i<=m;i++)
  122. {
  123. x=findr(edges[i].u);
  124. y=findr(edges[i].v);
  125. if(x!=y)
  126. {
  127. sum+=edges[i].e;
  128. root[x]=y;
  129. temp.e=edges[i].e;
  130. temp.to=edges[i].u;
  131. vec[edges[i].v].push_back(temp);
  132. temp.to=edges[i].v;
  133. vec[edges[i].u].push_back(temp);
  134. }
  135. }
  136. dfs(1,0,0);
  137. while(k--)
  138. {
  139. scanf("%d",&now);
  140. ans+=e[now];
  141. x=u[now];
  142. y=v[now];
  143. now=lca(x,y);
  144. ans+=sum-max(ask(now,x),ask(now,y));
  145. }
  146. printf("%lld\n",ans);
  147. }
  148. return 0;
  149. }

G 地雷迷阵

    无法过桥的情况只有一种:某些地雷连成一片,并且分别和桥的宽度方向的两个边界有接触。所以我们只需要枚举任意两个地雷,看他们是否有接触,如果有就连一条边。同时枚举地雷考虑和左右边界有没有接触。最后跑个搜索染色看看左右边界是否连在一起即可。
    时间复杂度o(T*N*N),空间复杂度o(N*N)。
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring>
  5. using namespace std;
  6. double x[105],y[105],r[105];
  7. bool maps[105][105];
  8. bool vis[105];
  9. int n;
  10. bool ok(int a,int b)
  11. {
  12. return (r[a]+r[b])*(r[a]+r[b])>=(x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);
  13. }
  14. void dfs(int x)
  15. {
  16. vis[x]=1;
  17. for(int i=0;i<=n+1;i++)
  18. {
  19. if(maps[x][i] && !vis[i])
  20. {
  21. dfs(i);
  22. }
  23. }
  24. }
  25. int main()
  26. {
  27. int t;
  28. double l,w;
  29. scanf("%d",&t);
  30. while(t--)
  31. {
  32. scanf("%lf%lf%d",&w,&l,&n);
  33. for(int i=1;i<=n;i++)
  34. scanf("%lf%lf%lf",&x[i],&y[i],&r[i]);
  35. memset(maps,0,sizeof(maps));
  36. memset(vis,0,sizeof(vis));
  37. for(int i=1;i<n;i++)
  38. for(int j=i+1;j<=n;j++)
  39. {
  40. if(ok(i,j))
  41. maps[i][j]=maps[j][i]=1;
  42. }
  43. for(int i=1;i<=n;i++)
  44. {
  45. if(x[i]<=r[i])
  46. maps[0][i]=maps[i][0]=1;
  47. if(x[i]+r[i]>=w)
  48. maps[n+1][i]=maps[i][n+1]=1;
  49. }
  50. dfs(0);
  51. if(vis[n+1])
  52. printf("GG\n");
  53. else
  54. printf("Nice\n");
  55. }
  56. return 0;
  57. }

H 夺命果奶

    枚举普通果苣的数目i,剩下的M-i种都是黑暗果苣,保证M-i<K的情况下,答案实际上是C(N1-N2,i)*C(N2,M-i)。把每种情况对应的答案加起来就是最后的答案。
    求组合数可以用C(N,M)=C(N-1,M-1)+C(N-1,M)的公式,题解给的是另一种办法:C(N,M)=N!/(M!*(N-M)!)=(N*(N-1)*...*(N-M+1))/(1*2*...M)。不过这样算会爆long long,所以我们要用N/1*(N-1)/2*(N-2)/3...*(N-M+1)/M。
    当N<M的时候C(N,M)=0。
    时间复杂度o(T*K*K),空间复杂度o(1)。
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. long long com(int n,int m)
  6. {
  7. long long now=1;
  8. if(m>n)
  9. return 0;
  10. for(int i=1;i<=m;i++)
  11. {
  12. now=now*n;
  13. n--;
  14. now=now/i;
  15. }
  16. return now;
  17. }
  18. int main()
  19. {
  20. int t,n1,n2,m,k;
  21. long long ans;
  22. scanf("%d",&t);
  23. while(t--)
  24. {
  25. scanf("%d%d%d%d",&n1,&n2,&m,&k);
  26. ans=0;
  27. for(int i=0;i<=m;i++)
  28. {
  29. if(m-i<k)
  30. ans+=com(n1-n2,i)*com(n2,m-i);
  31. }
  32. printf("%lld\n",ans);
  33. }
  34. return 0;
  35. }

I 锦鱼突刺

    一段连续的“O”可以毫无代价的走来走去,以“X”分隔开的两段“O”只能以跳跃的方式互相到达。先处理出每段连续的“O”的左端点和右端点,然后枚举两段“O”判断能不能跳到,能跳到就连一条无向边,最后求从含1的那段“O”到含N的那段“O”的最小距离,可以用bfs 解决。
    时间复杂度o(T*N*N),空间复杂度o(N*N)。
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring>
  5. #include<queue>
  6. using namespace std;
  7. char s[1005];
  8. int ans[1005];
  9. bool ok[1005][1005];
  10. int l[1005],r[1005];
  11. queue <int> q;
  12. int main()
  13. {
  14. int t,n,m,temp,cnt;
  15. bool flag;
  16. scanf("%d",&t);
  17. while(t--)
  18. {
  19. scanf("%d%d",&n,&m);
  20. scanf("%s",s+1);
  21. flag=0;
  22. cnt=0;
  23. for(int i=1;i<=n;i++)
  24. {
  25. if(s[i]=='O')
  26. {
  27. if(!flag)
  28. {
  29. cnt++;
  30. l[cnt]=i;
  31. flag=1;
  32. }
  33. }
  34. else
  35. {
  36. if(flag)
  37. {
  38. r[cnt]=i-1;
  39. flag=0;
  40. }
  41. }
  42. }
  43. if(flag)
  44. r[cnt]=n;
  45. for(int i=1;i<=cnt;i++)
  46. {
  47. ans[i]=-1;
  48. for(int j=1;j<=cnt;j++)
  49. ok[i][j]=0;
  50. }
  51. for(int i=1;i<cnt;i++)
  52. for(int j=i+1;j<=cnt;j++)
  53. {
  54. if(l[i]+m+1<=r[j] && r[i]+m+1>=l[j])
  55. ok[i][j]=ok[j][i]=1;
  56. }
  57. ans[1]=0;
  58. q.push(1);
  59. while(!q.empty())
  60. {
  61. temp=q.front();
  62. q.pop();
  63. for(int i=1;i<=cnt;i++)
  64. {
  65. if(ans[i]==-1 && ok[temp][i])
  66. {
  67. ans[i]=ans[temp]+1;
  68. q.push(i);
  69. }
  70. }
  71. }
  72. printf("%d\n",ans[cnt]);
  73. }
  74. return 0;
  75. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注