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

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

题解

由于时间比较紧，所以本次题解比较简略、代码只提供了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;
  6. double v[10005];
  8. int main()
  9. {
  10.     int t,n,m;
  11.     scanf("%d",&t);
  12.     while(t--)
  13.     {
  14.         scanf("%d%d",&n,&m);
  15.         for(int i=0;i<n;i++)
  16.             scanf("%lf",&v[i]);
  17.         v[n]=2017211799;
  18.         sort(v,v+n+1);
  19.         if(m>n)
  20.             printf("GG\n");
  21.         else
  22.             printf("%.2f\n",v[n-m]);
  23.     }
  24.     return 0;
  25. }

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;
  8. int num[100005];
  10. int main()
  11. {
  12.     int t,n,m;
  13.     long long ans,temp,maxx;
  14.     scanf("%d",&t);
  15.     while(t--)
  16.     {
  17.         scanf("%d%d",&n,&m);
  18.         ans=0;
  19.         for(int i=1;i<=n;i++)
  20.         {
  21.             scanf("%d",&num[i]);
  22.             ans+=num[i];
  23.         }
  24.         if(m>=n)
  25.             printf("0\n");
  26.         else
  27.         {
  28.             temp=0;
  29.             for(int i=1;i<=m;i++)
  30.                 temp+=num[i];
  31.             maxx=temp;
  32.             for(int i=m+1;i<=n;i++)
  33.             {
  34.                 temp+=num[i];
  35.                 temp-=num[i-m];
  36.                 maxx=max(maxx,temp);
  37.             }
  38.             printf("%lld\n",ans-maxx);
  39.         }
  40.     }
  41.     return 0;
  42. }

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;
  7. bool ok[10005];
  8. int ans[10005];
  9. int v[15],c[15],num[105];
  11. int main()
  12. {
  13.     int t,n,m,minn,cnt,temp,now;
  14.     scanf("%d",&t);
  15.     while(t--)
  16.     {
  17.         scanf("%d%d",&n,&m);
  18.         cnt=0;
  19.         for(int i=1;i<=n;i++)
  20.         {
  21.             scanf("%d%d",&v[i],&c[i]);
  22.             now=1;
  23.             while(c[i])
  24.             {
  25.                 if(c[i]>=now)
  26.                 {
  27.                     c[i]-=now;
  28.                     cnt++;
  29.                     num[cnt]=now*v[i];
  30.                 }
  31.                 else
  32.                 {
  33.                     cnt++;
  34.                     num[cnt]=c[i]*v[i];
  35.                     c[i]=0;
  36.                 }
  37.                 now*=2;
  38.             }
  39.         }
  40.         for(int i=0;i<=m;i++)
  41.         {
  42.             ok[i]=0;
  43.             ans[i]=10086;
  44.         }
  45.         ok[0]=1;
  46.         ans[0]=0;
  47.         minn=10086;
  48.         for(int i=1;i<=cnt;i++)
  49.             for(int j=m;j>=num[i];j--)
  50.                 ok[j]|=ok[j-num[i]];
  51.         for(int i=1;i<=n;i++)
  52.             for(int j=v[i];j<=m;j++)
  53.                 ans[j]=min(ans[j],ans[j-v[i]]+1);
  54.         for(int i=0;i<=m;i++)
  55.         {
  56.             if(ok[i])
  57.                 minn=min(minn,ans[m-i]);
  58.         }
  59.         if(minn==10086)
  60.             printf("-1\n");
  61.         else
  62.             printf("%d\n",minn);
  63.     }
  64.     return 0;
  65. }

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;
  7. struct Node
  8. {
  9.     bool ok[2];
  10.     int son[26];
  11. }p[200005];
  12. int cnt;
  13. char s[200005];
  15. void newnode()
  16. {
  17.     cnt++;
  18.     p[cnt].ok[0]=0;
  19.     p[cnt].ok[1]=0;
  20.     for(int i=0;i<26;i++)
  21.         p[cnt].son[i]=0;
  22. }
  23. void add(int x,int i)
  24. {
  25.     if(!s[i])
  26.         return;
  27.     s[i]-='a';
  28.     if(!p[x].son[s[i]])
  29.     {
  30.         newnode();
  31.         p[x].son[s[i]]=cnt;
  32.     }
  33.     add(p[x].son[s[i]],i+1);
  34. }
  35. void dfs(int x)
  36. {
  37.     bool flag=0;
  38.     for(int i=0;i<26;i++)
  39.     {
  40.         if(p[x].son[i])
  41.         {
  42.             flag=1;
  43.             dfs(p[x].son[i]);
  44.             if(!p[p[x].son[i]].ok[1])
  45.                 p[x].ok[1]=1;
  46.             if(!p[p[x].son[i]].ok[0])
  47.                 p[x].ok[0]=1;
  48.         }
  49.     }
  50.     if(!flag)
  51.         p[x].ok[1]=1;
  52. }
  54. int main()
  55. {
  56.     int t;
  57.     int n,k;
  58.     scanf("%d",&t);
  59.     while(t--)
  60.     {
  61.         scanf("%d%d",&n,&k);
  62.         cnt=-1;
  63.         newnode();
  64.         while(n--)
  65.         {
  66.             scanf("%s",s);
  67.             add(0,0);
  68.         }
  69.         dfs(0);
  70.         if((p[0].ok[0] && p[0].ok[1]) || (p[0].ok[0] && (k%2)))
  71.             printf("Pass\n");
  72.         else
  73.             printf("Fail\n");
  74.     }
  75.     return 0;
  76. }

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;
  7. struct Edge
  8. {
  9.     int u,v,e;
  10.     bool friend operator <(Edge x1,Edge x2)
  11.     {
  12.         return x1.e<x2.e;
  13.     }
  14. }edges[100005];
  15. struct E
  16. {
  17.     int to,e;
  18. }temp;
  19. int u[100005],v[100005],e[100005];
  20. int root[10005];
  21. int f[10005],pre[10005][15],maxx[10005][15];
  22. vector <E> vec[10005];
  24. int findr(int x)
  25. {
  26.     if(root[x]==x)
  27.         return x;
  28.     else
  29.         return root[x]=findr(root[x]);
  30. }
  31. void  dfs(int x,int fa,int nowe)
  32. {
  33.     f[x]=f[fa]+1;
  34.     pre[x][0]=fa;
  35.     maxx[x][0]=nowe;
  36.     for(int i=1;i<15;i++)
  37.     {
  38.         pre[x][i]=pre[pre[x][i-1]][i-1];
  39.         maxx[x][i]=max(maxx[x][i-1],maxx[pre[x][i-1]][i-1]);
  40.     }
  41.     for(int i=0;i<vec[x].size();i++)
  42.     {
  43.         if(vec[x][i].to!=fa)
  44.             dfs(vec[x][i].to,x,vec[x][i].e);
  45.     }
  46. }
  47. int lca(int x,int y)
  48. {
  49.     while(f[x]>f[y])
  50.     {
  51.         for(int i=14;i>=0;i--)
  52.         {
  53.             if(f[pre[x][i]]>f[y])
  54.                 x=pre[x][i];
  55.         }
  56.         x=pre[x][0];
  57.     }
  58.     while(f[y]>f[x])
  59.     {
  60.         for(int i=14;i>=0;i--)
  61.         {
  62.             if(f[pre[y][i]]>f[x])
  63.                 y=pre[y][i];
  64.         }
  65.         y=pre[y][0];
  66.     }
  67.     while(x!=y)
  68.     {
  69.         for(int i=14;i>=0;i--)
  70.         {
  71.             if(pre[y][i]!=pre[x][i])
  72.             {
  73.                 y=pre[y][i];
  74.                 x=pre[x][i];
  75.             }
  76.         }
  77.         x=pre[x][0];
  78.         y=pre[y][0];
  79.     }
  80.     return x;
  81. }
  82. int ask(int x,int y)
  83. {
  84.     int now=0;
  85.     while(f[y]>f[x])
  86.     {
  87.         for(int i=14;i>=0;i--)
  88.         {
  89.             if(f[pre[y][i]]>f[x])
  90.             {
  91.                 now=max(now,maxx[y][i]);
  92.                 y=pre[y][i];
  93.             }
  94.         }
  95.         now=max(now,maxx[y][0]);
  96.         y=pre[y][0];
  97.     }
  98.     return now;
  99. }
  101. int main()
  102. {
  103.     int t,n,m,k,x,y,now;
  104.     long long ans,sum;
  105.     scanf("%d",&t);
  106.     while(t--)
  107.     {
  108.         scanf("%d%d%d",&m,&n,&k);
  109.         for(int i=1;i<=n;i++)
  110.         {
  111.             vec[i].clear();
  112.             root[i]=i;
  113.         }
  114.         for(int i=1;i<=m;i++)
  115.         {
  116.             scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].e);
  117.             u[i]=edges[i].u;
  118.             v[i]=edges[i].v;
  119.             e[i]=edges[i].e;
  120.         }
  121.         sort(edges+1,edges+1+m);
  122.         ans=0;
  123.         sum=0;
  124.         for(int i=1;i<=m;i++)
  125.         {
  126.             x=findr(edges[i].u);
  127.             y=findr(edges[i].v);
  128.             if(x!=y)
  129.             {
  130.                 sum+=edges[i].e;
  131.                 root[x]=y;
  132.                 temp.e=edges[i].e;
  133.                 temp.to=edges[i].u;
  134.                 vec[edges[i].v].push_back(temp);
  135.                 temp.to=edges[i].v;
  136.                 vec[edges[i].u].push_back(temp);
  137.             }
  138.         }
  139.         dfs(1,0,0);
  140.         while(k--)
  141.         {
  142.             scanf("%d",&now);
  143.             ans+=e[now];
  144.             x=u[now];
  145.             y=v[now];
  146.             now=lca(x,y);
  147.             ans+=sum-max(ask(now,x),ask(now,y));
  148.         }
  149.         printf("%lld\n",ans);
  150.     }
  151.     return 0;
  152. }

G 地雷迷阵

    无法过桥的情况只有一种：某些地雷连成一片，并且分别和桥的宽度方向的两个边界有接触。所以我们只需要枚举任意两个地雷，看他们是否有接触，如果有就连一条边。同时枚举地雷考虑和左右边界有没有接触。最后跑个搜索染色看看左右边界是否连在一起即可。
    时间复杂度o(T*N*N)，空间复杂度o(N*N)。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring>
  5. using namespace std;
  7. double x[105],y[105],r[105];
  8. bool maps[105][105];
  9. bool vis[105];
  10. int n;
  12. bool ok(int a,int b)
  13. {
  14.     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]);
  15. }
  16. void dfs(int x)
  17. {
  18.     vis[x]=1;
  19.     for(int i=0;i<=n+1;i++)
  20.     {
  21.         if(maps[x][i] && !vis[i])
  22.         {
  23.             dfs(i);
  24.         }
  25.     }
  26. }
  28. int main()
  29. {
  30.     int t;
  31.     double l,w;
  32.     scanf("%d",&t);
  33.     while(t--)
  34.     {
  35.         scanf("%lf%lf%d",&w,&l,&n);
  36.         for(int i=1;i<=n;i++)
  37.             scanf("%lf%lf%lf",&x[i],&y[i],&r[i]);
  38.         memset(maps,0,sizeof(maps));
  39.         memset(vis,0,sizeof(vis));
  40.         for(int i=1;i<n;i++)
  41.             for(int j=i+1;j<=n;j++)
  42.             {
  43.                 if(ok(i,j))
  44.                     maps[i][j]=maps[j][i]=1;
  45.             }
  46.         for(int i=1;i<=n;i++)
  47.         {
  48.             if(x[i]<=r[i])
  49.                 maps[0][i]=maps[i][0]=1;
  50.             if(x[i]+r[i]>=w)
  51.                 maps[n+1][i]=maps[i][n+1]=1;
  52.         }
  53.         dfs(0);
  54.         if(vis[n+1])
  55.             printf("GG\n");
  56.         else
  57.             printf("Nice\n");
  58.     }
  59.     return 0;
  60. }

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;
  6. long long com(int n,int m)
  7. {
  8.     long long now=1;
  9.     if(m>n)
  10.         return 0;
  11.     for(int i=1;i<=m;i++)
  12.     {
  13.         now=now*n;
  14.         n--;
  15.         now=now/i;
  16.     }
  17.     return now;
  18. }
  20. int main()
  21. {
  22.     int t,n1,n2,m,k;
  23.     long long ans;
  24.     scanf("%d",&t);
  25.     while(t--)
  26.     {
  27.         scanf("%d%d%d%d",&n1,&n2,&m,&k);
  28.         ans=0;
  29.         for(int i=0;i<=m;i++)
  30.         {
  31.             if(m-i<k)
  32.                 ans+=com(n1-n2,i)*com(n2,m-i);
  33.         }
  34.         printf("%lld\n",ans);
  35.     }
  36.     return 0;
  37. }

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;
  8. char s[1005];
  9. int ans[1005];
  10. bool ok[1005][1005];
  11. int l[1005],r[1005];
  12. queue <int> q;
  14. int main()
  15. {
  16.     int t,n,m,temp,cnt;
  17.     bool flag;
  18.     scanf("%d",&t);
  19.     while(t--)
  20.     {
  21.         scanf("%d%d",&n,&m);
  22.         scanf("%s",s+1);
  23.         flag=0;
  24.         cnt=0;
  25.         for(int i=1;i<=n;i++)
  26.         {
  27.             if(s[i]=='O')
  28.             {
  29.                 if(!flag)
  30.                 {
  31.                     cnt++;
  32.                     l[cnt]=i;
  33.                     flag=1;
  34.                 }
  35.             }
  36.             else
  37.             {
  38.                 if(flag)
  39.                 {
  40.                     r[cnt]=i-1;
  41.                     flag=0;
  42.                 }
  43.             }
  44.         }
  45.         if(flag)
  46.             r[cnt]=n;
  47.         for(int i=1;i<=cnt;i++)
  48.         {
  49.             ans[i]=-1;
  50.             for(int j=1;j<=cnt;j++)
  51.                 ok[i][j]=0;
  52.         }
  53.         for(int i=1;i<cnt;i++)
  54.             for(int j=i+1;j<=cnt;j++)
  55.             {
  56.                 if(l[i]+m+1<=r[j] && r[i]+m+1>=l[j])
  57.                     ok[i][j]=ok[j][i]=1;
  58.             }
  59.         ans[1]=0;
  60.         q.push(1);
  61.         while(!q.empty())
  62.         {
  63.             temp=q.front();
  64.             q.pop();
  65.             for(int i=1;i<=cnt;i++)
  66.             {
  67.                 if(ans[i]==-1 && ok[temp][i])
  68.                 {
  69.                     ans[i]=ans[temp]+1;
  70.                     q.push(i);
  71.                 }
  72.             }
  73.         }
  74.         printf("%d\n",ans[cnt]);
  75.     }
  76.     return 0;
  77. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注