Codeforce Round#544 div3题解

￡神魔★判官ぃ 2022-01-21 01:57 278阅读 0赞

A.Middle of the Contest

1.题目描述

Problem A,给出开始时间以及截至时间求出中间的时间

2.题目思路

将开始时间以及结束时间都转化为分钟表示，相加除以2即为所得

  1. #include <stdio.h>
  2. int main() 
  3. {
  4.     int h1, h2, m1, m2;
  5.     int m3, h3;
  6.     scanf("%d:%d", &h1, &m1);
  7.     scanf("%d:%d", &h2, &m2);
  9.     int tot =(h1 * 60 + m1 + h2 * 60 + m2)/2;
  10.     h3 = tot / 60;
  11.     m3 = tot % 60;
  12.     if (h3< 10) 
  13.     {
  14.         printf("0%d:", h3);
  15.     }
  16.     else 
  17.     {
  18.         printf("%d:", h3);
  19.     }
  20.     if (m3 < 10) 
  21.     {
  22.         printf("0%d", m3);
  23.     }
  24.     else 
  25.     {
  26.         printf("%d", m3);
  27.     }
  28.     return 0;
  29. }

B.Preparation for International Women’s Day

1.题目

ProblemB

2.题解

首先题目可以简化为n个数，两两相加，满足(a+b)%k==0.

那么无论如何配对，无论a和b的取值是什么，我们都要满足a%k+b%k=0这个条件。

所以我们可以将题目简化，在读取每一个数n的时候，都mod k，并记录下，count[n mod k]

那么此时配对就变得简单，我们只需要找count[i]以及count[m-i],当两个都不为0的时候，sum+=min(mount[i],count[m-i]).

还有一种特殊的情况就是2*i=k的时候，这种情况需要特判，sum+=(count[i]/2)

最后由于我们计算的时候都只计算了一组，所以最后结果需要*2

3.代码

  1. #include <stdio.h>
  2. const int maxn = 200007;
  3. int box[maxn];
  4. bool visit[maxn] = { false };
  5. int count[107] = { false };
  6. int min(int a,int b) 
  7. {
  8.     if (a > b)
  9.         return b;
  10.     return a;
  11. }
  12. int main() 
  13. {
  14.     int n, m;
  15.     int sum = 0;
  16.     scanf("%d%d", &n, &m);
  17.     for (int i = 1; i <= n; i++) 
  18.     {
  19.         scanf("%d", &box[i]);
  20.         box[i] %= m;
  21.     }
  22.     for (int i = 1; i <= n; i++) 
  23.     {
  24.         count[box[i]]++;
  25.     }
  26.     sum += (count[0] / 2);
  27.         for (int i = 1; i <= m/2; i++)
  28.         {
  29.             if (i * 2 == m) 
  30.             {
  31.                 sum += count[i] / 2;
  32.             }
  33.             else
  34.             {
  35.                 if (count[i] && count[m - i])
  36.                 {
  37.                     sum += min(count[i], count[m - i]);
  38.                 }
  39.             }
  40.         }
  41.     printf("%d", sum*2);
  42.     return 0;
  43. }

C.Balanced Team

1.题目

ProblemC

2.解答

先求出数组相邻两个数的差值，并存为另一个数组，那么此时，我们可以将问题转化为，求在转化过后的数组中连续和不超过5的数的最大的长度即可。

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. const int maxn = 200007;
  5. int num[maxn] = { 0 };
  6. int num2[maxn] = { 0 };
  7. bool cmp(int a,int b)
  8. {
  9.     return a < b;
  10. }
  11. int main() 
  12. {
  13.     int n;
  14.     scanf("%d", &n);
  15.     for(int i=1;i<=n;i++)
  16.     {
  17.         scanf("%d", &num[i]);
  18.     }
  19.     sort(num + 1, num + n + 1, cmp);
  20.     int count = 0;
  21.     int max = -1;
  22.     for(int i=1;i<=n-1;i++)
  23.     {
  24.         num2[i] = num[i + 1] - num[i];
  25.     }
  26.     bool flag = false;
  27.     int sum = 0;
  28.     int j = 0;
  29.     int o = 0;
  30.     int p;
  31.     for(int i=1;i<=n-1;i++)
  32.     {
  33.         o = sum;
  34.         sum =sum+num2[i];
  35.         p = sum;
  36.         if(o<p&&!flag)
  37.         {
  38.             flag = true;
  39.             j = i;
  40.         }
  41.         if(sum>5)
  42.         {
  43.             sum = 0;
  44.             count = 0;
  45.             i = j;
  46.             flag = false;
  47.         }
  48.         else 
  49.         {
  50.             count++;
  51.         }
  52.         if(count>max)
  53.         {
  54.             max = count;
  55.         }
  56.     }
  57.     if(n==1)
  58.     {
  59.         printf("1");
  60.     }
  61.     else
  62.     printf("%d", max+1);
  63.     return 0;
  64. }

D.Zero Quantity Maximization

1.题目

ProblemD

2.解答

自己的思路，

构建结构体，并记录下d=a/b的值,对结构体数组关于d进行排序，再依次比对d的值，求出答案，没过emmm，考虑可能是精度问题，故舍弃

2.依然是构建结构体，此时不去管a/b的值，而是去求a和b的最小公因数r，并同时令a/r,b/r然后对结构体数组进行排序(以a的大小为序),然后再比较前后的值求解，没有通过，找不到原因+1；

3.放弃结构体，考虑stl中的map，以及pair类型

有关pair的用法参照pair传送门

map的用法参照map传送门

跟结构体用法基本类似，所以不是很能理解为什么第二种算法不对，emm可能这就是玄学吧，另外掌握了别的技巧还是蛮不错的。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=2*1e5+7;
  5. int gcd(int a,int b)
  6. {
  7.     if(b==0)
  8.     {
  9.         return a;
  10.     }
  11.     int r=1;
  12.     while(r)
  13.     {
  14.         r=a%b;
  15.         a=b;
  16.         b=r;
  17.     }    
  18.     return a;
  19. }
  21. int main()
  22. {
  23.     int n;
  24.     int a[maxn];
  25.     int b[maxn];
  26.     scanf("%d",&n);
  27.     for(int i=1;i<=n;i++)
  28.     {
  29.         scanf("%d",&a[i]);
  30.     }
  31.     for(int i=1;i<=n;i++)
  32.     {
  33.         scanf("%d",&b[i]);
  34.     }
  35.     map<pair<int,int>,int>test;
  36.     int special=0;
  37.     for(int i=1;i<=n;i++)
  38.     {
  39.         if(a[i]!=0)
  40.         {
  41.             int r=gcd(a[i],b[i]);
  42.             a[i]/=r;
  43.             b[i]/=r;
  44.         }
  45.     }
  46.     for(int i=1;i<=n;i++)
  47.     {
  48.         if(b[i]==0&&a[i]==0)
  49.         {
  50.             special++;    
  51.         } 
  52.         else if(a[i]==0)
  53.         {
  54.             continue;
  55.         }
  56.         else
  57.         {
  58.             test[{a[i],b[i]}]++;
  59.         }
  60.     }
  61.     int ans=0;
  62.     map<pair<int,int>,int>::iterator iter;
  63.     for(iter=test.begin();iter!=test.end();iter++)
  64.     {
  65.         ans=ans>iter->second?ans:iter->second;
  66.     }
  67.     ans+=special;
  68.     printf("%d",ans);
  69.     return 0;
  70. }

E.K Balanced Teams

1.题目

E

2.解答

这道题还是懵逼状态，所以参照了E题的官方题解，下面给出思路。（使用动态规划）

我们用dp[i][j]来表示，有i个人，j个队伍时答案的最优解。

首先我们对学生序列按照从小到大进行排列，与此同时，我们记录此时从第i个学生开始，向后寻找学生组队，该队伍的人数最多能有多少。最后进行dp,详细看代码注释。

  1. #include <stdio.h>
  2. #include <algorithm>
  3. using namespace std;
  4. const int maxn=5007;
  5. int num[maxn]={0};
  6. int dp[maxn][maxn]={0};//表示i个人，j个队伍的时候，所能容纳最多的人数 
  7. bool cmp(int a,int b)
  8. {
  9.     return a<b;
  10. }
  11. int max(int a,int b)
  12. {
  13.     if(a>b)
  14.     return a;
  15.     return b;
  16. }
  18. int main()
  19. {
  20.     int n;
  21.     int m;
  22.     scanf("%d%d",&n,&m);
  23.     for(int i=1;i<=n;i++)
  24.     {
  25.         scanf("%d",&num[i]);
  26.     }
  27.     sort(num+1,num+1+n,cmp);//按能力大小进行排序 
  28.     int cnt[maxn]={0};
  29.     for(int i=1;i<=n;i++)
  30.     {
  31.         while(i+cnt[i]<=n&&num[i+cnt[i]]-num[i]<=5)
  32.         {
  33.             cnt[i]++;//这里记录从第i个位置的同学开始的团队最多容纳学生的个数 
  34.         }
  35.     }
  36.     for(int i=1;i<=n;i++)
  37.     {
  38.         for(int j=0;j<=m;j++)
  39.         {
  40.             dp[i+1][j]=max(dp[i+1][j],dp[i][j]); //判断是从当前节点开始最好，还是从下一个节点开始最好 
  41.             if(j+1<=m)
  42.             {
  43.                 dp[i+cnt[i]][j+1]=max(dp[i+cnt[i]][j+1],dp[i][j]+cnt[i]);//此处是利用上面求出的cnt[i]，人数超过cnt[i]的时候，就要多开一支队伍 
  44.                 //为了使得总人数最大化，此处人数一定要加上cnt[i] 
  45.             }
  47.         }
  48.     }
  49.     printf("%d",dp[n+1][m]);
  50.     return 0;    
  51. }

F1.Spanning Tree with Maximum Degree

1.题目

F1

2.题解

题目是不难，只要读取图，然后找出度数最大的点，然后从这个点开始进行bfs操作即可。

但是在处理的过程中遇到了一些问题

1.想要建立二维数组来保存整张图的关系，结果发现图的边数太大，二维数组开不下，转用vector

2.在进行bfs的时候，由于是用数组来模拟队列，所以最后导致了空间超出。转用stl中的queue

3.在bfs的时候，因为多加入了一个判断是否已经遍历完当前点的循环，导致时间超出。

最终代码如下

  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  6. const int maxn=2*1e5+7;
  7. vector< vector<int> > g;
  8. bool visit[maxn]={false};
  9. int deg[maxn];
  10. int n;
  11. long long int m;
  12. void bfs(int number)
  13. {
  14.     queue<int>q;
  15.     q.push(number);
  16.     while(!q.empty())
  17.     {
  18.         int v=q.front();
  19.         q.pop();
  20.         for(int i=0;i<g[v].size();i++)
  21.         {
  22.             if(!visit[g[v][i]])
  23.             {
  24.                 printf("%d %d\n",v,g[v][i]);
  25.                 q.push(g[v][i]);
  26.                 visit[g[v][i]]=true;
  27.             }
  28.         }
  29.     }
  30. }
  32. int main()
  33. {
  34.     scanf("%d%lld",&n,&m);
  35.     int a,b;
  36.     g=vector<vector<int> >(maxn);
  37.     for(long long int i=1;i<=m;i++)
  38.     {
  39.         scanf("%d%d",&a,&b);
  40.         g[a].push_back(b);
  41.         g[b].push_back(a);
  42.         deg[a]++;
  43.         deg[b]++;
  44.     }
  45.     int pos=1;
  46.     for(int i=1;i<=n;i++)
  47.     {
  48.         if(deg[i]>deg[pos])
  49.         {
  50.             pos=i;
  51.         }
  52.     }
  53.     visit[pos]=true;
  54.     bfs(pos);
  55.     return 0;
  56. }

F2.Spanning Tree with One Fixed Degree

1.题目

F2

2.题解

看的时候完全没有思路，所以直接看了官方的题解。

实现思路如下

Step1:

将一号节点从整个图中删去，然后从其他节点开始，搜索生成树，该操作的目的是寻找只与一号节点相连的点的个数，（即该点无法通过与一号店相连的其他点到达）我们将这个个数叫做cnt

Step2:

不存在的情况只有两种，一种是cnt>D的情况即只与一号点的相连的个数要比需要的多，此时肯定无法找到，可以参照下面的图理解一下。另外一种则是，本身与一号点相连的点的个数要小于D，这个就不做过多解释

Step3：

接下来一是我们要将上面找到的cnt个节点加入答案序列中，二是我们要将随意挑选D-cnt个节点加入答案序列，重新构造图，再从一号节点进行bfs即可。（由于此时只有D个节点与一号节点相连，所以一定满足情况）

标程实现

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. int n, m, D;
  6. vector<vector<int>> g;
  8. int cnt;
  9. vector<int> p, color;
  10. vector<pair<int, int>> ans;
  12. mt19937 rnd(time(NULL));
  14. void bfs(int s, int bad) {
  15.     queue<int> q; 
  16.     q.push(s);
  17.     color[s] = cnt;//该步骤可以理解为上色过程，将联通的一块儿节点赋予相同的颜色
  18.     while (!q.empty()) {//bfs内容
  19.         int v = q.front();
  20.         q.pop();
  21.         if (p[v] != -1) {//此处为随机内容，主要目的是记录答案的值
  22.             if (rnd() & 1) ans.push_back(make_pair(p[v], v));
  23.             else ans.push_back(make_pair(v, p[v]));
  24.         }
  25.         for (auto to : g[v]) {
  26.             if (to == bad || color[to] != -1) continue;//如果是一号节点，或者已经属于另一块儿就不进行操作
  27.             p[to] = v;//记录下朝向的节点，方便上面处理答案序列
  28.             color[to] = cnt;//上色
  29.             q.push(to);
  30.         }
  31.     }
  32.     ++cnt;
  33. }
  35. int main() {
  36. #ifdef _DEBUG
  37.     freopen("input.txt", "r", stdin);
  38. //    freopen("output.txt", "w", stdout);
  39. #endif
  41.     cin >> n >> m >> D;
  42.     g = vector<vector<int>>(n);
  43.     for (int i = 0; i < m; ++i) {
  44.         int x, y;
  45.         cin >> x >> y;
  46.         --x, --y;
  47.         g[x].push_back(y);
  48.         g[y].push_back(x);
  49.     }
  50.     //读入数据 
  51.     p = color = vector<int>(n, -1);
  52.     cnt = 0;
  53.     for (int i = 1; i < n; ++i) {
  54.         if (color[i] == -1) {
  55.             bfs(i, 0);
  56.         }
  57.     }//统计"只"与1号节点相连的节点有多少 
  59.     if (cnt > D || D > int(g[0].size())) {
  60.         cout << "NO" << endl;
  61.         return 0;
  62.     }//不满足的情况只有两种，第一个是1的度不足D，二是D要比只与1号节点相连的节点要少 
  64.     sort(g[0].begin(), g[0].end(), [](int a, int b) {
  65.         return color[a] < color[b];
  66.     });//此处是为了下一步方便判断是否加入一号节点
  68.     for (int i = 0; i < int(g[0].size()); ++i) {
  69.         if (i == 0 || color[g[0][i]] != color[g[0][i - 1]]) {
  70.             ans.push_back(make_pair(0, g[0][i]));//如果两个节点不属于同一颜色块儿，就加入答案序列 
  71.         }
  72.     }
  74.     D -= cnt;//剩下的节点 
  75.     for (int i = 1; i < int(g[0].size()); ++i) {
  76.         if (D == 0)//剩下节点为0 
  77.         break;
  78.         if (color[g[0][i]] == color[g[0][i - 1]]) 
  79.         {    
  80.             ans.push_back(make_pair(0, g[0][i]));//再剩下的与1相连的节点中寻找剩下的节点 
  81.             --D;
  82.         }
  83.     }
  85.     g = vector<vector<int>>(n);//初始化g，重构图 
  86.     for (auto it : ans) {
  87.         g[it.first].push_back(it.second);
  88.         g[it.second].push_back(it.first);
  89.     }//进行重新连接 即将多余的节点与1号节点的连接断开 
  91.     ans.clear();清空答案序列，重新进行bfs，寻找答案序列
  92.     p = color = vector<int>(n, -1);//初始化p数组，以及颜色数组，由于只写了一个bfs此处可以方便操作，也可以考虑再写一个bfs
  93.     cnt = 0;
  94.     bfs(0, -1);//进行bfs 
  95.     shuffle(ans.begin(), ans.end(), rnd);//随机排列，但并没有必要
  96.     cout << "YES" << endl;
  97.     for (auto it : ans) {
  98.         cout << it.first + 1 << " " << it.second + 1 << endl;
  99.     }
  100.     return 0;
  101. }

发表评论

表情：
评论列表 （有 0 条评论，278人围观）

还没有评论，来说两句吧...

相关阅读