CF ER#108 E

CF ER#108 E

E.Off by One

Solution

首先, 由题意可以知道答案不会超过 $\lceil n/2 \rceil$; 接着, 可以利用建图的方法进行抽象然后构造证明答案就是 $\lceil n/2 \rceil$.

注意到每个点只能到达另外两个新的点, 所以把点看成图上的边, 新到达的点看成图上的点. 这样图中边数和点数都是 $O(n)$ 的(所以其实答案 $\lceil n/2 \rceil$ 是对于每个联通块而言的) . 那么问题转换为可以删多少次有公共点的两条边.

然后, 用下面的方法进行构造:

首先建立一棵生成树, 从根开始向下dfs. 对于一个结点, 先搜索其子结点, 子结点往下搜索走出若干条欧拉路径(回路), 而如果经历了偶数条边, 那么可以将其刚好一分为二, 如其不然, 则将当前与子结点相连的边加入其中使其边数变为偶数, 则可以走完. 这么处理之后, 当前点会剩下一些边(需要注意的是, 这里返祖边应当考虑在内), 如果这些边数量为偶数, 那么可以两两配对走完, 如果是奇数, 说明当前结点最终经过了奇数条边, 需要父亲节点提供一条边作为辅助.

时间复杂度: $O(n+n\log {M})$.

Code

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
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
// #define debug

using namespace std;

struct Edge {
int to, nxt, idx;
};

const int MAX_N = 2e5 + 7;
Edge e[MAX_N << 1];
map<pii, int> mp;
vector<pii> ans;
int head[MAX_N << 1], dfn[MAX_N << 1];
bool vis[MAX_N];
int n, tot, cnt, ord;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

void add(int u, int v, int idx) {
e[++cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt; e[cnt].idx = idx;
}

int dfs(int u, int fa) {
dfn[u] = ++ord;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (!dfn[v]) {
int res = dfs(v, u);
if (res) {
ans.push_back(pii(res, e[i].idx));
vis[res] = vis[e[i].idx] = true;
}
}
}
int lst = 0;
for (int i = head[u]; i; i = e[i].nxt) {
if (vis[e[i].idx] || e[i].to == fa) continue;
if (lst) {
ans.push_back(pii(lst, e[i].idx));
vis[e[i].idx]= vis[lst] = true;
lst = 0;
} else {
lst = e[i].idx;
}
}
return lst;
}

signed main() {
#ifndef debug
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
int a, b, c, d;
scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
int up = c * b, dn = d * (a + b);
int _gcd = gcd(up, dn);
pii u1(up / _gcd, dn / _gcd);
up = (c + d) * b, dn = a * d;
_gcd = gcd(up, dn);
pii u2(up / _gcd, dn / _gcd);
if (!mp.count(u1)) {
++tot;
mp[u1] = tot;
}
if (!mp.count(u2)) {
++tot;
mp[u2] = tot;
}
int u = mp[u1], v = mp[u2];
add(u, v, i), add(v, u, i);
}
#endif
printf("%lld\n", ans.size());
for (auto p : ans) {
printf("%lld %lld\n", p.first, p.second);
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×