题目：传送门
题意
给你两个01串 a 和 b，让你构造一个长度最短的且字典序最小的 01串，使得这个 01串既不是 a 的子串，也不是 b 的子串。
a,b串的长度都在1~4000之间。
思路
设 dp[x][y] 表示 a 串处理完了前 x 个， b 串处理完了前 y 个，构造出来的答案串的最小长度。
那么接下来我们可以对答案串进行两种操作：加入一个0和加入一个1。
若加入的是 0，那么对于 a 串来说，他可以直接跳到 succa[x][0] (succa[i][j] 表示 a 串的 x 位置后面的第一个 0 的位置)，同理， b 串可以直接跳到 succb[x][0]；
若加入的是 1，那么对于 a 串来说，他可以直接跳到 succa[x][1] (succa[i][j] 表示 a 串的 x 位置后面的第一个 1 的位置)，同理， b 串可以直接跳到 succb[x][1]；
那我们对这两种操作，取个 min，更新答案就可以了。
#include <bits/stdc++.h> #define LL long long #define ULL unsigned long long #define UI unsigned int #define mem(i, j) memset(i, j, sizeof(i)) #define rep(i, j, k) for(int i = j; i <= k; i++) #define dep(i, j, k) for(int i = k; i >= j; i--) #define pb push_back #define make make_pair #define INF 0x3f3f3f3f #define inf LLONG_MAX #define PI acos(-1) #define fir first #define sec second #define lb(x) ((x) & (-(x))) #define dbg(x) cout<<#x<<" = "<<x<<endl; using namespace std; const int N = 1e6 + 5; char a[N], b[N]; int lena, lenb; int succa[N][2], succb[N][2]; int f[4004][4004], dp[4004][4004]; int dfs(int posa, int posb) { if(posa == lena + 1 && posb == lenb + 1) return 0; /// 若两个串都处理完了，就返回 if(dp[posa][posb]) return dp[posa][posb]; /// 若处理过了，就返回 int tmp1 = dfs(succa[posa][0], succb[posb][0]); /// 加入 0 int tmp2 = dfs(succa[posa][1], succb[posb][1]); /// 加入 1 if(tmp1 <= tmp2) f[posa][posb] = 0; /// 要字典序最小，所以 tmp1 == tmp2 也是加 0 else f[posa][posb] = 1; return dp[posa][posb] = min(tmp1, tmp2) + 1; /// 更新 dp } void print(int posa, int posb) { /// 输出答案 if(posa == lena + 1 && posb == lenb + 1) return ; if(f[posa][posb] == 0) { printf("0"); print(succa[posa][0], succb[posb][0]); } else { printf("1"); print(succa[posa][1], succb[posb][1]); } } void solve() { scanf("%s", a + 1); scanf("%s", b + 1); lena = strlen(a + 1); lenb = strlen(b + 1); succa[lena + 1][0] = succa[lena + 1][1] = lena + 1; succb[lenb + 1][0] = succb[lenb + 1][1] = lenb + 1; dep(i, 0, lena) { /// 预处理 succa[i][0], succa[i][1]； succa[i][0] = succa[i + 1][0]; succa[i][1] = succa[i + 1][1]; if(a[i + 1] == '0') succa[i][0] = i + 1; else succa[i][1] = i + 1; } dep(i, 0, lenb) { /// 预处理 succb[i][0], succb[i][1]； succb[i][0] = succb[i + 1][0]; succb[i][1] = succb[i + 1][1]; if(b[i + 1] == '0') succb[i][0] = i + 1; else succb[i][1] = i + 1; } int up = dfs(0, 0); /// 记忆化搜索 print(0, 0); /// 输出答案 puts(""); } int main() { // int _; scanf("%d", &_); // while(_--) solve(); solve(); return 0; }