CF508D Tanya and Password(欧拉路径)

题目链接

CF

题意简述

有一个字符串 $S[1..n+2]$,告诉你 $\forall 1\le i\le n, S[i..i+2]$(所有长为 $3$ 的子串),求任意一个满足条件的 $S$。

$1\le n\le 2\cdot 10^5$,字符集为大小写字母 + 数字。

简要做法

容易想到需要建图。

但是,如果把每个长为 $3$ 的子串看成点,前后缀匹配看成边,就做不下去了。

正确做法是把每个长为 $2$ 的子串看成点,长为 $3$ 的子串看成边。这样原问题就转化成了求有向图的欧拉路径。(不会这个的话建议自行搜索一下。)

如果每次 dfs 同一个点时都遍历所有出边,度数比较大就会挂。使用 vector 存边的话可以 pop_back() 或者记录一下已经遍历到了哪一条边,使用前向星的话可以像当前弧优化那样修改 head

参考代码

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
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstdlib>

using namespace std;

const int N = 200010;
const int W = 62 * 62;

int head[N], nxt[N], to[N], cnt;
int n, ind[N], outd[N], tot;
char s[N], ans[N];

int charToInt(char x)
{
if (isdigit(x)) return x - '0';
if (islower(x)) return x - 'a' + 10;
return x - 'A' + 36;
}

char intToChar(int x)
{
if (x < 10) return x + '0';
if (x < 36) return x - 10 + 'a';
return x - 36 + 'A';
}

int wordToInt(char x, char y)
{
return charToInt(x) * 62 + charToInt(y);
}

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

void fail()
{
puts("NO");
exit(0);
}

void dfs(int u)
{
for (int& i = head[u]; i; )
{
int v = to[i];
i = nxt[i];
dfs(v);
}
ans[--tot] = intToChar(u % 62);
}

int main()
{
scanf("%d", &n);

for (int i = 1; i <= n; ++i)
{
scanf("%s", s);
int u = wordToInt(s[0], s[1]);
int v = wordToInt(s[1], s[2]);
++outd[u];
++ind[v];
add(u, v);
}

int oneMoreIn = 0, oneMoreOut = 0;

for (int i = 0; i < W; ++i)
{
if (ind[i] == outd[i]) continue;
if (ind[i] == outd[i] + 1)
{
if (oneMoreIn) fail();
oneMoreIn = i;
}
else if (ind[i] + 1 == outd[i])
{
if (oneMoreOut) fail();
oneMoreOut = i;
}
else fail();
}

if (!oneMoreOut)
{
for (int i = 0; i < W; ++i)
{
if (outd[i])
{
oneMoreOut = i;
break;
}
}
}

tot = n + 2;
dfs(oneMoreOut);
ans[--tot] = intToChar(oneMoreOut / 62);

if (!tot) printf("YES\n%s", ans);
else puts("NO");

return 0;
}