http://ac.jobdu.com/problem.php?pid=1009
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define rep(i,j,k) for(int i=j;i<=k;i++) #define inone(i) scanf("%d",&i) //typedef struct nd { int v; struct nd * l, *r;} Nd; const int maxn = 1000; char s[20]; int n, v[maxn], l[maxn], r[maxn], vis[maxn], root, tot; void build(char c, int& root) { if (root == -1) { v[tot] = c; root = tot++; return; } if (v[root] > c) build(c, l[root]); else build(c, r[root]); } bool visit(int root, char c) { if (root == -1) return false; if (v[root] == c) { vis[root] = 1; return true; } if (vis[root] == 0) return false; if (v[root] > c) return visit(l[root], c); else return visit(r[root], c); } int main() { while (inone(n) != EOF) { fill(l, l + maxn, -1); fill(r, r + maxn, -1); if (n == 0) break; scanf("%s",s); tot = 0; root = -1; int len = strlen(s); rep(i,0,len-1) build(s[i],root); rep(i,1,n) { scanf("%s", s); bool flag = true; fill(vis, vis + maxn, 0); rep(j, 0, len - 1) { if (visit(root, s[j]) == false) { flag = false; break; } } printf("%s\n",flag?"YES":"NO") ; } } return 0; }
