Skip to content

S2OJ - 965. 交错的字符串

题解706 字
# S2OJ # 搜索 # 2019 # 雅礼集训
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

Mark Douglas 是一名律师。他的客户 Yuri Ball 在一场车祸中不幸去世。为了帮助 Yuri 的亲属拿到他的遗产，Mark 需要得到一个密码。在 Yuri 的笔记本上，有一个长为 2n2n 的只包含小写字母的字符串，Mark 知道密码恰好是将这个字符串分解为两个长度为 nn 的子序列且它们构成的字符串恰好相反的方案数。我们认为两种分解方法是不同的，当且仅当两个下标集合构成的集合 {S1,S2}\{S_1, S_2\} 是不同的，注意 {S1,S2}\{S_1, S_2\} 和 {S2,S1}\{S_2, S_1\} 我们认为是相同的分解方法。如 cabaacba 的合法分解共有 cabaacba 和 cabaacba 两种。Mark 希望你能帮助他计算出密码，事成之后他决定分给你 six million five hundred thousand dollars 并邀请你去柬埔寨度假。

#输入格式

第一行为一个正整数 nn。

第二行为一个长度为 2n2n 的字符串，仅包含小写字母。

#输出格式

输出一行表示答案。

#输入输出样例

样例输入 #1

4
cabaacba

样例输出 #1

2

#数据范围与约定

测试点编号 约束
1∼71 \sim 7 n≤10n \leq 10
8∼108\sim 10 字符串中仅有小写字母 a
11∼1411 \sim 14 字符串中除去两个 b 外其余全是 a
15∼1815 \sim 18 字符串中仅有 a、b 两种字符
19∼2519 \sim 25 无

对于 100%100\% 的测试数据，1≤n≤181 \leq n \leq 18。

#思路

折半搜索。

我们将字符串分为前后两部分。如果前半部分中搜得的前缀串为 {S1,S2}\{S_1, S_2\}，那么后半部分中搜得的后缀串必须为 {rev(S2),rev(S1)}\{\text{rev}(S_2), \text{rev}(S_1)\}，且为有序对。对于两侧分别枚举每个字符的归属情况，使用 std::unordered_map 计数即可。

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <string>
#include <unordered_map>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = (18 << 1) + 5;

int n;
long long ans;
bool vis[N];
std::string s;
std::unordered_map<std::string, int> map;

void dfs1(int x) {
    if (x == n + 1) {
        std::string s1, s2;

        for (int i = 1; i <= n; i++) {
            (vis[i] ? s2 : s1).push_back(s[i]);
        }

        map[s1 + ' ' + s2]++;

        return;
    }

    dfs1(x + 1);
    vis[x] = true;
    dfs1(x + 1);
    vis[x] = false;
}

void dfs2(int x) {
    if (x == n * 2 + 1) {
        std::string s1, s2;

        for (int i = n + n; i > n; i--) {
            (vis[i] ? s2 : s1).push_back(s[i]);
        }

        ans += map[s1 + ' ' + s2];

        return;
    }

    dfs2(x + 1);
    vis[x] = true;
    dfs2(x + 1);
    vis[x] = false;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s;

    s = ' ' + s;

    dfs1(1);
    dfs2(n + 1);

    cout << (ans >> 1) << endl;

    return 0;
}