题解：P3881 [JLOI2008] CODES

zhangzhixing99 · 2026-07-22 14:16:53 · 题解

前情提要

暴力 DP 过了。

荣获最优解榜三。——2026.7.22 \ 14:32

题意简述

给定 n 个字符串 s_1 \sim s_n，保证字符集 \isin \{\texttt{0}, \texttt{1}\}。求一个字符串 T，可以据此构造两种不同的序列，满足：

• 设这个序列为 p_1, p_2, \cdots, p_k，则 \forall \ i \isin [1, k], p_i \isin [1, n]；s_{p_1} + s_{p_2} + \cdots + s_{p_k} = T，其中 a + b 表示字符串 a 拼接 b。

求最短的 T，在所有最短的中选取字典序最小的那一个。

保证题目有解。

前置知识

• 动态规划。
• 实现上需要一些 \operatorname{set} 的技巧。

  正题开始

  考虑从零开始拼接两个字符串，并关注当前两个串的差异，如：

• 样例中，其中一个串现在拼接到了 \texttt{00110}（s_2 + s_5），另一个串拼接到了 \texttt{001100}（s_4），则它们的差异为 \texttt{0}。如果第一个串拼接为 \texttt{001100110}，而第二个串不变，则此时差异变为 \texttt{110}。

根据当前的长串的长度和差异进行 \operatorname{DP}，因为当差异相同时，只需要取较长串字典序最小者即可。

设 f_{i, d} 表示当前较长串长度为 i，差异为 d，较长串字典序最小是什么。d 一定是较长串中最后一个拼接的串的后缀，所以 d 最多有 400 种可能，最长约为 20。

转移时，考虑在较短串上拼接新串 s_j。则有 3 种情况：

• ## 实现方法 注意到转移时，$i$ 增加或 $d$ 变短，所以先枚举 $i$，在从长到短枚举 $d$。

可以使用 \operatorname{map} 保存 \operatorname{DP} 数组。转移时使用 \operatorname{set} 枚举 d 即可。参见代码。

时间复杂度

• 设 \max(s_i) = L, \max(i) = i_{max}。
• 时间复杂度为 O(i_{max} \cdot n^2 \cdot L^2 \cdot \log_2 (n \cdot L))，实际上很难跑满。
• 所以时间复杂度取决于实现上 i_{max} 取到多少。实测 i_{max} 取到 400 即可。

  空间复杂度

• 取决于实现方法。

  代码

  
  #include <bits/stdc++.h>
  using namespace std;

define EOL '\n'

define int long long

define double long double

define sqrt sqrtl

struct Cmp { bool operator () (const string &s1, const string &s2) const { return s1.size() >= s2.size(); } };

string s[30]; map<string, string> f[410];

int read() { int ret = 0, neg = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') { neg = -neg; } ch = getchar(); } while (isdigit(ch)) { ret = ret 10 + ch - '0'; ch = getchar(); } return ret neg; }

string reads() { string s = ""; char c = getchar(); while (!isdigit(c)) { c = getchar(); } while (isdigit(c)) { s += c; c = getchar(); } return s; }

void writes(string s) { for (char c: s) { putchar(c); } }

bool cmp(string s1, string s2) { if (s1.size() != s2.size()) { return s1.size() < s2.size(); } return s1 <= s2; }

signed main() { int n = read(); for (int i = 1; i <= n; ++i) { s[i] = reads(); } sort(s + 1, s + n + 1, cmp); for (int i = 1; i < n; ++i) { for (int j = i + 1; j <= n; ++j) { if (s[j].substr(0, s[i].size()) == s[i]) { int sz = s[j].size(); string t = s[j].substr(s[i].size()); if (!f[sz].count(t)) { f[sz][t] = s[j]; } else { f[sz][t] = min(f[sz][t], s[j]); } } } } for (int i = 1; i <= 400; ++i) { set<string, Cmp> se; for (pair<string, string> kv: f[i]) { se.insert(kv.first); } while (!se.empty()) { string d = *se.begin(), t = f[i][d]; se.erase(se.begin()); for (int j = 1; j <= n; ++j) { if (s[j].size() <= d.size()) { if (d.substr(0, s[j].size()) == s[j]) { string nd = d.substr(s[j].size()); if (!f[i].count(nd)) { f[i][nd] = t; } else { f[i][nd] = min(f[i][nd], t); } se.insert(nd); } } else { if (s[j].substr(0, d.size()) == d) { string nd = s[j].substr(d.size()); int sz = i + nd.size(); if (!f[sz].count(nd)) { f[sz][nd] = t + nd; } else { f[sz][nd] = min(f[sz][nd], t + nd); } } } } } if (f[i].count("")) { writes(to_string(i) + EOL + f[i][""] + EOL); return 0; } } return 3; }