Codeforces Round #544 (Div. 3)
A. Middle of the Contest
题意
求两个时间段的中点。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* <<head>> */
// ------- 变量 ------- //
int h1, m1, h2, m2;
// ------- 函数 ------- //
void Init() {
scanf("%d:%d%d:%d", &h1, &m1, &h2, &m2);
}
int Solve() {
int a = h1 * 60 + m1;
int b = h2 * 60 + m2;
int c = b - a >> 1;
a += c;
return printf("%02d:%02d\n", a/60, a%60);
}
B. Preparation for International Women’s Day
题意
$n$ 个数，最多能分多少组，使得每组两个数，且两个数相加可被 $k$ 整除。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/* <<head>> */
const int N = (int)1e5+7;
// ------- 变量 ------- //
int n, k;
int cnt[107];
// ------- 函数 ------- //
void Init() {
scanf("%d%d", &n, &k);
rep(i, 0, n) {
int x; scanf("%d", &x);
cnt[x%k]++;
}
}
int Solve() {
ll ans = 0;
rep(i, 1, (k+1)/2) ans += min(cnt[i], cnt[k-i]);
if (~k & 1) ans += cnt[k/2] / 2;
ans += cnt[0] / 2;
return printf("%lld\n", ans << 1);
}
C. Balanced Team
题意
$n$ 个数，选尽可能多的数，使得两两差值不超过 $5$ 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* <<head>> */
const int N = (int)2e5+7;
// ------- 变量 ------- //
int n, a[N];
// ------- 函数 ------- //
void Init() {
scanf("%d", &n);
rep(i, 0, n) scanf("%d", a+i);
}
int Solve() {
sort(a, a + n);
int ans = -INF, r = 1;
rep(l, 0, n) {
while (r < n && a[r] - a[l] <= 5) r++;
ans = max(ans, r - l);
}
return printf("%d\n", ans);
}
D. Zero Quantity Maximization
题意
$n$ 个数 $a[\ ]$ 和 $n$ 个数 $b[\ ]$ ，令 $c[i] = d \cdot a[i] + b[i]$ ，求：当选择最优的 $d$ 时， $c[\ ]$ 中最多有多少个 $0$ 。
题解
推导出 $\large d = -\frac{b[i]}{a[i]}$ ，用 $map$ 记录。
特判 $a[i] = 0$ 的情况，累加到答案。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/* <<head>> */
const int N = (int)2e5+7;
// ------- 变量 ------- //
int n, a[N], b[N];
map <pii, int> M;
// ------- 函数 ------- //
pii work(int a, int b) {
int g = __gcd(a, b);
a /= g; b /= g;
if (a < 0) return mp(-a, -b);
return mp(a, b);
}
void Init() {
scanf("%d", &n);
M.clear();
rep(i, 1, n+1) scanf("%d", a+i);
rep(i, 1, n+1) scanf("%d", b+i);
}
int Solve() {
int ans = 0, num = 0;
rep(i, 1, n+1) num += (a[i] == 0 && b[i] == 0);
rep(i, 1, n+1) {
if (a[i] == 0) continue;
int tmp = ++M[work(a[i], b[i])];
ans = max(ans, tmp);
}
return printf("%d\n", ans + num);
}
E. K Balanced Teams
dp
题意
$n$ 个数分 $k$ 组，每组内极差不超过 $5$ ，求最多有多少个数可被分到组内。
$1 \le k \le n \le 5000$
$1 \le a_i \le 10^9$
题解
-
从小到大排序，分组一定为若干段。
-
预处理 $pre[i]$ 表示第 $i$ 个数向左最长延伸多长。
-
$dp[i][j]$ 表示前 $i$ 个数，分 $j$ 组的答案，转移有：
-
不使用第 $j$ 个数：
$dp[i][j] = dp[i-1][j]$
-
以第 $j$ 个数作为最后一组的最后一个数：
$dp[i][j] = dp[i-pre[i]][j-1] + pre[i]$
-
-
边界情况： $i-pre[i]$ 可能会小于 $j-1$
-
当 $dp[i][j]$ 的 $i$ 小于 $j$ 时，答案即为 $i$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* <<head>> */
const int N = (int)5e3+7;
// ------- 变量 ------- //
int n, k, a[N], pre[N], dp[N][N];
// ------- 函数 ------- //
void Init() {
scanf("%d%d", &n, &k);
memset(dp, 0, sizeof(dp));
rep(i, 1, n+1) scanf("%d", a+i);
sort(a + 1, a + n + 1);
}
int Solve() {
int l = 1;
rep(r, 1, n+1) {
while (a[r] - a[l] > 5) l++;
pre[r] = r - l + 1;
}
rep(i, 1, n+1) rep(j, 1, k+1) {
if (i <= j) dp[i][j] = i;
else dp[i][j] = max(dp[i-1][j], dp[i-pre[i]][j-1] + pre[i]);
}
return printf("%d\n", dp[n][k]);
}
F1. Spanning Tree with Maximum Degree
题意
$n$ 个点， $m$ 条边，求一棵生成树，使得度数最大的节点的度数尽可能大。
题解
贪心
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/* <<head>> */
const int N = (int)2e5+7;
// ------- 变量 ------- //
int n, m;
vi e[N];
vector <pii> ans;
// ------- 函数 ------- //
int vis[N];
void bfs(int rt) {
queue <int> Q;
Q.push(rt);
vis[rt] = 1;
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (auto v : e[u]) if (!vis[v]) {
ans.pb(mp(u, v));
Q.push(v);
vis[v] = 1;
}
}
}
void Init() {
scanf("%d%d", &n, &m);
ans.clear();
rep(i, 0, n+1) e[i].clear();
memset(vis, 0, sizeof(vis));
rep(i, 0, m) {
int u, v; scanf("%d%d", &u, &v);
e[u].pb(v); e[v].pb(u);
}
}
int Solve() {
int mx = 0, rt;
rep(i, 1, n+1) if (sz(e[i]) > mx) {
mx = sz(e[i]); rt = i;
}
bfs(rt);
for (auto o : ans) printf("%d %d\n", o.fi, o.se);
}
F2. Spanning Tree with One Fixed Degree
图论 生成树 并查集
题意
$n$ 个点， $m$ 条边的无向无权连通图，保证无自环和重边。
构造一棵生成树，满足编号为 $1$ 的节点有 $D$ 个度。
$2 \le n \le 2 \cdot 10^5$
$n-1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2})$
$1 < D < n$
题解
- 若 $1$ 号节点度数小于 $D$ ，则无解
- 去掉 $1$ 号节点及所连的边，然后将剩下的点用并查集缩点
- 若连通块个数大于 $D$ ，则无解
- 先将 $1$ 号节点与连通块连边
- 多余的度数随便选择边与连通块相连
- 剩下的边用 $bfs$ 构造
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/* <<head>> */
const int N = (int)2e5+7;
// ------- 变量 ------- //
int n, m, D;
int fa[N], ucc[N], vis_u[N], vis[N];
vi e[N];
// ------- 函数 ------- //
int Find(int x) { return x == fa[x] ? x : fa[x] = Find(fa[x]); }
void Union(int x, int y) { fa[Find(y)] = Find(x); }
void Init() {
scanf("%d%d%d", &n, &m, &D);
memset(vis, 0, sizeof(vis));
memset(vis_u, 0, sizeof(vis_u));
rep(i, 1, n+1) e[i].clear();
rep(i, 1, n+1) fa[i] = i;
rep(i, 0, m) {
int u, v; scanf("%d%d", &u, &v);
e[u].pb(v); e[v].pb(u);
if (u != 1 && v != 1) Union(u, v);
}
}
int Solve() {
if (sz(e[1]) < D) return puts("NO");
rep(i, 2, n+1) ucc[i] = Find(i);
int cnt = 0;
rep(i, 2, n+1) if (ucc[i] == i) cnt++;
if (cnt > D) return puts("NO");
vector <pii> ans;
queue <int> Q;
vis[1] = 1;
for (auto v : e[1]) if (!vis_u[ucc[v]]) {
vis_u[ucc[v]] = 1;
ans.pb(mp(1, v));
vis[v] = 1;
Q.push(v);
}
int d = D - cnt;
for (auto v : e[1]) if (!vis[v]) {
if (d == 0) break;
d--;
ans.pb(mp(1, v));
vis[v] = 1;
Q.push(v);
}
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (auto v : e[u]) if (!vis[v]) {
vis[v] = 1;
ans.pb(mp(u, v));
Q.push(v);
}
}
puts("YES");
for (auto o : ans) printf("%d %d\n", o.fi, o.se);
return 0;
}
