阅读程序

注意：切勿用电脑直接运行代码得出答案，请用大脑+笔+纸运行代码答题，否则是在浪费你的时间。

第9节：树和图

第3题【NOIP】2012

#include <iostream>
#include <string>
using namespace std;
int lefts[20], rights[20], father[20];
string s1, s2, s3;
int n, ans;
void calc(int x, int dep) {
	ans = ans + dep*(s1[x] - 'A' + 1);
	if (lefts[x] >= 0) calc(lefts[x], dep+1);
	if (rights[x] >= 0) calc(rights[x], dep+1);
}
void check(int x) {
	if (lefts[x] >= 0) check(lefts[x]);
	s3 = s3 + s1[x];
	if (rights[x] >= 0) check(rights[x]);
}
void dfs(int x, int th) {
	if (th == n) {
19		s3 = "";
		check(0);
		if (s3 == s2) {
			ans = 0;
			calc(0, 1);
			cout<<ans<<endl;
		}
		return;
	}
	if (lefts[x] == -1 && rights[x] == -1) {
		lefts[x] = th;
		father[th] = x;
		dfs(th, th+1);
		father[th] = -1;
		lefts[x] = -1;
	}
	if (rights[x] == -1) {
		rights[x] = th;
		father[th] = x;
		dfs(th, th+1);
		father[th] = -1;
		rights[x] = -1;
	}
	if (father[x] >= 0)
		dfs(father[x], th);
}
int main() {
	cin>>s1;
	cin>>s2;
48	n = s1.size();
	memset(lefts, -1, sizeof(lefts));
	memset(rights, -1, sizeof(rights));
	memset(father, -1, sizeof(father));
	dfs(0, 1);
}

●判断题

(1)将19行去掉，程序运行结果与原来一致。

{{ select(3-1) }}

• 正确
• 错误

(2)该程序时间复杂度为O($n^3$)。

{{ select(3-2) }}

• 正确
• 错误

(3)将02行去掉，程序运行结果与原来一致。

{{ select(3-3) }}

• 正确
• 错误

(4)48行函数时间复杂度为O(1)。

{{ select(3-4) }}

• 正确
• 错误

●选择题

(5)当输入为

ABCDEF
BCAEDF

,输出为()。

{{ select(3-5) }}

• 54
• 55
• 56
• 57

(6)此程序主要执行的算法思路是()。

{{ select(3-6) }}

• 深搜
• 广搜
• 动规
• 分治