题解

问题描述

题目要求我们根据多张写有“B”和“G”的字符串纸，推断出最少可能的孩子数量。每个字符串代表一个回合的传递过程，孩子们围成一圈，纸张可以顺时针或逆时针传递。我们需要找到一个最小的圈，使得所有字符串都能在这个圈中找到对应的连续子序列。

输入输出格式

• 输入：
  • 第一行是一个整数 ( N )，表示纸张的数量。
  • 接下来 ( N ) 行，每行是一个字符串，由字母“B”和“G”组成。
  • 当 ( N = 0 ) 时，输入结束。
• 输出：
  • 对于每个测试用例，输出一行，表示最少可能的孩子数量。

问题分析

1. 字符串的循环性质：
   由于孩子们围成一圈，每个字符串可以有两种表示方式：正序和逆序。例如，字符串“BGGB”可以表示为“BGGB”或“BGBG”（逆序）。

2. 子串匹配：
   每个字符串必须是某个更大字符串的子串。我们需要找到一个最小的字符串，使得所有输入的字符串都能在这个字符串中找到对应的子串。

3. 动态规划与状态压缩：

   • 使用动态规划来解决这个问题。状态表示为：当前已经选择的字符串集合、最后一个选择的字符串、以及最后一个字符串的方向。
   • 使用状态压缩来表示选择的字符串集合，因为 ( N ) 的最大值为 16，可以用一个 16 位的整数来表示。

代码解析

1. 输入处理：

   • 读取每个字符串，并将其正序和逆序存储起来，方便后续处理。

2. 预处理：

   • 检查每个字符串是否是其他字符串的子串。如果是，则可以忽略该字符串，因为它不会影响最终结果。
   • 计算每个字符串在另一个字符串中的重叠长度。重叠长度表示两个字符串可以拼接的部分长度。

3. 动态规划：

   • 使用三维数组 dp[mask][i][x] 表示当前选择的字符串集合为 mask，最后一个选择的字符串为 i，方向为 x 的最大重叠长度。
   • 通过状态转移方程更新 dp 数组，状态转移时考虑选择下一个字符串和方向。

4. 结果计算：

   • 最终答案为所有字符串的总长度减去最大重叠长度。如果结果小于 2，则输出 2（因为至少有两个孩子）。

代码详细解析

#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
using namespace std;

struct seq
{
    char s[2][110]; // 存储正序和逆序字符串
    int l;          // 字符串长度
}a[20], f[20];     // a 存储所有字符串，f 存储最终需要处理的字符串

int n, n1;          // n 是输入的字符串数量，n1 是最终需要处理的字符串数量
int ovl[20][2][20][2]; // 重叠长度
int dp[1 << 17][20][2]; // 动态规划数组
bool out[20];      // 标记是否可以忽略的字符串
char temp[110];    // 临时存储字符串

// 输入处理
void in()
{
    int i, j;
    for (i = 1; i <= n; i++)
    {
        scanf("%s", a[i].s[0] + 1); // 输入字符串
        a[i].l = strlen(a[i].s[0] + 1); // 获取长度
        strcpy(temp + 1, a[i].s[0] + 1); // 复制字符串
        for (j = 1; j <= a[i].l; j++)
            a[i].s[1][j] = temp[a[i].l - j + 1]; // 生成逆序字符串
    }
}

// 判断 s1 是否是 s2 的子串
bool inc(char* s1, int l1, char* s2, int l2)
{
    if (l1 > l2) return 0; // 如果 s1 比 s2 长，不可能是子串
    int i, j;
    bool flag;
    for (i = 1; i + l1 - 1 <= l2; i++) // 遍历 s2 的所有可能子串
    {
        flag = 1;
        for (j = 1; j <= l1; j++) // 检查子串是否匹配
            if (s1[j] != s2[i + j - 1])
            {
                flag = 0;
                break;
            }
        if (flag) return 1; // 如果找到匹配，返回 true
    }
    return 0; // 否则返回 false
}

// 计算两个字符串的重叠长度
int cal(char* s1, int l1, char* s2, int l2)
{
    int i, j;
    bool flag;
    for (i = max(1, l1 - l2 + 2); i <= l1; i++) // 遍历可能的重叠部分
    {
        flag = 1;
        for (j = 1; i + j - 1 <= l1; j++) // 检查重叠部分是否匹配
            if (s2[j] != s1[i + j - 1])
            {
                flag = 0;
                break;
            }
        if (flag) return l1 - i + 1; // 如果找到匹配，返回重叠长度
    }
    return 0; // 否则返回 0
}

// 预处理
void pre()
{
    int i, j, x, y;
    n1 = 0; // 初始化需要处理的字符串数量
    memset(out, 0, sizeof(out)); // 初始化标记数组
    for (i = 1; i <= n; i++) // 遍历所有字符串
        for (j = 1; j <= n; j++)
            if (i != j && (inc(a[i].s[0], a[i].l, a[j].s[0], a[j].l) || inc(a[i].s[0], a[i].l, a[j].s[1], a[j].l)) && (!out[j]))
                out[i] = 1; // 如果 a[i] 是 a[j] 的子串，标记 a[i] 可以忽略
    for (i = 1; i <= n; i++) // 筛选需要处理的字符串
        if (!out[i])
            f[n1++] = a[i];
    for (i = 0; i < n1; i++) // 计算所有字符串的重叠长度
        for (x = 0; x < 2; x++)
            for (j = 0; j < n1; j++)
                for (y = 0; y < 2; y++)
                    ovl[i][x][j][y] = cal(f[i].s[x], f[i].l, f[j].s[y], f[j].l);
}

// 更新动态规划数组
void upd(int &x, int y)
{
    if (y > x) x = y; // 如果 y 更优，更新 x
}

// 动态规划求解
void solve()
{
    int i, j, x, y, mx = (1 << n1) - 1, tot = 0, k, ans; // mx 是状态集合的最大值，tot 是所有字符串的总长度
    memset(dp, 128, sizeof(dp)); // 初始化动态规划数组
    dp[1][0][0] = 0; // 初始状态
    for (i = 1; i < mx; i++) // 遍历所有状态集合
        for (j = 0; j < n1; j++) // 遍历当前选择的字符串
            if (i & (1 << j)) // 如果当前字符串在集合中
                for (x = 0; x < 2; x++) // 遍历当前字符串的方向
                    for (k = 0; k < n1; k++) // 遍历下一个选择的字符串
                        if (!(i & (1 << k))) // 如果下一个字符串不在集合中
                            for (y = 0; y < 2; y++) // 遍历下一个字符串的方向
                                upd(dp[i | (1 << k)][k][y], dp[i][j][x] + ovl[j][x][k][y]); // 状态转移
    for (i = 0; i < n1; i++) // 计算所有字符串的总长度
        tot += f[i].l;
    ans = -1; // 初始化答案
    for (i = 0; i < n1; i++) // 遍历所有可能的最终状态
        for (x = 0; x < 2; x++)
            upd(ans, dp[mx][i][x] + ovl[i][x][0][0]); // 更新答案
    printf("%d\n", max(2, tot - ans)); // 输出最终结果
}

int main()
{
    while (scanf("%d", &n) && n) // 读取输入，直到 n = 0
    {
        in(); // 输入处理
        pre(); // 预处理
        solve(); // 动态规划求解
    }
    return 0;
}

关键点解释

1. 字符串的正序和逆序：
   每个字符串有两种表示方式，正序和逆序。这是因为纸张可以顺时针或逆时针传递。

2. 子串匹配：
   使用 inc 函数判断一个字符串是否是另一个字符串的子串。如果某个字符串是另一个字符串的子串，则可以忽略它，因为它不会影响最终结果。

3. 重叠长度计算：
   使用 cal 函数计算两个字符串的重叠长度。重叠长度表示两个字符串可以拼接的部分长度。

4. 动态规划：
   使用状态压缩表示选择的字符串集合，动态规划数组 dp[mask][i][x] 表示当前选择的字符串集合为 mask，最后一个选择的字符串为 i，方向为 x 的最大重叠长度。通过状态转移方程更新 dp 数组。

5. 结果计算：
   最终答案为所有字符串的总长度减去最大重叠长度。如果结果小于 2，则输出 2，因为至少有两个孩子。