【题解】POJ-3746 Teacher YYF

Teacher YYF(POJ-3746)

题面

As we all know, grammar is very important when learning English. Now, YYF become a teacher of a primary school. The students are good at memory so they can tell the meaning and the function (noun, verb …) of the words in the textbook. But, they cannot use these words properly.

In YYF’s mind, writing sentences is a good way to learn grammar. So he tells the student to write 20 sentences a day, using the word learned in the class. As YYF has a lot of student, he will receive many sentences from his student. What a horrible work to check all the sentences. You are one of YYF’s friends, so he asks you for help. You task is to write a program to check the sentences.

To make the work simple, YYF chooses a part of the grammar: All the words can be grouped into seven divisions (noun, pronoun, adjective, adverb, preposition, article, and verb). A verb can be transitive or intransitive. So we use “n.”, “pron.”, “adj.”, “adv.”, “prep.”, “art.”, “vt.” and “vi.” to be short of noun, pronoun, adjective, adverb, preposition, article, transitive verb and intransitive verb. If a word is marked as “v.”, it can be used as either transitive verb or intransitive verb.

Here comes the sentence structure:

  1. Subject + Intransitive Verb
  2. Subject + Transitive Verb + Object

Noun and pronoun can be used as Subject or Object. When using a noun, an article should be placed ahead of it. A noun can be modified by an adjective and a verb can be modified by an adverb. When an adjective is used to modify a noun, it should be put between article and noun. When an adverb is used to modify a verb, it should be put ahead of the verb. A prepositional phrase can be put ahead of Subject, between Subject and Verb, behind Intransitive Verb, between Verb and Object, or behind Object. A prepositional phrase is made up of a preposition and a noun/pronoun. In one sentence, at most one prepositional phrase is allowed. Any two parts of the sentence cannot intersect. For example, “He is a good student” is OK, but “He a good is student” is not. Every word in the dictionary will have only one function. The words are not case sensitive and Subject-Verb Agreement does not matter. That’s all the rules. Now, it’s your time to show.

输入

The input contains only one case.
The first line specifies two number N and M (1 ≤ N, M ≤ 5000). The next N lines will be the words and the functions. Every line contains a word and its function, separated by a space. The next M lines will be the sentences — one sentence per line. Each sentences contains at most 20 words. Every word in the sentences will appear in the dictionary.

输出

The output contains M lines. For each line, output “YES” if the sentence is OK, and output “NO” if not.

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
10 6
he pron.
see vt.
a art.
baby n.
at prep.
the art.
airport n.
happy adj.
guess v.
immediately adv.
He guess.
He see baby.
Happy he see a baby.
He immediately see a baby.
He see a baby immediately.
At the airport, he see a happy baby.

样例输出

1
2
3
4
5
6
YES
NO
NO
YES
NO
YES

提示

Please read the Problem Description carefully. Do not use your own English knowledge to construct rules.

思路

不太符合专题内容,估计是题目拉错没删,【题解】HDU-3746 Cyclic Nacklace。网上找的用stl的实现,很灵活。

代码

查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
map<string,string> mp;
map<string,bool> ste;
map<string,char> str, fun;

void init()
{
fun["n."]='0';
fun["pron."]='1';
fun["adj."]='2';
fun["adv."]='3';
fun["prep."]='4';
fun["art."]='5';
fun["vt."]='6';
fun["vi."]='7';
fun["v."]='8';

str["450"]='A'; // 介词短语
str["4520"]='A';
str["41"]='A';
str["1"]='S'; // 主/宾语
str["50"]='S';
str["520"]='S';
str["7"]='I'; // 不及物谓语
str["37"]='I';
str["6"]='T'; // 及物谓语
str["36"]='T';
str["8"]='V'; // 通用谓语
str["38"]='V';
// 句子可能的总体结构
ste["SI"]=1;
ste["STS"]=1;
ste["SV"]=1;
ste["SVS"]=1;
ste["ASI"]=1;
ste["ASTS"]=1;
ste["ASV"]=1;
ste["ASVS"]=1;
ste["SAI"]=1;
ste["SATS"]=1;
ste["SAV"]=1;
ste["SAVS"]=1;
ste["SIA"]=1;
ste["STAS"]=1;
ste["SVA"]=1;
ste["SVAS"]=1;
ste["STSA"]=1;
ste["SVSA"]=1;
}

bool check(string s){
string res="", c="";
for(int i=0; i<s.size(); i++){
c += s[i];
if(str[c] > 0){
res += str[c];
c = "";
}
}
res += c;
return ste[res];
}

string work(string s){
stringstream ss(s);
string st, ans;
while(ss >> st){
int len=st.size(), flag=0;
st[0] = tolower(st[0]);
if(st[len-1] == '.'){
flag = 1;
st.erase(--st.end());
}
if(st[len-1] == ',')
st.erase(--st.end());
ans += fun[mp[st]];
if(flag && !check(ans))
return "NO";
}
return "YES";
}

int main()
{
init(); int n, m;
while(cin >> n >> m)
{
mp.clear();
string s, s1, s2;
for(int i=0; i<n; i++){
cin >> s1 >> s2;
mp[s1] = s2;
}
cin.get();
for(int i=0; i<m; i++){
getline(cin, s);
cout << work(s) << endl;
}
}
}
_/_/_/_/_/ EOF _/_/_/_/_/