武昌手机网站,wordpress页脚页眉插件,企业网站建设实战教程,兰州网站开发企业原题目链接
1011 NTA
NTA#xff08;非确定性树自动机#xff09;是一种树形结构装置#xff0c;该装置内置有一套运行规则#xff0c;通过这些规则#xff0c;装置可以产生若干个信号#xff0c;这些信号组成一个信号系统#xff0c;在这样的系统中#xff0c;一个信…原题目链接
1011 NTA
NTA非确定性树自动机是一种树形结构装置该装置内置有一套运行规则通过这些规则装置可以产生若干个信号这些信号组成一个信号系统在这样的系统中一个信号为起始信号若干个信号为可接受信号其余信号为辅助信号。如果一对信号中的两个信号都是可接受的则称该对信号为可接受对。
这里讨论的树都是二叉树每个非叶子节点都有两个后继。在任何一棵有限树中每个节点都有一个信号传递元素。当信号到达一个节点时信号遇到信号传递物质引发信号反应产生多对信号。然后设备非确定性地选择一对信号发送给它的后继。信号对中的第一个信号发送给左边的后继节点第二个信号发送给右边的后继节点。
NTA 的整个操作如下
该装置首先向根节点发出起始信号根据根节点的信号传输物质非确定性地选择一对信号将第一对信号发送给左子树将第二对信号发送给右子树然后两对信号分别在相应的节点遇到信号传输物质产生另外两对信号如此循环往复直至到达叶子节点。
如果信号到达一个叶子并且该叶子能够产生一对可接受的信号我们就说该叶子是“可摇动的”。如果所有叶子都是“可摇动的”则从根到叶子的信号传输被认为是有效的。如果存在这样的有效传输则具有信号传输物质的树结构是有效的。如果所有传输都是无效的则树是无效的。
为简单起见我们用连续的小写字母“a”、“b”、“c”等表示信号传输元件。NTA 的信号是连续的数字 0、1、2、… 等等。第一个信号 0 始终是起始信号。因此4 信号 NTA 的信号为“0”、“1”、“2”和“3”。接受信号排列在数字序列的末尾因此如果 4 信号 NTA 有两个接受信号则接受信号为“2”和“3”。信号的转换规则基于转换表。例如下表描述了具有四个信号“0”、“1”、“2”、“3”和三个信号传输元件“a”、“b”和“c”的转换表。
Tabc0(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)
在这个转换表中信号对某些信号传输元件的反应是确定性的而其他反应则是非确定性的。在上面的例子中如果信号“1”到达具有传输元件“b”的节点则反应是非确定性的。
现在你的任务是编写一个程序来判断含有某种信号传递物质的树结构是否有效。
输入
输入文件包含几个案例。每个案例都描述了一系列 NTA 描述和一些初始树配置。每个案例的第一行由三个整数 n、m 和 k 组成。整数 n 表示信号的数量m 表示接受信号的数量k 表示信号传输元件的数量。接下来的 nk 行按行主序描述转换表。信号到信号传输元件的每个转换都在单独的一行中给出。在这样的行上每两个数字代表一个可能的转换。
接下来是树结构的描述。对于每个树结构在单独的一行中给出一个数字 L以指示树的级别。接下来的 L1 行包含字母序列描述树结构。每行描述一个级别。两个连续字母之间存在一个空格。第 0 级首先开始。在树结构中空节点用“*”标记。L-1 的树结构终止该 NTA 的树结构配置不应判断此结构。
输入以 n0、m0 和 k0 开头的描述结束。不应处理此描述。
注意在每种情况下NTA 最多有 l5 个信号和 10 个字符。每棵树的级别不超过 10。
输出
对于每个 NTA 描述打印 NTA 编号NTA1、NTA2 等后跟冒号。然后对于 NTA 的每个初始树配置打印单词“有效”或“无效”。
在 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
Invalidc代码
#includebits/stdc.husing 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, vectorvectorvectorint trans, int* left, int* right){vectorint 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;vectorvectorvectorint trans(n, vectorvectorint(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;vectorvectortree* 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题目解析
题目涉及一个名为 NTA非确定性树自动机的设备该设备基于一组转换规则将信号传递下去最终判断树结构是否有效。具体来说设备根据信号传递规则向二叉树的各个节点传递信号信号传递的有效性取决于每个叶子节点是否能够接受一对“有效的信号对”。
树是一个二叉树每个非叶子节点有两个子节点。信号传递过程中从根节点开始传递信号根节点通过转换规则将信号分发到两个子节点。这个过程会一直递归到叶子节点。
转移规则可以是确定性的一个信号只能产生一个新的信号对也可以是非确定性的一个信号可以产生多个不同的信号对。
当信号到达叶子节点时该节点被认为是“可摇动”的只有当该节点能产生一个有效的信号对两个信号都为接受信号时才认为该叶子节点是可摇动的。
如果从根节点到所有叶子节点的信号传递都能满足每个叶子节点的可摇动条件即每个叶子节点的信号对都为接受信号对则该树结构是有效的。
否则该树结构为无效。
样例理解 ZOJ 1011 NTA第一个样例解释 ZOJ 1011 NTA 第二个样例解释 实现思路
1、获得转移表
vectorvectorvectorint trans(n, vectorvectorint(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);//获得转移表}}
}2、创建层序遍历树形数组
输入是按层输入的根据这个特点可以得出层序遍历树形数组
vectorvectortree* roots(L 1); //初始化roots[0]表示第一层结点,roots[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));}
}3、根据层序遍历树形数组创建树形结构
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]就是我们的根节点已经创建好了4、深度优先搜索
bool dfs(tree* root, vectorvectorvectorint trans, int* left, int* right){//root当前根节点,trans转换表,left,right有效信号的区间范围vectorint 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;//所有的路这棵树都无效可以得出这棵树无效
}
