題目鏈接

題意

給一個(gè)長(zhǎng)度為$M$的序列，問(wèn)它是否能作為給定的一棵樹(shù)的dfs序的一部分

思路

比賽的時(shí)候和隊(duì)友在寫(xiě)假算法，本來(lái)以為會(huì)$TLE$或者$MLE$，但是一直$WA$。
回來(lái)問(wèn)了學(xué)長(zhǎng)才過(guò)的。
按照給定序列的順序從下到上打上同一個(gè)標(biāo)記，遇到打過(guò)標(biāo)記的點(diǎn)就$return$，然后按照標(biāo)記從小到大$dfs$得到一個(gè)$dfs$序，最后查找序列是否出現(xiàn)在$dfs$序列里面。
因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$dfs$結(jié)束之后才加入隊(duì)列，所以序列前面的節(jié)點(diǎn)最先訪問(wèn)，這是就給他打上一個(gè)小的標(biāo)記，這樣只要序列正確，一定會(huì)出現(xiàn)在$dfs$序中

#include <bits/stdc++.h> #define LL long long #define P pair<int, int> #define lowbit(x) (x & -x) #define mem(a, b) memset(a, b, sizeof(a)) #define mid ((l + r) >> 1) #define lc rt<<1 #define rc rt<<1|1 using namespace std; const int maxn = 1e6 + 1;vector<int> g[maxn], num; int fa[maxn], sign[maxn], now; void dfs(int x) {for (int it : g[x]) {dfs(it);}num.push_back(x); }bool cmp(int x, int y) {return sign[x] < sign[y]; }int main () {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T;scanf("%d", &T);while (T--) { int n, m; scanf("%d%d", &n, &m);vector<int> list(m);now = 0;for (int i = 1; i <= n; ++i) sign[i] = 0, g[i].clear();for (int i = 2, x; i <= n; ++i) {scanf("%d", &x);g[x].push_back(i);fa[i] = x;}for (int i = 0; i < m; ++i) {scanf("%d", &list[i]);now = i+1;int tmp = list[i];while (sign[tmp] == 0) {sign[tmp] = now;tmp = fa[tmp];if (tmp == 0) break;}}for (int i = 1; i <= n; ++i) {sort(g[i].begin(), g[i].end(), cmp);}num.clear();dfs(1);int flag = 1;int j = 0;for (int i = 0; i < n; ++i) {if (num[i] == list[j]) j++;if (j == m) break;}if (j != m) flag = 0;puts(flag ? "NOT BAD":"BAD GUGU");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的zzuli 2525: 咕咕的搜索序列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。