Fork me on GitHub

复赛冲刺Day1R1-Color题解

这道题是考试时的$T2$,我感觉这道题出的特别好(虽然当时并不会做

首先看题目:$emmmmm…..$
什么鬼啊这个题是$QAQ$

当时直接一脸懵逼,然后只会写2^n 枚举每一种填充方式,然后再检测的方法…
然而这道题这么做只有10分啊$qaq….$

然后赛后题解告诉我:这题TM是个欧拉回路!!!!
当时我就懵逼了….
然后当dalao们给我把这道题讲明白了之后,我才发现这道题思路的奇妙

首先,我们发现,对于一个点,它对应着一个横坐标和一个纵坐标。
蒽….一个点对应着两个数值,这个时候我们应该想到什么?
二分图?
对了,这东西还真的就是要你用二分图的思想来建图….(心态崩了我要妹子$QAQ$)

我们建图,然后我们发现,因为一个点对应着一个横坐标和一个纵坐标,那么我们想到:
在二分图中,每一条边也是对应着两种点。那么受到这样的启发,我们就可以建图了:
我们把横坐标和纵坐标分别看成一种点,然后将题目中给你的点看成这张图上的边,
那么因为题目中要求:黑点和白点的绝对值差不大于1…..,那么我们能想到什么呢?
我们要对这些边进行黑白染色,所以我们要一个点出发,一直走一条欧拉回路,这样能走遍所有的边。

但是这样做,我们会发现一个问题:只有$subtask4$的$30$分数据告诉你是偶数。而存在欧拉回路的图的特点是什么呢?
每个点的度数都是偶数,那么当点的度数是奇数的时候,我们怎么办呢?

我在这里选择了度数为奇数的点向一个虚拟节点连边,然后当所有点的度数都是偶数时,这时候没有其他点向这个点连边
所以这时候这个虚拟节点对答案没有影响。

然后,我们就直接对边进行染色就可以了。

我只想说,这道题出的真的好,佩服出题人。

代码:

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

const int N = 5e5 + 10;

struct Data {
int v;
int p;
}data[N];
struct Edge {
int to;
int next;
}e[N << 1];
int n , m , t = 1 , num;
int head[N] , d[N];
int x[N] , y[N] , ans[N];
bool flag[N];

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}
inline void add ( int x , int y ) {
e[++t].to = y;
e[t].next = head[x];
head[x] = t;
return;
}
inline bool cmp ( Data x , Data y ) {
return x.v<y.v;
}
void lisanhua () {
for ( int i = 1 ; i <= n ; i++ ) {
data[i].v = x[i];
data[i].p = i;
}
std :: sort ( data + 1 , data + 1 + n , cmp );
data[0].v = -1;
for ( int i = 1 ; i <= n ; i++ ) {
if ( data[i].v != data[i - 1].v )
num++;
x[data[i].p] = num;
}
for ( int i = 1 ; i <= n ; i++ ) {
data[i].v = y[i];
data[i].p = i;
}
std :: sort ( data + 1 , data + 1 + n , cmp );
data[0].v = -1;
for ( int i = 1 ; i <= n ; i++ ) {
if ( data[i].v != data[i - 1].v )
num++;
y[data[i].p] = num;
}
return;
}
void dfs ( int cur , bool last ) {
for ( int i = head[cur] ; i ; i = e[i].next ) {
if ( flag[i >> 1] )
continue;
int j = e[i].to;
flag[i >> 1] = 1;
d[cur]--;
d[j]--;
ans[i >> 1] = !last;
dfs ( j , !last );
}
return;
}

int main ( void ) {
n = read ();
for ( int i = 1 ; i <= n ; i++ ) {
x[i] = read ();
y[i] = read ();
}
lisanhua();
for ( int i = 1 ; i <= n ; i++ ) {
d[x[i]]++;
d[y[i]]++;
add ( x[i] , y[i] );
add ( y[i] , x[i] );
}
for ( int i = 1 ; i <= num ; i++ )
if ( d[i] & 1 ) {
d[i]++;
d[num + 1]++;
add ( i , num + 1 );
add ( num + 1 , i );
}
num++;
memset ( ans , -1 , sizeof ( ans ) );
for ( int i = 1 ; i <= num ; i++ )
while ( d[i] )
dfs ( i , 1 );
for ( int i = 1 ; i <= n ; i++ )
printf ( "%d%c" , ans[i] , i == n ? '\n' : ' ' );
return 0;
}

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:复赛冲刺Day1R1-Color题解

文章作者:KRrrrrrrrr

发布时间:2018年11月01日 - 19:11

最后更新:2019年10月21日 - 11:10

原始链接:http://krrrr.xyz/2018/11/01/复赛冲刺Day1R1-Colory题解/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。