[欧拉路]CF1152E Neko and Flashback
生活随笔
收集整理的這篇文章主要介紹了
[欧拉路]CF1152E Neko and Flashback
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
1152E - Neko and Flashback
題意:對于長為n的序列c和長為n - 1的排列p,我們可以按照如下方法得到長為n - 1的序列a,b,a',b'。
ai = min(ci, ci+1),bi = max(ci, ci+1)
a'i = ap[i],b'i = bp[i]。
現在給定a'和b',求一個合法的c或者無解。
解:仔細分析性質,發現在a和b中,c除了開頭和結尾會出現1次之外,每個數都會出現兩次,且相鄰。
我們可以把c的開頭找出來,然后根據開頭確定c2,然后確定c3...最后到cn。
注意到這些數可能有重復的,于是我們要試圖在中間插入一段。我一開始想的是鏈表后來發現很難寫...
仔細分析,如果把a'和b'的每個位置當成邊,數字當成點,就是求歐拉路。然后就沒了......
關于歐拉路:就暴力DFS,把每條邊都訪問一次。回溯的時候把這條邊入棧/把y入棧。
1 #include <bits/stdc++.h> 2 3 const int N = 200010; 4 5 struct Edge { 6 int nex, v, id, pre; 7 }edge[N << 1]; int tp = 1; 8 9 int X[N], xx, a[N], b[N], cnt[N], e[N], stk[N], top, deg[N]; 10 bool vis[N]; 11 12 inline void erase(int x, int i) { 13 int nex = edge[i].nex, pre = edge[i].pre; 14 if(e[x] == i && !nex) { 15 e[x] = 0; 16 } 17 else if(e[x] == i) { 18 e[x] = nex; 19 edge[nex].pre = 0; 20 return; 21 } 22 else if(!nex) { 23 edge[pre].nex = 0; 24 } 25 else { 26 edge[nex].pre = pre; 27 edge[pre].nex = nex; 28 } 29 edge[i].nex = edge[i].pre = 0; 30 return; 31 } 32 33 inline void add(int x, int y, int z) { 34 edge[++tp].v = y; 35 edge[tp].id = z; 36 edge[tp].nex = e[x]; 37 edge[e[x]].pre = tp; 38 e[x] = tp; 39 return; 40 } 41 42 void DFS(int x) { 43 for(int i = e[x]; i; i = edge[i].nex) { 44 erase(x, i); 45 int y = edge[i].v; 46 if(vis[edge[i].id]) { 47 continue; 48 } 49 vis[edge[i].id] = 1; 50 DFS(y); 51 stk[++top] = y; 52 } 53 return; 54 } 55 56 int main() { 57 58 int n; 59 scanf("%d", &n); 60 for(int i = 1; i < n; i++) { 61 scanf("%d", &a[i]); 62 X[++xx] = a[i]; 63 } 64 for(int j = 1; j < n; j++) { 65 scanf("%d", &b[j]); 66 X[++xx] = b[j]; 67 if(b[j] < a[j]) { 68 puts("-1"); 69 return 0; 70 } 71 } 72 73 std::sort(X + 1, X + xx + 1); 74 xx = std::unique(X + 1, X + xx + 1) - X - 1; 75 for(int i = 1; i < n; i++) { 76 a[i] = std::lower_bound(X + 1, X + xx + 1, a[i]) - X; 77 b[i] = std::lower_bound(X + 1, X + xx + 1, b[i]) - X; 78 add(a[i], b[i], i); 79 add(b[i], a[i], i); 80 deg[a[i]]++; 81 deg[b[i]]++; 82 } 83 int s = 0, pos = 1; 84 for(int i = 1; i <= xx; i++) { 85 if(deg[i] & 1) { 86 s++; 87 pos = i; 88 } 89 } 90 if(s != 0 && s != 2) { 91 puts("-1"); 92 return 0; 93 } 94 95 DFS(pos); 96 stk[++top] = pos; 97 if(top != n) { 98 puts("-1"); 99 return 0; 100 } 101 for(int i = top; i >= 1; i--) { 102 printf("%d ", X[stk[i]]); 103 } 104 105 return 0; 106 } AC代碼注意復雜度,刪邊......
1 #include <bits/stdc++.h> 2 3 const int N = 200010; 4 5 struct Edge { 6 int nex, v, id; 7 }edge[N << 1]; int tp = 1; 8 9 int X[N], xx, a[N], b[N], cnt[N], e[N], stk[N], top, deg[N]; 10 bool vis[N]; 11 12 inline void add(int x, int y, int z) { 13 edge[++tp].v = y; 14 edge[tp].id = z; 15 edge[tp].nex = e[x]; 16 e[x] = tp; 17 return; 18 } 19 20 void DFS(int x) { 21 for(int i = e[x]; i; i = e[x]) { 22 e[x] = edge[i].nex; 23 int y = edge[i].v; 24 if(vis[edge[i].id]) { 25 continue; 26 } 27 vis[edge[i].id] = 1; 28 DFS(y); 29 stk[++top] = y; 30 } 31 return; 32 } 33 34 int main() { 35 36 int n; 37 scanf("%d", &n); 38 for(int i = 1; i < n; i++) { 39 scanf("%d", &a[i]); 40 X[++xx] = a[i]; 41 } 42 for(int j = 1; j < n; j++) { 43 scanf("%d", &b[j]); 44 X[++xx] = b[j]; 45 if(b[j] < a[j]) { 46 puts("-1"); 47 return 0; 48 } 49 } 50 51 std::sort(X + 1, X + xx + 1); 52 xx = std::unique(X + 1, X + xx + 1) - X - 1; 53 for(int i = 1; i < n; i++) { 54 a[i] = std::lower_bound(X + 1, X + xx + 1, a[i]) - X; 55 b[i] = std::lower_bound(X + 1, X + xx + 1, b[i]) - X; 56 add(a[i], b[i], i); 57 add(b[i], a[i], i); 58 deg[a[i]]++; 59 deg[b[i]]++; 60 } 61 int s = 0, pos = 1; 62 for(int i = 1; i <= xx; i++) { 63 if(deg[i] & 1) { 64 s++; 65 pos = i; 66 } 67 } 68 if(s != 0 && s != 2) { 69 puts("-1"); 70 return 0; 71 } 72 73 DFS(pos); 74 stk[++top] = pos; 75 if(top != n) { 76 puts("-1"); 77 return 0; 78 } 79 for(int i = top; i >= 1; i--) { 80 printf("%d ", X[stk[i]]); 81 } 82 83 return 0; 84 } 另一種刪邊方式?
轉載于:https://www.cnblogs.com/huyufeifei/p/10958711.html
總結
以上是生活随笔為你收集整理的[欧拉路]CF1152E Neko and Flashback的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 最后一个社团换届的感谢和感悟
- 下一篇: 如何创建企业微信应用