复健，时间有限题解比较简陋

A. Middle of the Contest

将小时转成分钟，得到起止时间在一天中的分钟数，取平均值即可，复杂度O(1)。平均值转换会时间的时候注意前导0。

  1. void solve(int x) {
  2.     x /= 2;
  3.     printf("%02d:%02d\n", x / 60, x % 60);
  4. }
  5. int main() {
  6.     // freopen("in.txt", "r", stdin);
  7.     // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)cpp;
  8.     int h1, h2, m1, m2;
  9.     char c;
  10.     cin >> h1 >> c >> m1;
  11.     cin >> h2 >> c >> m2;
  12.     solve(h1 * 60 + m1 + h2 * 60 + m2);
  13. }

B. Preparation for International Women’s Day

要加起来能被k整除, 只需要看模k的余数即可。余数为i的与余数为k-i的互补可以被k整除，通过计数看有多少对能互补。需要注意的是，为余数为0和k/2（k为偶数）时，只能同余数的互补，此时计数是偶数个时都能配对，奇数个时能配对的数量是计数 - 1。复杂度O(n + k)。

  1. int main() {
  2.     // freopen("in.txt", "r", stdin);
  3.     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  4.     int n, k, x, cnt = 0;
  5.     cin >> n >> k;
  6.     int d[k] = {0};
  7.     for (int i = 0; i < n; ++i) cin >> x, d[x % k]++;
  8.     for (int i = 0; i < (k + 1) / 2; ++i) {
  9.         if (i == 0)
  10.             cnt += d[i] / 2;
  11.         else {
  12.             cnt += min(d[i], d[k - i]);
  13.         }
  14.     }
  15.     if (k % 2 == 0) cnt += d[k / 2] / 2;
  16.     cout << cnt * 2;
  17. }

C. Balanced Team

单调队列，从小到大添加元素，保证队首和队尾差不超过5，超过了则出队，否则用当前队列大小更新最优解。如果元素x < y则x一定比y先入队，而且能与x共存的最小值sx和能与y共存的最小值sy有sx <= sy。使用单调队列，每次入队后进行出队操作，出队完成后队首就是能与入队元素共存的最小值，队列内的元素就是以入队元素为最大值时所有能存在的元素。复杂度O(n)

  1. int main() {
  2.     // freopen("in.txt", "r", stdin);
  3.     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  4.     int n;
  5.     cin >> n;
  6.     ll a[n + 1];
  7.     for (int i = 1; i <= n; ++i) cin >> a[i];
  8.     sort(a + 1, a + 1 + n);
  9.     int cnt = 0, l = 1, r = 2;
  10.     while (l <= r && r <= n) {
  11.         if (a[r] - a[l] > 5) cnt = max(cnt, r - l), l++;
  12.         r++;
  13.     }
  14.     cnt = max(cnt, r - l);
  15.     cout << cnt;
  16. }

D. Zero Quantity Maximization

d * a[i] + b[i] = 0可得d = - b[i] / a[i]，统计每种d取值的个数，取最大即可。对于a[i]为0的情况需要特殊讨论，如果b[i]也为0则此时d可以取任意值；否则，d的取值为0。另外，为了避免浮点误差，不能直接统计d，而是要统计<a, b>这个配对；同时，为了归一化，需要将a与b同时除以他们的最大公约数，并保证a是正数。复杂度O(nlog(n)),log是因为用了map来计数。

  1. // Author : RioTian
  2. // Time : 20/11/10
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. typedef long long ll;
  6. const int N = 1e5 + 10;
  7. int main() {
  8.     // freopen("in.txt", "r", stdin);
  9.     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  10.     int n;
  11.     cin >> n;
  12.     ll a[n + 1], b[n + 1];
  13.     for (int i = 0; i < n; ++i) {
  14.         cin >> a[i];
  15.     }
  16.     for (int i = 0; i < n; ++i) {
  17.         cin >> b[i];
  18.     }
  19.     int zeroBCnt = 0, zeroBothCnt = 0;
  20.     map<pair<int, int>, int> hash;
  21.     for (int i = 0; i < n; ++i) {
  22.         if (a[i] == 0) {
  23.             if (b[i] == 0) ++zeroBothCnt;
  24.             continue;
  25.         }
  26.         if (b[i] == 0) {
  27.             ++zeroBCnt;
  28.         }
  29.         int divisor = gcd(abs(a[i]), abs(b[i]));
  30.         a[i] /= divisor;
  31.         b[i] /= divisor;
  32.         if (a[i] < 0) {
  33.             a[i] = -a[i];
  34.             b[i] = -b[i];
  35.         }
  36.         if (hash[make_pair(a[i], b[i])])
  37.             ++hash[make_pair(a[i], b[i])];
  38.         else
  39.             hash[make_pair(a[i], b[i])] = 1;
  40.     }
  41.     int ans = zeroBCnt;
  42.     for (auto item : hash) {
  43.         if (item.second > ans) ans = item.second;
  44.     }
  45.     cout << ans + zeroBothCnt << endl;
  46.     return 0;
  47. }

E. K Balanced Teams

与C题思路类似，先得到取每个元素为最大值，能共存的元素有哪些（排过序的数组保留首位指针即可），比如位置为i的元素最小可共存元素的位置是maxStart[i]，这样数组里面maxStart[i]到i都是可共存元素。问题就转成如何在里面选k个，让元素尽量多，这样dp即可。dp[i][j]表示前i个元素选j队的最优值，则如果选maxStart[i]到i，最优值为dp[maxStart[i] - 1], j - 1] + i - maxStart[i] + 1；如果不选，最优值为dp[i - 1][j]；两者取最优得到状态转移方程。另外由于j只会从j - 1转移，因此可以用滚动数组节约内存。复杂度O(nk)。

  1. // Author : RioTian
  2. // Time : 20/11/10
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. const int N = 5e3 + 10;
  6. int a[N], maxStart[N], dp[N][2];
  7. int n, k;
  8. int main() {
  9.     cin >> n >> k;
  10.     for (int i = 0; i < n; ++i) cin >> a[i];
  11.     sort(a, a + n);
  12.     int l = 0, r = 0;
  13.     while (r < n) {
  14.         if (a[r] - a[l] <= 5) {
  15.             maxStart[r] = l, ++r;
  16.             continue;
  17.         }
  18.         ++l;
  19.     }
  20.     for (int i = 1; i <= k; ++i) {
  21.         for (int j = 0; j < n; ++j) {
  22.             if (maxStart[j]) {
  23.                 dp[j][i % 2] =
  24.                     max(dp[j - 1][i % 2],
  25.                         dp[maxStart[j] - 1][(i - 1) % 2] + j - maxStart[j] + 1);
  26.                 continue;
  27.             }
  28.             dp[j][i % 2] = max(dp[j - 1][i % 2], j - maxStart[j] + 1);
  29.         }
  30.     }
  31.     cout << dp[n - 1][k % 2] << endl;
  32.     return 0;
  33. }

F1. Spanning Tree with Maximum Degree

直接找到度最大的节点bfs即可，复杂度O(n + m)。

  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  5. using namespace std;
  7. vector<int> node[200010];
  8. bool visited[200010];
  10. void bfs(int start) {
  11.     queue<int> qu;
  12.     qu.push(start);
  13.     visited[start] = true;
  14.     while (qu.size()) {
  15.         int cur = qu.front();
  16.         qu.pop();
  17.         for (auto next : node[cur]) {
  18.             if (visited[next]) continue;
  19.             visited[next] = true;
  20.             qu.push(next);
  21.             cout << cur + 1 << ' ' << next + 1 << endl;
  22.         }
  23.     }
  24. }
  26. int main() {
  27.     int n, m, x, y, tmp, maxCnt = 0, maxNode = -1;
  28.     cin >> n >> m;
  29.     for (int i = 0; i < m; ++i) {
  30.         cin >> x >> y;
  31.         --x;
  32.         --y;
  33.         node[x].push_back(y);
  34.         node[y].push_back(x);
  35.         tmp = node[x].size() > node[y].size() ? x : y;
  36.         if (node[tmp].size() > maxCnt) {
  37.             maxCnt = node[tmp].size();
  38.             maxNode = tmp;
  39.         }
  40.     }
  41.     bfs(maxNode);
  42.     return 0;
  43. }

F2. Spanning Tree with One Fixed Degree

如果从1的一个分支出发能从另一个分支回到1，则这些分支划分为同一组，dfs即可得到这些分组。如果一组里面所有分支都被去掉了，则这组里面的节点就无法出现在树里面，因此至少要保留一个。dfs得到有多少这样的组，每组里面取一个分支，剩下还可以取则任意取。这些分支作为bfs的第一步，继续搜下去，按搜索顺序输出即可。非法的情况有：dfs时存在节点没有走到；需要的度数比组数少（此时至少有一组所有分支都被去掉）；需要的度数比1链接的分支多。复杂度O(n + m)。

  1. #include <cstring>
  2. #include <iostream>
  3. #include <queue>
  4. #include <vector>
  6. using namespace std;
  7. bool visited[200010];
  8. vector<int> node[200010];
  9. vector<int> group[200010];
  10. queue<int> qu;
  11. int n, m, d, g;
  13. void dfs(int cur, int parent) {
  14.     visited[cur] = true;
  15.     for (auto next : node[cur]) {
  16.         if (visited[next]) {
  17.             if (parent == -1) group[g - 1].push_back(next);
  18.             continue;
  19.         }
  20.         if (parent == -1) {
  21.             group[g++].push_back(next);
  22.         }
  23.         dfs(next, cur);
  24.     }
  25. }
  27. void bfs() {
  28.     while (qu.size()) {
  29.         int cur = qu.front();
  30.         qu.pop();
  31.         for (auto next : node[cur]) {
  32.             if (!visited[next]) {
  33.                 visited[next] = true;
  34.                 cout << cur + 1 << ' ' << next + 1 << endl;
  35.                 qu.push(next);
  36.             }
  37.         }
  38.     }
  39. }
  41. int main() {
  42.     int x, y;
  43.     cin >> n >> m >> d;
  44.     for (int i = 0; i < m; ++i) {
  45.         cin >> x >> y;
  46.         --x;
  47.         --y;
  48.         node[x].push_back(y);
  49.         node[y].push_back(x);
  50.     }
  51.     memset(visited, 0, sizeof(visited));
  52.     dfs(0, -1);
  53.     for (int i = 0; i < n; ++i) {
  54.         if (!visited[i]) {
  55.             cout << "NO" << endl;
  56.             return 0;
  57.         }
  58.     }
  59.     if (g > d || node[0].size() < d) {
  60.         cout << "NO" << endl;
  61.         return 0;
  62.     }
  63.     cout << "YES" << endl;
  64.     memset(visited, 0, sizeof(visited));
  65.     visited[0] = true;
  66.     d -= g;
  67.     for (int i = 0; i < g; ++i) {
  68.         cout << '1' << ' ' << group[i][0] + 1 << endl;
  69.         visited[group[i][0]] = true;
  70.         qu.push(group[i][0]);
  71.         for (int j = 1; d && j < group[i].size(); ++j) {
  72.             cout << '1' << ' ' << group[i][j] + 1 << endl;
  73.             visited[group[i][j]] = true;
  74.             qu.push(group[i][j]);
  75.             --d;
  76.         }
  77.     }
  78.     bfs();
  79.     return 0;
  80. }