第三题（NOIP2012）

#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) {
        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;
    n = s1.size();
    memset(lefts, -1, sizeof(lefts));
    memset(rights, -1, sizeof(rights));
    memset(father, -1, sizeof(father));
    dfs(0, 1);
}

1. 【判断题】将23行去掉，程序运行结果与原来一致。
   {{ select(1) }}

• 正确
• 错误

2. 【判断题】该程序时间复杂度为 (O(n^{3})) 。
   {{ select(2) }}

• 正确
• 错误

3. 【判断题】将02行去掉，程序运行结果与原来一致。
   {{ select(3) }}

• 正确
• 错误

4. 【判断题】55行函数时间复杂度为O(1)。
   {{ select(4) }}

• 正确
• 错误

5. 【选择题】当输入为ABCDEF\n BCAEDF时，输出为（ ）。
   {{ select(5) }}

• 54
• 55
• 56
• 57

6. 【选择题】此程序主要执行的算法思路是（ ）。
   {{ select(6) }}

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