title: UVa 124
date: 2021-04-27 14:00:38
categories:
- UVa
mathjax: true
tags:
- UVa
- DFS
UVa 124
題目
http://domen111.github.io/UVa-Easy-Viewer/?124
給你幾個不重複的小寫英文字母，告訴你某些字母之間的大小關係，把所有從小到大的排列列出來
如果沒有告知某個元素的大小關係，那可以任意擺放
想法1
我們可以紀錄兩個元素之間的關係，兩兩元素間的關係可以分成 a<b a>b 未定義 三種
只要當前枚舉的元素跟前面的元素彼此之間不衝突，也就是說並不是 a>b 的狀態就可以枚舉下去
因為要找出所有情況，所以枚舉方式是採用 DFS
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
| #include<iostream>
#include<sstream>
using namespace std;
int var_nums, tbl[26];
int less_than[26][26];
string vars, cons;
char v, x, y, res[26];
bool out=false, used_vars[26];
void DFS(int depth){
if(depth == var_nums){
for(int i=0 ; i<depth ; i++){
cout<<res[i];
}
cout<<"\n";
return;
}
for(int i=0 ; i<26 ; i++){
if(tbl[i]){
bool less=true;
for(int j=0 ; j<depth ; j++){
if(less_than[res[j]-'a'][i]==2){
less=false;
}
}
if(less){
res[depth] = i+'a';
DFS(depth+1);
}
}
}
}
int main(){
while(getline(cin, vars)){
if(out) cout<<'\n';
else out=true;
var_nums=0;
for(int i=0 ; i<26 ; i++){
tbl[i] = 0;
used_vars[i] = false;
for(int j=0 ; j<26 ; j++){
less_than[i][j] = 2;
}
}
stringstream ss;
ss<<vars;
while(ss>>v){
tbl[v-'a']++;
var_nums++;
used_vars[v-'a'] = true;
}
for(int i=0 ; i<26 ; i++){
if(!tbl[i]) continue;
for(int j=0 ; j<26 ; j++){
if(!tbl[j]) continue;
if(i != j)
less_than[i][j] = 0;
}
}
getline(cin, cons);
ss.str("");
ss.clear();
ss<<cons;
while(ss>>x>>y){
less_than[x-'a'][y-'a'] = 1;
less_than[y-'a'][x-'a'] = 2;
}
DFS(0);
}
return 0;
}
|
想法2
既然題目給的是兩兩之間的關係，那麼就可以想到用一個圖來表示
例如題目的第一筆測資
那麼該怎麼枚舉呢?隨便選一個點走下去嗎?
從上圖可以發現到，因為 $G$ 跟其他點的大小關係是未定義的，所以我們永遠走不到它，所以要換個想法
如果當前連到點 $x$ 的線數量是 $0$ ，就表示我們可以選擇這個點
在選擇 $x$ 之後，我們需要把 $x$ 以及 $x$ 所能連接到的所有點的邊砍斷
如此一來，與 $x$ 相連的所有點在下一次都是可以枚舉的點了!
並且我們不會忽略那些未定義的點
這個方法被稱為拓樸排序，也會用到 DFS 的概念
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
|
#include<iostream>
#include<sstream>
using namespace std;
string vars, cons;
char v, x, y, res[26];
bool out=false, nxt[26][26];
int var_nums, tbl[26], in[26];
void DFS(int depth){
if(depth == var_nums){
for(int i=0 ; i<depth ; i++){
cout<<res[i];
}
cout<<"\n";
return;
}
for(int i=0 ; i<26 ; i++){
if(tbl[i] && in[i]==0){
res[depth] = i+'a';
in[i]--;
for(int j=0 ; j<26 ; j++){
if(tbl[j] && nxt[i][j]){
in[j]--;
}
}
DFS(depth+1);
in[i]++;
for(int j=0 ; j<26 ; j++){
if(tbl[j] && nxt[i][j]){
in[j]++;
}
}
}
}
}
int main(){
while(getline(cin, vars)){
if(out) cout<<"\n";
else out=true;
var_nums=0;
for(int i=0 ; i<26 ; i++){
tbl[i] = in[i] = 0;
for(int j=0 ; j<26 ; j++){
nxt[i][j] = false;
}
}
stringstream ss;
ss<<vars;
while(ss>>v){
tbl[v-'a']=1;
var_nums++;
}
getline(cin, cons);
ss.str("");ss.clear();
ss<<cons;
while(ss>>x>>y){
in[y-'a']++;
nxt[x-'a'][y-'a'] = true;
}
DFS(0);
}
return 0;
}
|
想法3
前面有用 DFS 以及 拓樸排序 的方式寫過這題，現在用位元運算的角度來看
我們可以用數字的 bit 去紀錄字元 $a$ 是否小於字元 $b$
例如說 $b < a$ ，那麼就在記錄 $b$ 小於的數字 $m$ 中第 $0$ (a-a = 0) 個 bit 紀錄 $1$
接下來當我們透過 DFS 枚舉的過程時，把當前有用到的字元都記錄在一個數字的相對應 bit 上
要判斷某個字元能否放上去，就只需要判斷出現過的字元是否都符合小於的條件即可
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
|
#include<iostream>
#include<sstream>
using namespace std;
string s;
int vars, var_num, Less[30];
char x, y, res[30];
bool out=false;
void DFS(int depth, int used){
if(depth == var_num){
for(int i=0 ; i<var_num ; i++){
cout<<res[i];
}
cout<<"\n";
return;
}
for(int i=0, now ; i<26 ; i++){
now = (1<<i);
if((vars & now) != 0 && (used & now) == 0 && (Less[i] & used) == 0){
res[depth] = 'a'+i;
DFS(depth+1, used|now);
}
}
}
int main(){
while(getline(cin, s)){
if(out) cout<<"\n";
else out=true;
vars = var_num = 0;
for(int i=0 ; i<30 ; i++){
Less[i] = 0;
}
stringstream ss;
ss<<s;
while(ss>>x){
vars |= (1<<(x-'a'));
var_num++;
}
getline(cin, s);
ss.str("");
ss.clear();
ss<<s;
while(ss>>x>>y){
Less[x-'a'] |= (1<<(y-'a'));
}
DFS(0, 0);
}
return 0;
}
|