题目大意：有一颗完全二叉树，给节点一个信号会从一个表中选择一对信号分别传递给两个子节点。最后判断所有叶子节点是否满足给定的规则。题目有点长，具体可参见原题。
首先是表格中数据的存储，由于会有多个元素，用vector进行保存。其次，树是完全二叉树，可以用数组存储树。然后就是遍历二叉树了。
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std; struct Signal
{
int left, right;
};
vector<Signal> table[][];
char tree[]; int n, m, k;
// n is the number of signals, m is the number of accepting signals, k is the number of signal transmitting elements.
int l; // the level of the tree
int nodeN; // the number of nodes of the tree void readTable()
{
for (int i = ; i < n; i++)
for (int j = ; j < k; j++)
{
table[i][j].clear();
Signal pair;
while (true)
{
scanf("%d%d", &pair.left, &pair.right);
table[i][j].push_back(pair);
char ch = getchar();
if (ch == '\n') break;
}
}
} void readTree()
{
char ch;
nodeN = ;
for (int i = ; i <= l; i++)
for (int j = ; j < (<<i); j++)
{
cin >> ch;
tree[++nodeN] = ch;
}
} bool judge(int signal, int node)
{
if (tree[node] == '*' || node > nodeN)
{
if (signal < n-m) return false;
else return true;
}
int t = tree[node] - 'a';
for (int i = ; i < table[signal][t].size(); i++)
{
int signal1 = table[signal][t][i].left;
int signal2 = table[signal][t][i].right;
if (judge(signal1, node*) && judge(signal2, node*+)) return true;
}
return false;
} int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int kase = ;
while (scanf("%d%d%d", &n, &m, &k) && (n || m || k))
{
if (kase++) printf("\n");
printf("NTA%d:\n", kase);
readTable();
while (scanf("%d", &l) && (l != -))
{
readTree();
if (judge(, )) printf("Valid\n");
else printf("Invalid\n");
}
}
return ;
}
vector就用过几次，算是熟悉了一下vector的用法吧，clear()清除内容，另外常用的就是puch_back()了，其他的还有pop_back()和insert()。还有那个利用'\n'判断是否还有数据的方法比用读整行字符串再处理简单多了，然后就是知道了用 cin >> ch 读字符可以跳过空格。最后用递归判断所有叶子节点是否符合要求的思想也让我长见识啦：D。因为输出时把NTA写成NAT，WA了一次，无语...