C++(g++ 7.5.0) 解法, 执行用时: 179ms, 内存消耗: 197772K, 提交时间: 2023-05-06 17:32:31

#include<bits/stdc++.h>
using namespace std;
const int N=5010+10;
int dp[N][N][2];
int son[N][2], cnt[N], idx;
struct Node{
    int a,b,k;
};
queue<Node> q;
void insert(string str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - '0';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}
bool update(int &x,int y){
    if(x==-1){
        x=y+1;
        return true;
    }
    return false;
}
bool work(Node t,int k){
    int a=son[t.a][k],b=son[t.b][k];
    if(a&&b){
        int now=dp[t.a][t.b][t.k];
        if(cnt[a]&&cnt[b]&&t.k&&update(dp[0][0][1],now)){
        	return true;
        }
        if(cnt[a]&&update(dp[0][b][1],now))
			q.push({0,b,1});
        if(cnt[b]&&update(dp[a][0][1],now))
			q.push({a,0,1});
        if(update(dp[a][b][t.k],now))
			q.push({a,b,t.k});
    }
    return false;
}
void bfs(){
    dp[0][0][0]=0;
    q.push({0,0,0});
    while(q.size()){
        auto t=q.front();
        q.pop();
        if(work(t,0))return;
        if(work(t,1))return;
    }
}
void solve(){
    memset(dp,-1,sizeof dp);
    int n;
    cin>>n;
    string s;
    for(int i=1;i<=n;i++){
        cin>>s;
        insert(s);
    }
    bfs();
    cout<<dp[0][0][1];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    solve();
    
}

C++ 解法, 执行用时: 122ms, 内存消耗: 196524K, 提交时间: 2022-07-07 15:55:56

#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int n;
int nxt[N][2], tot;
bool ed[N];
char s[N];
int dp[N][N][2];
void ins(char* s) {
	int p = 0;
	for (int i=0; s[i]; i++) {
		int k = s[i] - '0';
		if (!nxt[p][k]) nxt[p][k] = ++tot;
		p = nxt[p][k];
	}
	ed[p] = true;
}
bool upd(int& x, int y) {
	if (x==-1) {
		x = y + 1;
		return true;
	}
	return false;
}
int main() {
	scanf("%d", &n);
	for (int i=1; i<=n; i++) {
		scanf("%s", s);
		ins(s);
	}
	queue<array<int, 3>> que;
	memset(dp, -1, sizeof(dp));
	dp[0][0][0] = 0;
	que.push({0, 0, 0});
	while (!que.empty()) {
		auto cur = que.front(); que.pop();
		for (int k=0; k<2; k++) {
			int p = nxt[cur[0]][k], q = nxt[cur[1]][k];
			if (p && q) {
				if (upd(dp[p][q][cur[2]], dp[cur[0]][cur[1]][cur[2]])) que.push({p, q, cur[2]});
				if (ed[p] && ed[q] && upd(dp[0][0][cur[2]], dp[cur[0]][cur[1]][cur[2]])) que.push({0, 0, cur[2]});
				if (ed[p] && upd(dp[0][q][1], dp[cur[0]][cur[1]][cur[2]])) que.push({0, q, 1});
				if (ed[q] && upd(dp[p][0][1], dp[cur[0]][cur[1]][cur[2]])) que.push({p, 0, 1});
			}
		}
	}
	printf("%d\n", dp[0][0][1]);
	return 0;
}