Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

字典树,杀鸡焉用牛刀!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Posted by lolihunter at 2009-11-27 19:30:33 on Problem 3746 and last updated at 2009-11-30 16:37:11
这题有很多人说是字典树,我更愿意把它放在我最开始也是想用字典树做的,但是题目中一句话(Any two parts of the sentence cannot intersect.)说各个部分不交叉,名词,代词就是主语宾语,动词就是谓语。这提醒我这题可能没有那么麻烦。事实证明,用字典树有点杀鸡用牛刀了。
把词性数字化0-8;按照要求建立词性邻接矩阵。如果2个词性可以相邻,矩阵值为1,否则为0。字典中单词按字典序排序。
输入句子后,单词分割并小写化。把单词按词性转化成数字。看当前单词与上一个单词词性是否邻接即可,注意介词短语单独分析。分类代码中注释很详细。
注意几点:
1.句子中,不是字母的都是无用字符。
2.介词短语中,名词不可以用形容词修饰。
3.谓语动词唯一
4.抛弃已有的语法观点,坚持题目要求。
5 句子最后一个词必须是不及物动词或者名词。
6句子开头必须是介词或者名词或者代词或者冠词。
7介词短语是单独分析的

0-7对应题中给出的词性的顺序。8是V.
以下是邻接矩阵
    g[9][9]={0,0,0,1,1,0,1,1,1,
             0,0,0,1,1,0,1,1,1,
             1,0,0,0,0,0,0,0,0,
             0,0,0,0,0,0,1,1,1,
             0,1,0,0,0,1,0,0,0,
             1,0,1,0,0,0,0,0,0,
             0,1,0,0,1,1,0,0,0,
             0,0,0,0,1,0,0,0,0,
             0,1,0,0,1,1,0,0,0
            };
详细代码:
http://hi.baidu.com/%E5%B0%91%E4%B8%80%E6%96%A4/blog/item/ec4b7819040009be4aedbcbd.html

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator