c 做网站后端,百度指数搜索指数的数据来源,wordpress 下载选择,用asp做网站需要什么软件UVa11604 General Sultan 题目链接题意分析AC 代码 题目链接 UVA - 11604 General Sultan
题意 给出一些0和1组成的模式串#xff0c;问是否存在一个串使得有多种方案将这个串分解成模式串。 给一个包含n#xff08;n≤100#xff09;个符号的二进制编码方式#xff… UVa11604 General Sultan 题目链接题意分析AC 代码 题目链接 UVA - 11604 General Sultan
题意 给出一些0和1组成的模式串问是否存在一个串使得有多种方案将这个串分解成模式串。 给一个包含nn≤100个符号的二进制编码方式是否存在一个二进制序列存在至少两种解码方法。比如{a01, b001, c01001}是有歧义的因为01001可以解码为ab或者c。每个编码由不超过20个0或1组成。
分析 很好的一道图论建模题目思路来自于HouseFangFZC的博文。 先看一个两种方案去拼接形成同一个串的图 可以发现总是一个方案新追加的串和另一个方案当前未匹配部分做匹配并且其中一者完全匹配掉另一者有剩余部分或者另一者也匹配完即找到了两种不同拼接方案。 将每个模式串的每一个字符看成一个结点并额外增加起点s、终点t两个虚拟结点。首先起点与每个模式串的首字母连一条有向边。对于第i个模式串考虑其第 h i h_i hi个字符开始的子串对应节点u若其与第j个模式串做匹配注意 h i 0 h_i0 hi0时 j ≠ i j\ne i ji满足至少一者匹配到结尾则连有向边分三种情况若两者都匹配完则 u → t u\rightarrow t u→t若模式串j的首个未匹配字符是 h j h_j hj对应节点v则 u → v u\rightarrow v u→v若子串 h i h_i hi的首个未匹配字符是 h x h_x hx对应节点w则 u → w u\rightarrow w u→w。 有向图建完后跑一遍dfs看起点s能否到达终点t就能解决问题。
AC 代码
#include iostream
#include cstring
using namespace std;#define L 22
#define N 101
int g[N*L][N*L], c[N*L], e[N], t[N], m, n, kase 0; char s[N][L], tmp[L]; bool vis[N*L];int common(int i, int h, int j) {int k 0;while (h e[i]) {if (s[i][h] ! s[j][k]) return k;h; k;}return k;
}bool dfs(int u 0) {if (u m) return true;vis[u] true;for (int i0, v; ic[u]; i) if (!vis[v g[u][i]] dfs(v)) return true;return false;
}void solve() {memset(c, 0, sizeof(c)); memset(vis, 0, sizeof(vis));for (int i0; in; i) cin tmp s[i], e[i] strlen(s[i]), g[0][c[0]] t[i] i1 ? 1 : t[i-1] e[i-1];m t[n-1] e[n-1];for (int i0; in; i) for (int j0; je[i]; j) for (int k0; kn; k) {if (ik j0) continue;int cc common(i, j, k), u t[i]j;if (cc e[k] ccj e[i]) g[u][c[u]] m;else if (cc e[k] ccj e[i]) g[u][c[u]] t[k] cc;else if (cc e[k] ccj e[i]) g[u][c[u]] u cc;}cout Case # kase (dfs() ? : Ambiguous. : : Not ambiguous.) endl;
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);while (cin n n) solve();return 0;
}
