题目翻译

给定 $n(n\leq 100)$ 个字符串 $s_i$，满足 $\sum |s_i|\leq 100$，再给出 $m(m\leq 100)$ 个新串，给定 $x,y$，新串为 $s_x+s_y$。对于这 $m$ 个串，找到最大的 $k$，使得所有长度为 $k$ 的 01 串均被其包含。

题目思路

设子串长度是 $L$，因为 $\sum |s_i|\leq 100$，因此长度为 $L$ 的互不相同的子串仅在原 $n$ 个串中也只会有 $100$ 个。$m\leq 100$，每次连接最多产生 $L-1$ 个本质不同的长度为 $L$ 的子串，所以长度为 $L$ 的不同子串最多只有 $(L-1)\times 100+100=100L$ 个。然而要满足包含所有长度为 $L$ 的子串，必要条件是 $100L\geq 2^{L}$。解得 $L\leq 9$，也就是说，我们不可能构造答案为 $10$ 的数据。

那么知道这个结论之后就很好做了。我们判断是否合法只需要暴力匹配。但是我们合并之后的字符串会很长，我们发现中间很大一部分是没有用的，我们前后保留 $900$ 个字符即可。

但这 $900$ 个字符只是我们认为的『可能得到的更优答案』，这样又导致我们可能答案产生在没有被我们保留的部分中，产生在了我们删除的部分之中。设我们每次拼接 $s_x,s_y$，这两个串的答案是 $ans_x,ans_y$，我们删除的部分答案只可能有 $\max\{ans_x,ans_y\}$。因此我们答案取 $\max\{ans_x,ans_y,k\}$ 即可。其中 $k$ 是我们合并之后的答案。

完整代码

#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmx(T &x, T y) { x = max(x, y); }
int n, m;
string s[520];
int ans[520];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    cin >> m;
    for (int i = n + 1; i <= n + m; i++)
    {
        int x, y;
        cin >> x >> y;
        s[i] = s[x] + s[y];
        ans[i] = max(ans[x], ans[y]);
        for (int k = 1; k <= 9; k++)
        {
            bool ok = 1;
            for (int S = 0; S < 1 << k; S++)
            {
                string t = "";
                for (int j = 0; j < k; j++)
                    t += char('0' + (S >> j & 1));
                if (s[i].find(t) == string::npos)
                    ok = 0;
            }
            if (!ok)
            {
                chkmx(ans[i], k - 1);
                break;
            }
        }
        if (s[i].size() > 1800)
            s[i] = s[i].substr(0, 900) + s[i].substr(s[i].size() - 900);
        cout << ans[i] << endl;
    }
    return 0;
}