2．N叉树
题目描述:
我们都了解二叉树的先根遍历，中根遍历和后根遍历。当知道先根遍历的结果和中根遍
历结果的时候，我们可以唯一的确定二叉树；同样的，如果知道了后根遍历的结果和中根遍
历结果，二叉树也是唯一确定的。但是如果只知道先根遍历和后根遍历的结果，二叉树就不
是唯一的了。但是我们可以计算满足条件的不同二叉树的一共有多少个。这不是一个很困难
的问题，稍微复杂一点，我们把这个问题推广到N叉树。
我们用小写英文字母来表示N 叉树的结点，不同的结点用不同的字母表示。比如，对
于4叉树，如果先根遍历的结果是abdefgc，后根遍历的结果是defgbca，那么我们可以
得到6个不同的4叉树（如下图）。
输入:
输入数据包括3行。
第一行是一个正整数N(1 ≤ N ≤ 20)，表示我们要考虑N叉树。
第二行和第三行分别是两个字符串序列，分别表示先根遍历和后根遍历的结果。
输出:
输出不同的N叉树的数目。题目中给的数据保证得到的结果小于2
31
。
输入样例:
4
abdefgc
defgbca
输出样例:
6
程序：
#include <stdio.h>
#include <string.h>
char str1[100], str2[100];
int N;
long com[100][100];
long getcom(int x, int y) {
if (y == 0 || x == y) ① ;
else if (com[x][y] != 0) return com[x][y];
else {
com[x][y] = getcom(x - 1, y)+ ② ;
return com[x][y];
}
}
long count(int a, int b, int c){
long sum = 1;
int k = 0;
int s = a + 1, t = c, p;
if (a == b) return 1;
while(s <= b){
p = t;
while(str1[s] != str2[t]) t++;
sum = sum * count(s, s + t - p, p);
s = ③ ;
④ ;
k++;
}
return ⑤ * getcom(N, k);
}
int main(){
int len;
scanf("%d", &N);
scanf("%s%s", str1, str2);
len = strlen(str1);
printf("%ld\n", count( ⑥ ));
return 0;
}
|
第十一届全国青少年信息学奥林匹克联赛初赛试题提高组(P&C)参考答案
|
|
由OIFans（www.OIFans.cn）整理 |
|
一. 单项选择题 （共10题，每题1.5分，共计15分。每题有且仅有一个正确答案.）
|
题号
|
1
|
2
|
３
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
选择
|
B
|
A
|
D
|
E
|
D
|
E
|
E
|
B
|
A
|
C
|
二．不定项选择题 （共10题，每题1.5分，共计15分。多选或少选均不得分）。
|
题号
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
|
选择
|
CDE
|
BCE
|
BC
|
CE
|
BCE
|
B
|
ACD
|
BCDE
|
ABCDE
|
BDE
|
三．问题求解（共2题，每题5分，共计10分）
1. 答： 5
2. 答： 11011
四. 阅读程序（共4题，每题8分，共计32分）
（1）程序的运行结果是: -7452
（2）程序的运行结果是: 3223
（3）程序的运行结果是: zzzaaabbbcccy
（4）程序的运行结果是: 31
五. 完善程序 (前5空，每空2分，后6空，每空3分，共28分)
pascal语言
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
1.
（1） num + len[i] div t
（2） num >= k
（3） left := 0
（4） left + 1
（5） not isok(mid) （或者 isok(mid) = false）
2.
（1） getcom := 1
（2） getcom(x - 1, y - 1)
（3） s + t - p + 1
（4） inc(t) （或者t := t + 1）
（5） sum
（6） 1, len, 1
C语言
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
1.
（1） num + len[i] / t
（2） num >= k
（3） left = 0
（4） left + 1
（5） !isok(mid) （或者 isok(mid) == 0）
2.
（1） return 1 （或者 return 1L，或者 return 1l）
（2） getcom(x - 1, y - 1)
（3） s + t - p + 1
（4） t++ （或者 ++t，或者 t = t + 1，或者 t += 1）
（5） sum
（6） 0, len - 1, 0 |
上一页 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
您当前的位置：惠州一中电教科组 -> 信息奥赛 -> 奥赛试题 -> 文章内容
减小字体
增大字体
∷相关文章评论∷ （评论内容只代表网友观点，与本站立场无关！） [