[实验舱 CSP/NOIP新赛制内部挑战赛5] B.小F的编码（BFS/DP）

Problem

题目地址

Solution

• 考虑一个简化版问题：给定长度为 \(m\) 的字符串 \(S\)，和一些模式串 \(c_i\)，问有多少种方案拼成 \(S\)。

• 思路：设 \(f[i]\) 表示有多少种方案拼成 \(S[1...i]\)，那么有转移 \(f[i]=\sum_{c_x=S[k...i]} f[k]\)，答案就是 \(f[m]\)。具体的，看作有 \(m+1\) 个点，若 \(c_x = S[k...i]\)，则在 \(k->i\) 连一条边，最统计有多少种从 \(0\) 到 \(m\) 的路径。

题解

设 \(f[i,j]\) 表示第 \(i\) 个字符串匹配了 \(j\) 位是否可达。

同样把 \((i,j)\) 这个状态看成一个点。\((i,j)->(u,v)\) 之间有边则说明可以将 \(c_u\) 接上去，即满足：\(S_i[j...len]=S_u[1...v]\)。

注意处理一些细节。初始状态 \(f[i,0]=1\)，最终看是否有 \(f[i,n]=1\)。状态数 \(O(nL)\)，建边复杂度 \(O(n^2L^2)\)，时间复杂度 \(O(n^2L^2)\)。

Code

Talk is cheap.Show me the code.

#include
#define mp make_pair
#define fi first
#define se second
using namespace std;
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
typedef pair PII;
const int N = 57, maxn = N*N;
int n,cnt;
int head[maxn];
int f[N][N];
char str[N][N];
struct Edge {
    int next,to;
}edge[maxn*maxn];
inline void add(int u,int v) {
    edge[++cnt] = (Edge)<%head[u],v%>;
    head[u] = cnt;
}
bool check(int x,int lx,int y,int ly,int len) {
    for(int i=0;i= len-j) {
                    if(check(i,j+1,u,1,len-j)) {
                        add(Getid(mp(i,j)), Getid(mp(u,len-j)));
                    }
                } else {
                    if(check(i,j+1,u,1,ulen)) {
                        add(Getid(mp(i,j)), Getid(mp(i,j+ulen)));
                    }
                }
            }
        }
    }
    queue q;
    for(int i=1;i<=n;++i) {
        int len = strlen(str[i]+1);
        q.push(Getid(mp(i,0)));
        f[i][0] = 1;
    }
    while(!q.empty()) {
        int u = q.front(); q.pop();
        PII uu = Getpii(u); int x = uu.fi, y = uu.se;
        for(int i=head[u];i;i=edge[i].next) {
            int v = edge[i].to;
            PII vv = Getpii(v); int nx = vv.fi, ny = vv.se;
            if(!f[nx][ny]) {
                f[nx][ny] = f[x][y]; q.push(v);
            }
        }
    }
    bool flag = 0;
    for(int i=1;i<=n;++i) flag |= f[i][strlen(str[i]+1)];
    if(flag) puts("No");
    else puts("Yes");
}
int main()
{
    int T = read();
    while(T--) work();
    return 0;
}
/*
1
2
00
000

No
*/

Summary

可能有一点相似题：