原題目鏈接

1011 NTA

NTA（非確定性樹自動機(jī)）是一種樹形結(jié)構(gòu)裝置，該裝置內(nèi)置有一套運(yùn)行規(guī)則，通過這些規(guī)則，裝置可以產(chǎn)生若干個(gè)信號，這些信號組成一個(gè)信號系統(tǒng)，在這樣的系統(tǒng)中，一個(gè)信號為起始信號，若干個(gè)信號為可接受信號，其余信號為輔助信號。如果一對信號中的兩個(gè)信號都是可接受的，則稱該對信號為可接受對。

這里討論的樹都是二叉樹，每個(gè)非葉子節(jié)點(diǎn)都有兩個(gè)后繼。在任何一棵有限樹中，每個(gè)節(jié)點(diǎn)都有一個(gè)信號傳遞元素。當(dāng)信號到達(dá)一個(gè)節(jié)點(diǎn)時(shí)，信號遇到信號傳遞物質(zhì)，引發(fā)信號反應(yīng)，產(chǎn)生多對信號。然后設(shè)備非確定性地選擇一對信號發(fā)送給它的后繼。信號對中的第一個(gè)信號發(fā)送給左邊的后繼節(jié)點(diǎn)，第二個(gè)信號發(fā)送給右邊的后繼節(jié)點(diǎn)。

NTA 的整個(gè)操作如下：

該裝置首先向根節(jié)點(diǎn)發(fā)出起始信號，根據(jù)根節(jié)點(diǎn)的信號傳輸物質(zhì)，非確定性地選擇一對信號，將第一對信號發(fā)送給左子樹，將第二對信號發(fā)送給右子樹，然后兩對信號分別在相應(yīng)的節(jié)點(diǎn)遇到信號傳輸物質(zhì)，產(chǎn)生另外兩對信號，如此循環(huán)往復(fù)，直至到達(dá)葉子節(jié)點(diǎn)。

如果信號到達(dá)一個(gè)葉子，并且該葉子能夠產(chǎn)生一對可接受的信號，我們就說該葉子是“可搖動的”。如果所有葉子都是“可搖動的”，則從根到葉子的信號傳輸被認(rèn)為是有效的。如果存在這樣的有效傳輸，則具有信號傳輸物質(zhì)的樹結(jié)構(gòu)是有效的。如果所有傳輸都是無效的，則樹是無效的。

為簡單起見，我們用連續(xù)的小寫字母“a”、“b”、“c”等表示信號傳輸元件。NTA 的信號是連續(xù)的數(shù)字 0、1、2、… 等等。第一個(gè)信號 0 始終是起始信號。因此，4 信號 NTA 的信號為“0”、“1”、“2”和“3”。接受信號排列在數(shù)字序列的末尾，因此，如果 4 信號 NTA 有兩個(gè)接受信號，則接受信號為“2”和“3”。信號的轉(zhuǎn)換規(guī)則基于轉(zhuǎn)換表。例如，下表描述了具有四個(gè)信號“0”、“1”、“2”、“3”和三個(gè)信號傳輸元件“a”、“b”和“c”的轉(zhuǎn)換表。

T	a	b	c
0	(1,2)	(2,1)	(1,0)
1	(2,2)	(0,2),(1,0)	(3,2)
2	(2,2)	(2,3)	(1,2)
3	(1,2)	(2,1)	(3,2)

在這個(gè)轉(zhuǎn)換表中，信號對某些信號傳輸元件的反應(yīng)是確定性的，而其他反應(yīng)則是非確定性的。在上面的例子中，如果信號“1”到達(dá)具有傳輸元件“b”的節(jié)點(diǎn)，則反應(yīng)是非確定性的。

現(xiàn)在你的任務(wù)是編寫一個(gè)程序來判斷含有某種信號傳遞物質(zhì)的樹結(jié)構(gòu)是否有效。

輸入

輸入文件包含幾個(gè)案例。每個(gè)案例都描述了一系列 NTA 描述和一些初始樹配置。每個(gè)案例的第一行由三個(gè)整數(shù) n、m 和 k 組成。整數(shù) n 表示信號的數(shù)量，m 表示接受信號的數(shù)量，k 表示信號傳輸元件的數(shù)量。接下來的 nk 行按行主序描述轉(zhuǎn)換表。信號到信號傳輸元件的每個(gè)轉(zhuǎn)換都在單獨(dú)的一行中給出。在這樣的行上，每兩個(gè)數(shù)字代表一個(gè)可能的轉(zhuǎn)換。

接下來是樹結(jié)構(gòu)的描述。對于每個(gè)樹結(jié)構(gòu)，在單獨(dú)的一行中給出一個(gè)數(shù)字 L，以指示樹的級別。接下來的 L+1 行包含字母序列，描述樹結(jié)構(gòu)。每行描述一個(gè)級別。兩個(gè)連續(xù)字母之間存在一個(gè)空格。第 0 級首先開始。在樹結(jié)構(gòu)中，空節(jié)點(diǎn)用“*”標(biāo)記。L=-1 的樹結(jié)構(gòu)終止該 NTA 的樹結(jié)構(gòu)配置，不應(yīng)判斷此結(jié)構(gòu)。

輸入以 n=0、m=0 和 k=0 開頭的描述結(jié)束。不應(yīng)處理此描述。

注意：在每種情況下，NTA 最多有 l5 個(gè)信號和 10 個(gè)字符。每棵樹的級別不超過 10。

輸出

對于每個(gè) NTA 描述，打印 NTA 編號（NTA1、NTA2 等），后跟冒號。然后對于 NTA 的每個(gè)初始樹配置，打印單詞“有效”或“無效”。

在 NTA 案例之間打印空白行。

示例輸入

4 2 3
1 2
2 1
1 0
2 2
0 2 1 0
3 2
2 2
2 3
1 2
1 2
2 1
3 2
3
a
b c
a b c b
b a b a c a * *
2
b
a b
b c * *
-1
0 0 0

樣本輸入的輸出

NTA1:
Valid
Invalid

c++代碼

#include<bits/stdc++.h>using namespace std;class tree{
public:char val;int code;tree* left;tree* right;tree(char val){this->val = val;this->code = -1;this->left = NULL;this->right = NULL;}
};bool dfs(tree* root, vector<vector<vector<int>>>& trans, int* left, int* right){vector<int> middle = trans[root->code][root->val - 'a'];if (root->left == NULL && root->right == NULL){for (int i = 0; i < middle.size(); i += 2){if (middle[i] >= * left && middle[i] <= *right&& middle[i + 1] >= * left && middle[i + 1] <= * right) return true;}return false;}for (int i = 0; i < middle.size(); i += 2){root->left->code = middle[i];root->right->code = middle[i + 1];bool key1 = false, key2 = false;key1 = dfs(root->left, trans, left, right);if (key1) key2 = dfs(root->right, trans, left, right);if (key1 && key2) return true;}return false;
}int main(){int n, m, k, L, count = 0;while(cin >> n >> m >> k){getchar();count++;if (n == 0 && m == 0 && k == 0) break;vector<vector<vector<int>>> trans(n, vector<vector<int>>(k));for (int i = 0; i < n; i++){for (int j = 0; j < k; j++){while(true){char a = (char)getchar();if (a == '\n') break;if (a == ' ') continue;trans[i][j].push_back(a - '0');}}}if (count != 1) cout << endl;cout << "NTA" << count << ":" << endl;while(cin >> L){getchar();if (L == -1) break;vector<vector<tree*>> roots(L + 1);for (int i = 0; i < L + 1; i++){while(true){char a = (char)getchar();if (a == '\n') break;if (a == ' ') continue;if (a == '*') roots[i].push_back(NULL);else roots[i].push_back(new tree(a));}}for (int i = 0; i < L + 1; i++){int z = roots[i].size();for (int j = 0; j < z; j++){if (i != L && roots[i][j] != NULL){roots[i][j]->left = roots[i + 1][2 * j];roots[i][j]->right = roots[i + 1][2 * j + 1];}}}roots[0][0]->code = 0;int right = n - 1;int left = n - m;if (dfs(roots[0][0], trans, &left , &right)) cout << "Valid" << endl;else cout << "Invalid" << endl;}}return 0;
}//by wqs

題目解析

題目涉及一個(gè)名為 NTA（非確定性樹自動機(jī)）的設(shè)備，該設(shè)備基于一組轉(zhuǎn)換規(guī)則將信號傳遞下去，最終判斷樹結(jié)構(gòu)是否有效。具體來說，設(shè)備根據(jù)信號傳遞規(guī)則，向二叉樹的各個(gè)節(jié)點(diǎn)傳遞信號，信號傳遞的有效性取決于每個(gè)葉子節(jié)點(diǎn)是否能夠接受一對“有效的信號對”。

樹是一個(gè)二叉樹，每個(gè)非葉子節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)。信號傳遞過程中，從根節(jié)點(diǎn)開始傳遞信號，根節(jié)點(diǎn)通過轉(zhuǎn)換規(guī)則將信號分發(fā)到兩個(gè)子節(jié)點(diǎn)。這個(gè)過程會一直遞歸到葉子節(jié)點(diǎn)。

轉(zhuǎn)移規(guī)則可以是確定性的（一個(gè)信號只能產(chǎn)生一個(gè)新的信號對），也可以是非確定性的（一個(gè)信號可以產(chǎn)生多個(gè)不同的信號對）。

當(dāng)信號到達(dá)葉子節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)被認(rèn)為是“可搖動”的，只有當(dāng)該節(jié)點(diǎn)能產(chǎn)生一個(gè)有效的信號對（兩個(gè)信號都為接受信號時(shí)），才認(rèn)為該葉子節(jié)點(diǎn)是可搖動的。

如果從根節(jié)點(diǎn)到所有葉子節(jié)點(diǎn)的信號傳遞都能滿足每個(gè)葉子節(jié)點(diǎn)的可搖動條件（即每個(gè)葉子節(jié)點(diǎn)的信號對都為接受信號對），則該樹結(jié)構(gòu)是有效的。

否則該樹結(jié)構(gòu)為無效。

樣例理解

實(shí)現(xiàn)思路

1、獲得轉(zhuǎn)移表

vector<vector<vector<int>>> trans(n, vector<vector<int>>(k));//轉(zhuǎn)移表初始化for (int i = 0; i < n; i++){for (int j = 0; j < k; j++){while(true){char a = (char)getchar();if (a == '\n') break;if (a == ' ') continue;trans[i][j].push_back(a - '0');//獲得轉(zhuǎn)移表}}
}

2、創(chuàng)建層序遍歷樹形數(shù)組

輸入是按層輸入的，根據(jù)這個(gè)特點(diǎn)可以得出層序遍歷樹形數(shù)組

vector<vector<tree*>> roots(L + 1); //初始化，roots[0]表示第一層結(jié)點(diǎn),roots[1]表示第二層結(jié)點(diǎn)，以此類推for (int i = 0; i < L + 1; i++){while(true){char a = (char)getchar();if (a == '\n') break;if (a == ' ') continue;if (a == '*') roots[i].push_back(NULL);else roots[i].push_back(new tree(a));}
}

3、根據(jù)層序遍歷樹形數(shù)組創(chuàng)建樹形結(jié)構(gòu)

for (int i = 0; i < L + 1; i++){int z = roots[i].size();for (int j = 0; j < z; j++){if (i != L && roots[i][j] != NULL){roots[i][j]->left = roots[i + 1][2 * j];roots[i][j]->right = roots[i + 1][2 * j + 1];}}
}//roots[i][j]的左孩子是roots[i + 1][2 * j]，右孩子是roots[i + 1][2 * j + 1]
//這樣roots[0][0]就是我們的根節(jié)點(diǎn)，已經(jīng)創(chuàng)建好了

4、深度優(yōu)先搜索

bool dfs(tree* root, vector<vector<vector<int>>>& trans, int* left, int* right){//root當(dāng)前根節(jié)點(diǎn),trans轉(zhuǎn)換表,left,right有效信號的區(qū)間范圍vector<int> middle = trans[root->code][root->val - 'a'];if (root->left == NULL && root->right == NULL){//葉子結(jié)點(diǎn)for (int i = 0; i < middle.size(); i += 2){if (middle[i] >= * left && middle[i] <= *right&& middle[i + 1] >= * left && middle[i + 1] <= * right) return true;//只要有一對有效的就是可搖動}return false;//沒有一對有效的信號，足以說明此條路，樹是無效的}for (int i = 0; i < middle.size(); i += 2){root->left->code = middle[i];root->right->code = middle[i + 1];bool key1 = false, key2 = false;key1 = dfs(root->left, trans, left, right);//判斷左子樹是否有效if (key1) key2 = dfs(root->right, trans, left, right);//判斷右子樹是否有效if (key1 && key2) return true;//左子樹有效并且右子樹有效則這棵樹有效}return false;//所有的路這棵樹都無效，可以得出這棵樹無效
}