首页 > ACM题库 > HDU-杭电 > HDU 3198-Play on Words[解题报告]HOJ
2014
03-06

HDU 3198-Play on Words[解题报告]HOJ

Play on Words

问题描述 :

  Detective Liu recently got his eye on someone suspicious and also he got a letter from the guy. Detective Liu has his own method to judge whether a person was evil. He got a list words, which was collected during the years he worked. Those are the words that the evils often used.
  Here comes your task. Give a list of the “evil” words and another word; you are going to find the “evilness” of it. The “evilness” of the word is defined by the times that it appears in the list. If A is evil under the word B, then every letter of A should appear in B in order but could leave some of B unmatched.

输入:

The first line give M (10 <= M <= 5000), the number of the evil words.
Then M lines follows, which is the evil words each in one line, at most 20 characters, all lowercase.
Next comes N (1 <= N <= 1000) stand for the number of query words.
Then comes the query words with the same constraints.

输出:

The first line give M (10 <= M <= 5000), the number of the evil words.
Then M lines follows, which is the evil words each in one line, at most 20 characters, all lowercase.
Next comes N (1 <= N <= 1000) stand for the number of query words.
Then comes the query words with the same constraints.

样例输入:

3
hello
summer
goodbye
1
good

样例输出:

1

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>

using namespace std;

typedef long long ll;

#define REP(i,s,t) for(int i=(s);i<(t);i++)
#define FORST(X,S,T) for(int X=(S); X<=(T); X++)  
#define RFORST(X,S,T) for(int X=(S); X>=(T); X--)  
#define FOR(X,XB) for(int X=0; X<(XB); X++)
#define RFOR(X,XB) for(int X=(XB)-1; X>=0; X--)
#define FOREACH(i,v) for(typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define FILL(x,v) memset(x,v,sizeof(x))
const int INF = (int)1E9;
#define MAXN 1005

int N;
char buf[MAXN];
int odeg[26], ideg[26];
bool g[26][26], v[26], h[26];
void dfs(int k){
	v[k] = 1;
	REP(i,0,26) if(g[k][i] && !v[i]) dfs(i);
}
int main(){
	int cs;
	cin >> cs;
	while(cs--){
		int st;
		scanf("%d", &N);
		FILL(odeg,0); FILL(ideg,0); FILL(g,0); FILL(h,0);
		REP(i,0,N){
			scanf("%s", buf);
			int l = strlen(buf);
			int c0 = buf[0]-'a', cl = buf[l-1]-'a';
			odeg[c0]++; ideg[cl]++;
			g[c0][cl] = 1;
			h[c0] = h[cl] = 1;
			st = c0;
		}
		bool ok = 1;
		int ii=0, oo=0;
		REP(i,0,26){
			if(ideg[i]!=odeg[i]){
				if(ideg[i]==odeg[i]+1) ii++;
				else if(odeg[i]==ideg[i]+1) { oo++; st = i; }
				else{ ok = 0; break; }
			}
		}
		if(ok && (ii==1 && oo==1 || ii==0 && oo==0)){
			FILL(v,0);
			dfs(st);
			REP(i,0,26) if(h[i] && !v[i]) { ok = 0; break; }
		}else ok = 0;
		if(ok) puts("Ordering is possible.");
		else puts("The door cannot be opened.");
	}
	return 0;
}

  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  3. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c