EOJ Monthly 2019.1 题解

B 唐纳德先生与网络降级计划

有一个 $n$ 个点的无根树,现在要求给每条边定向,使得每个点的出度至多为 $1$,并且对所有 $1 \le i \le q$ 满足 $s_i$ 到 $t_i$ 有通路。

其实就是对每个路径定一个方向,最后考虑一下剩余的边,使得度数不大于 $1$。

对每个询问打一个标记,表示这个点往上走多少个需要被染色为某一个方向,离线后扫一遍即可。

$-1$ 写成 $+1$ 调了三个小时是怎么回事啊?

D 唐纳德先生与 .DOC

猜一发样例对了。

E 唐纳德先生与假骰子

猜一发样例对了。

代码

B

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#define assert(x) do{int a=1,b=0;if(!(x))printf("%d",a/b);}while(0)
#ifdef XLor
#define dbg(args...) do {cout << #args << " -> "; err(args);} while (0)
#else
#define dbg(...)
#endif
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9 + 7;
const int maxn = 1000000 + 5;

int n, q, eu[maxn], ev[maxn], dep[maxn];
vector<PII> edge[maxn];

namespace hld {
int siz[maxn], fa[maxn], son[maxn], top[maxn];
void dfs(int u, int f) {
dep[u] = dep[f] + 1; fa[u] = f; siz[u] = 1; son[u] = 0;
int m = -1;
for (auto& x: edge[u]) {
int v = x.first;
if (v == f) continue;
dfs(v, u);
siz[u] += siz[v];
if (siz[v] > m) son[u] = v, m = siz[v];
}
}
void dfs(int u, int f, int tp) {
top[u] = tp;
if (!son[u]) return;
dfs(son[u], u, tp); //
for (auto& x: edge[u]) {
int v = x.first;
if (v == f || v == son[u]) continue;
dfs(v, u, v);
}
}
void init() {
dfs(1, 0); dfs(1, 0, 1);
}
int qlca(int u, int v) {
while (top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
}
return dep[u] < dep[v] ? u : v;
}
}

int tag[maxn][2], ans[maxn], oud[maxn];
int dfs(int u, int f) {
int a = tag[u][0], b = tag[u][1];
for (auto& x: edge[u]) {
int v = x.first;
if (v == f) continue;
int r = dfs(v, u);
dbg(u, v, r);
if (r < 0) {
if (eu[x.second] == u) ans[x.second] = -1;
else ans[x.second] = 1;
// assert(oud[v] == 0);
oud[v]++;
a = max(a, -r - 1);
} else if (r > 0) {
if (eu[x.second] == u) ans[x.second] = 1;
else ans[x.second] = -1;
// assert(oud[u] == 0);
oud[u]++;
b = max(b, r - 1);
}
assert(a == 0 || b == 0);
}
// assert(a == 0 || b == 0);
if (a) return -a;
if (b) return b;
return 0;
}
void dfs2(int u, int f) {
for (auto& x: edge[u]) {
int v = x.first;
if (v == f) continue;
dfs2(v, u);
if (ans[x.second]) continue;
if (oud[v] == 0) {
if (eu[x.second] == u) ans[x.second] = -1;
else ans[x.second] = 1;
oud[v]++;
} else if (oud[u] == 0) {
if (eu[x.second] == u) ans[x.second] = 1;
else ans[x.second] = -1;
oud[u]++;
} else {
assert(0);
}
}
}

int main(){
int T; scanf("%d", &T);
while (T--){
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) edge[i].clear(), tag[i][0] = tag[i][1] = 0, ans[i] = 0, oud[i] = 0;
for (int i = 2; i <= n; i++) {
scanf("%d%d", eu + i, ev + i);
edge[eu[i]].push_back({ev[i], i});
edge[ev[i]].push_back({eu[i], i});
}
hld::init();
int u, v;
while (q--) {
scanf("%d%d", &u, &v);
int x = hld::qlca(u, v);
// dbg(u, v, x);
tag[u][0] = max(dep[u] - dep[x], tag[u][0]);
tag[v][1] = max(dep[v] - dep[x], tag[v][1]);
}
// for (int i = 1; i <= n; i++) dbg(tag[i][0], tag[i][1]);
dfs(1, 0); dfs2(1, 0);
// for (int i = 1; i <= n; i++) assert(oud[i] <= 1);
for (int i = 2; i <= n; i++) {
if (ans[i] < 0) putchar('C');
else putchar('D');
}
puts("");
}
return 0;
}

D

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 1000000 + 5;

int n; char s[maxn];

int main(){
int T; scanf("%d", &T);
while (T--){
scanf("%s", s + 1); n = strlen(s + 1);
for (int i = 1; i < n; i++) {
if (s[i] == '.' && s[i + 1] == '.') putchar('C');
else putchar('D');
}
puts("");
}
return 0;
}

E

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 100000 + 5;

int a[10];

int main(){
int T; scanf("%d", &T);
while (T--){
double ans = 0;
ll sum = 0;
for (int i = 1, x; i <= 6; i++) {
scanf("%d", &x);
sum += x;
ans = max(1.0 * i * x, ans);
}
printf("%.12lf\n", ans / sum);
}
return 0;
}
  • 本文作者: XLor
  • 本文链接: https://xlor.cn/2019/1/eoj1/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!