Codeforces Round 544 (Div. 3)

概述

很水的一场比赛，快来做前几场比赛的小清新题！！

A

Description

给出两个时间，求它们中点时间。

Solution

把小时和分钟转化成分钟再取中点，再转化回去即可。

Code

#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 10;

char a[maxn], b[maxn];

int change(char *a)
{
    int h = (a[0] - '0') * 10 + a[1] - '0', m = (a[3] - '0') * 10 + a[4] - '0';
    return h * 60 + m;
}

std::string enchange(int mid)
{
    std::string s = "     ";
    int h = mid / 60, m = mid % 60;
    s[0] = h / 10 + '0', s[1] = h % 10 + '0', s[2] = ':', s[3] = m / 10 + '0', s[4] = m % 10 + '0';
    return s;
}

int main()
{
    cin >> a >> b;
    int p = change(a), q = change(b);
    int mid = (p + q) / 2;
    cout << enchange(mid) << endl;
}

B

Description

从 $n$ 个数中每次选两个数，这两个数的和必须为 $k$ 的倍数。问最多能选出多少个数满足条件。

Solution

显然加入一个数模 $k$ 是 $x$，那么他只能和模 $k$ 是 $k-x$ 的数配对。

开一个桶记录一下每种余数的个数然后统计答案即可。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 2e5 + 10;

int a[maxn], b[maxn], k, n;

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1, x; i <= n; i++)
        cin >> x, b[x % k]++;
    int ans = b[0] / 2 * 2;
    for (int i = 1; i < k / 2; i++)
        ans += std::min(b[i], b[k - i]) * 2;
    if (k % 2 == 0)
        ans += b[k / 2] / 2 * 2;
    else
        ans += std::min(b[k / 2], b[k / 2 + 1]) * 2;
    cout << ans << endl;
}

C

Description

给 $n$ 个数，让你找出 $m$ 个数，使得这 $m$ 个数中的最大值减去最小值不大于 $5$，求最大的 $m$。

Solution

排序 + 双指针，太水了我都不知道该说什么。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 2e5 + 10;

int a[maxn], n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    std::sort(a + 1, a + 1 + n);
    int l = 1, r = 1, ans = 1;
    while (l <= n)
    {
        while (r <= n && a[r] - a[l] <= 5)
            r++;
        ans = std::max(ans, r - l);
        l++;
    }
    cout << ans << endl;
}

D

Description

给出两个长度为 $n$ 的数组 $a,b$。

你想要创建一个长度为 $n$ 的数组 $c$，且 $c_i=d\times a_i+b_i,i\in[1, n]$，要求你给 $d$ 赋值，使得数组 $c$ 中的 $0$ 的个数最多并输出最多的 $0$ 的个数。

Solution

$$ c_i=d\times a_i+b_i\Rightarrow d=\frac{-b_i}{a_i} $$

可以算出来让每个数变成 $0$ 的 $d$ 是多少，然后看看出现次数最多是多少。

为了避免浮点误差，我们把分子分母约分一下然后放进 map 里。

特判一下本来就是 $0$ 的情况。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
#include <map>
#include <utility>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }

typedef std::pair<int, int> pii;
const int maxn = 1e6 + 10;

std::map<pii, int> mp;

int a[maxn], b[maxn], n;
int ans;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i <= n; i++)
        if (a[i] < 0)
            a[i] *= -1, b[i] *= -1;
        else if (a[i] == 0)
            ans += b[i] == 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == 0)
            continue;
        int d = gcd(a[i], b[i] < 0 ? -b[i] : b[i]);
        a[i] /= d, b[i] /= d;
        mp[pii(a[i], b[i])]++;
    }
    int cnt = 0;
    for (auto k : mp)
    {
        cnt = std::max(cnt, k.second);
    }
    cout << ans + cnt << endl;
}

E

Description

您是本地大学的教练，有 $n$ 位选手在你这里学习，并且已知第 $i$ 位的能力值为 $a_i$。

现在您需要挑选出若干位选手组成至多 $k$ 支队伍。众所周知，参赛的人数越多，你的大学获胜的概率越大。所以，你需要使得你选出的至多$k$支（至少$1$支）非空队伍的总人数最多。但是，你知道每支队伍中队员们的实力应当差不多，这意味着对于任意一支队伍，不应当存在两名实力值相差超过 $5$ 的选手。所有的队伍都是相互独立的（这意味着我们不考虑来自两只不同队伍的选手的实力值差距）。

可能有的选手不属于任何一支队伍。

您的任务是求出满足以上要求的至多 $k$（至少 $1$）支非空队伍的总人数。

$n,k\leq5000$。

Solution

数据范围告诉我们要 DP。

我们把实力值排个序，显然如果选了一个人，把和他实力值相差小于 $5$ 的人全选上是最优的。

预处理一个 $lst_i$ 表示第 $i$ 个人，上一个实力值比他小超过 $5$ 的人的位置。

设 $f(i,j)$ 表示前 $i$ 个人，已经组了 $j$ 个队伍的参赛总人数。

然后考虑这个人选不选，有： $$ f(i,j)=\max(f(i-1,j),f(lst_i,j-1)+i-lst_i) $$ 前面是不选，后面是选。

直接转移即可，时间复杂度 $O(nk)$。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 5010;

int lst[maxn], f[maxn][maxn], a[maxn], n, k;

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    std::sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++)
    {
        int pos = i;
        while (pos >= 1 && a[i] - a[pos] <= 5)
            pos--;
        lst[i] = pos;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            f[i][j] = f[i - 1][j];
            f[i][j] = std::max(f[i][j], f[lst[i]][j - 1] + i - lst[i]);
        }
    }
    cout << f[n][k] << endl;
}

F1

Description

给出了一个由 $n$ 个顶点和 $m$ 条边组成的无向无权连通图。它保证在给定的图中没有自环或重边。

你的任务是找到这个图的一棵生成树，使得树上点的最大度数尽可能地大。

Solution

很显然我们可以构造出一棵以原图中度数最大的点为根，包括其在原图上所有相邻结点的树。

BFS 构造一下就行。

Code

#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 2e5 + 10;

int n, m, d;

std::vector<int> e[maxn];
inline void add(int x, int y) { e[x].push_back(y), e[y].push_back(x); }

int cnt, vis[maxn], vis2[maxn], used[maxn];

void bfs(int s)
{
    std::queue<int> q;
    vis2[s] = 1;
    q.push(s);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (int v : e[x])
        {
            if (!vis2[v])
                cout << x << " " << v << endl, q.push(v), vis2[v] = 1;
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0, x, y; i < m; i++)
        cin >> x >> y, add(x, y);
    int s = 1;
    for (int i = 2; i <= n; i++)
        if (e[i].size() > e[s].size())
            s = i;
    bfs(s);
}

F2

Description

给你一个图，让你构造出一个编号为 $1$ 的点的度数为 $D$ 的树

（保证没有自环和重边）

Solution

我们设这棵树以 $1$ 为根。

一开始想的是假如 $1$ 的一个子树内有一条边连向另一个子树，那么这条边就可以删掉。

感觉很点双啊。。。。。。

后来转念一想，都点双了，我们直接把 $1$ 号点删掉然后看有几个联通块不就能得到能删掉几条边了吗？。。。

这样就能判断出来有解的条件：

点 $1$ 的度数不小于 $D$；
删掉 $1$ 之后连通块个数不大于 $D$。

可以 DFS 找连通块，用和 F1 类似的 BFS 做法输出答案。

Code

很丑。

#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 2e5 + 10;

int n, m, d;

std::vector<int> e[maxn];
inline void add(int x, int y) { e[x].push_back(y), e[y].push_back(x); }

int cnt, vis[maxn], vis2[maxn], used[maxn];

void dfs(int x, int p)
{
    vis[x] = p;
    for (int v : e[x])
        if (v != 1 && !vis[v])
            dfs(v, p);
}

void bfs()
{
    std::queue<int> q;
    vis2[1] = 1;
    int tot = 0;
    for (int i = 0; i < (int)e[1].size(); i++)
        if (!used[vis[e[1][i]]])
            q.push(e[1][i]), cout << 1 << " " << e[1][i] << endl, vis2[e[1][i]] = 1, used[vis[e[1][i]]] = 1, tot++;
    for (int v : e[1])
    {
        if (!vis2[v])
            cout << 1 << " " << v << endl, vis2[v] = 1, tot++, q.push(v);
        if (tot == d)
            break;
    }
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (int v : e[x])
        {
            if (!vis2[v])
                cout << x << " " << v << endl, q.push(v), vis2[v] = 1;
        }
    }
}

int main()
{
    cin >> n >> m >> d;
    for (int i = 0, x, y; i < m; i++)
        cin >> x >> y, add(x, y);
    for (int i = 2; i <= n; i++)
        if (!vis[i])
            dfs(i, ++cnt);
    if ((int)e[1].size() < d || cnt > d)
    {
        puts("NO");
        return 0;
    }
    //for (int i = 1; i <= n; i++)
    //    cout << vis[i] << " ";
    //cout << endl;
    puts("YES");
    bfs();
}

概述¶

A¶

Description¶

Solution¶

Code¶

B¶

Description¶

Solution¶

Code¶

C¶

Description¶

Solution¶

Code¶

D¶

Description¶

Solution¶

Code¶

E¶

Description¶

Solution¶

Code¶

F1¶

Description¶

Solution¶

Code¶

F2¶

Description¶

Solution¶

Code¶

概述

A

Description

Solution

Code

B

Description

Solution

Code

C

Description

Solution

Code

D

Description

Solution

Code

E

Description

Solution

Code

F1

Description

Solution

Code

F2

Description

Solution

Code