Fork me on GitHub

[POJ2284]That Nice Euler Circuit

传送门

思路

首先我们想到的就是直接开二维数组模拟然后$bfs$统计答案.但是这样的话时间复杂度是不行的,所以我们需要考虑其他方法.
我们考虑到欧拉公式,即$E=V+F-2$.在这里$E$为边数,$V$为点数,$F$为面的个数.
本来这个欧拉公式是求三维的情况的,但是发现二维的情况也适用,所以我把它称为木大公式.
可以直接开$map$统计点和边的个数,然后试用欧拉公式进行计算即可. (注意特判刚开始$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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10;

int NodeNum , EdgeNum;
char s[N];
struct kuai {
int x , y;
};
bool operator < ( kuai x , kuai y ) {
if ( x.x == y.x )
return x.y < y.y;
return x.x < y.x;
};
map < kuai , bool > Node;
map < pair < kuai , kuai > , bool > Edge;

int main ( void ) {

scanf ( "%s" , s + 1 );
int n = strlen ( s + 1 );
int xx = 0 , yy = 0;
Node[ kuai { 0 , 0 } ] = 1;
NodeNum = 1;
for ( int i = 1 ; i <= n ; i++ ) {
int lx = xx , ly = yy;
if ( s[i] == 'L' )
xx--;
else if ( s[i] == 'R' )
xx++;
else if ( s[i] == 'U' )
yy++;
else if ( s[i] == 'D' )
yy--;
if ( !Node[ kuai { xx , yy } ] ) {
Node[ kuai { xx , yy } ] = 1;
NodeNum++;
}
if ( !Edge[ make_pair ( kuai { lx , ly } , kuai { xx , yy } ) ] && !Edge[ make_pair ( kuai { xx , yy } , kuai { lx , ly } ) ] ) {
Edge[ make_pair ( kuai { xx , yy } , kuai { lx , ly } ) ] = 1;
Edge[ make_pair ( kuai { lx , ly } , kuai { xx , yy } ) ] = 1;
EdgeNum++;
}
// printf ( "step:%d , from(%d,%d) -> to(%d,%d)\n" , i , lx , ly , xx , yy );
}
// printf ( "%d %d\n" , EdgeNum , NodeNum );
printf ( "%d\n" , EdgeNum - NodeNum + 2 );
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:[POJ2284]That Nice Euler Circuit

文章作者:KRrrrrrrrr

发布时间:2019年10月28日 - 20:10

最后更新:2019年10月28日 - 20:10

原始链接:http://krrrr.xyz/2019/10/28/POJ2284-ThatNiceEulerCircuit/

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