Codeforces Round #592 (Div. 2)

A - Pens and Pencils

没啥好说,直接做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int a, b, c, d, k;
cin >> a >> b >> c >> d >> k;
int x = (a % c) ? a / c + 1 : a / c;
int y = (b % d) ? b / d + 1 : b / d;
if (x + y > k)
cout << -1 << endl;
else
cout << x << ' ' << y << endl;
}
return 0;
}

B - Rooms and Staircases

可以发现上下楼梯唯一的作用就是回头,因为如果下楼梯仍继续向前走的话和不下楼梯没有区别。然后还可以发现整个过程只能够回头一次,否则就撞车了。

如果没有楼梯,显然只能从一层的一端走到另一端。

如果只有一条楼梯,那么从一层的一端走到楼梯时,可以选择继续走到尽头,也可以选择下楼梯并回头走到尽头。

如果有两条以上的楼梯,要么从一层的一段走到另一端,要么从一层的一端走到最后一个楼梯并下楼然后回头走到尽头。实际上是上一种情况的推广。

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
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> s;
int main()
{
int t;
cin >> t;
while (t--)
{
s.clear();
cin >> n;
for (int i = 1; i <= n; i++)
{
char c = getchar();
while (c != '0' && c != '1')
c = getchar();
if (c == '1')
s.push_back(i);
}

if (s.size() == 0)
cout << n << endl;
else
cout << max(s[s.size() - 1] * 2, max((n - s[0] + 1) * 2, n)) << endl;
}
return 0;
}

D - Paint the Tree

显然只有树是一条链时才存在染色方案。那么只要枚举一下头部两个节点的颜色,后面的都可以推出来。

(讲个笑话,long long best = 0x7fffffff;

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <vector>
using namespace std;

constexpr int MAXN = 100005;
vector<int> edges[MAXN];
void add_edge(int u, int v)
{
edges[u].push_back(v);
}
int n, cnt[MAXN];
int ans[2][MAXN];
long long c[3][MAXN];
bool check(int node, int pa)
{
for (int v : edges[node])
{
if (v != pa)
{
cnt[node]++;
if (!check(v, node))
return false;
}
}
if (pa != -1)
return cnt[node] <= 1;
else
return cnt[node] <= 2;
}
void dfs(int node, int color, int pa, int pa_color, long long &cost)
{
ans[0][node] = color;
cost += c[color][node];
for (int v : edges[node])
{
if (v != pa)
dfs(v, 3 - color - pa_color, node, color, cost);
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> c[0][i];
for (int i = 1; i <= n; i++)
cin >> c[1][i];
for (int i = 1; i <= n; i++)
cin >> c[2][i];

for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
add_edge(u, v);
add_edge(v, u);
}

if (check(1, -1))
{
int head = 0;
for (int i = 1; i <= n; i++)
{
if (cnt[i] == 0)
{
head = i;
break;
}
}
if (head == 0)
{
cout << -1 << endl;
return 0;
}

long long best = 0x7fffffffffffffff, a = 0;
for (int i = 0; i <= 2; i++)
{
for (int j = 0; j <= 2; j++)
{
if (i == j)
continue;
a = 0;
dfs(head, i, -1, j, a);
if (a < best)
{
best = a;
for (int i = 1; i <= n; i++)
ans[1][i] = ans[0][i];
}
}
}

cout << best << endl;
for (int i = 1; i <= n; i++)
cout << ans[1][i] + 1 << ' ';
}
else
cout << -1 << endl;

return 0;
}
Author: ssttkkl
Link: https://ssttkkl.github.io/Codeforces/2019/10/Codeforces-Round-592-Div-2/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.