hdu 4096 Universal Question Answering System-白红宇

hdu 4096 Universal Question Answering System

阅读量：5334 次

发布时间：2019-06-15

本文共 5953 字，大约阅读时间需要 19 分钟。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4096

神坑一：名词和动词可能拼写相同，所以要区分一下词性

神坑二（猜想）：提问中可能有问一些诸如“are Z Z?” 然后在原文中却压根没提到Z的...

个人的具体做法：

通过map来给每一个读进来的单词一个数字编号

词性的区分通过在单词前面加前缀v和n来实现【网上很多博客的写法是用两个map来搞都可以】

对于每个询问直接暴力dfs【本来想求传递闭包后来发现那样复杂度更高】

上AC代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         using namespace std;const int maxv = 2100;const int maxe = 20000;struct edge{
   int to, next;}E[maxe];int head[maxv];int si;int vis[maxv];void addedge(int u, int v){    E[si].to = v;    E[si].next = head[u];    head[u] = si++;}bool dfs(int x, int y){    if(x == y)        return true;    vis[x] = 1;    for(int i = head[x]; i != -1; i = E[i].next)    {        if(vis[E[i].to] == 1)            continue;        if(dfs(E[i].to, y))        {            return true;        }    }    return false;}char buf[50100][110];map
          
            id;int nameid;int main(){ //freopen("in.txt", "r", stdin); int T; scanf("%d", &T); int kase = 0; while(T--) { printf("Case #%d:\n", ++kase); id.clear(); nameid = 1; si = 0; memset(E, -1, sizeof(E)); memset(head, -1, sizeof(head)); bool kaseend = false; while(!kaseend) { int loc = 0; while(true)//如果读不到标点符号就一直循环 { scanf("%s", buf[loc++]); int len = strlen(buf[loc-1]);//the last word's len if(buf[loc-1][len-1] == '!')//读到感叹号就退出 { printf("\n"); kaseend = true; //kase终止标记 break; } else if(buf[loc-1][len-1] == '.')//事实陈述句 { if(loc == 3) { string a = buf[0]; buf[loc-1][len-1] = '\0';//去掉那个标点 string b = buf[2]; string mode = buf[1]; if(mode == "can")//对于词性的处理 { a = "n" + a; b = "v" + b; } else { a = "n" + a; b = "n" + b; } if(!id.count(a))//map类的函数，判断map中a有没有出现过 { id[a] = nameid++; } if(!id.count(b)) { id[b] = nameid++; } addedge(id[a], id[b]); } else if(loc == 6) { string a = buf[3]; buf[loc-1][len-1] = '\0'; string b = buf[5]; string mode = buf[4]; if(mode == "can") { a = "v" + a; b = "v" + b; } else { a = "v" + a; b = "n" + b; } if(!id.count(a)) { id[a] = nameid++; } if(!id.count(b)) { id[b] = nameid++; } addedge(id[a], id[b]); } break; } else if(buf[loc-1][len-1] == '?')//读到询问 { if(loc == 3) { string a = buf[1]; buf[loc-1][len-1] = '\0'; string b = buf[2]; string mode = buf[0]; if(mode == "can") { a = "n" + a; b = "v" + b; } else { a = "n" + a; b = "n" + b; } if(!id.count(a))//也给每一个出现的东西一个nameid { id[a] = nameid++; } if(!id.count(b)) { id[b] = nameid++; } memset(vis, 0, sizeof(vis)); if(dfs(id[a], id[b])) { printf("Y"); } else printf("M"); } else if(loc == 6) { string a = buf[4]; buf[loc-1][len-1] = '\0'; string b = buf[5]; string mode = buf[0]; if(mode == "can") { a = "v" + a; b = "v" + b; } else { a = "v" + a; b = "n" + b; } if(!id.count(a)) { id[a] = nameid++; } if(!id.count(b)) { id[b] = nameid++; } memset(vis, 0, sizeof(vis)); if(dfs(id[a], id[b])) { printf("Y"); } else printf("M"); } break; } } } } return 0;}

碎碎念：

趁期末考还没正式到来在着手解决一些“历史遗留的弃疗问题”...

说这道题是坑题一点都不为过

今年九月份打练习赛的时候没有做出来

然后看了题解才发现那个词性的神坑，结果还是没过

看了网上的题解

本身就很少

而且过的人好多也不知道自己第一次是怎么wa的

让我很是无奈

于是弃疗

最近数据结构调自己一个五百行的huffman程序

那才是真正的“大模拟”调了我好几天。。。

之后我就发现自己看一般的模拟都不觉得恶心了Orz

于是就想动手艹这题

A了以后发现之前自己dfs写搓了

如下：

bool dfs(int x, int y){    if(vis[x] == 1)        return false;    bool flag = false;    vis[x] = 1;    for(int i = head[x]; i != -1; i = E[i].next)    {        if(E[i].to == y || dfs(E[i].to, y))        {            flag = true;            break;        }    }    return flag;}

之前觉得姿势是丑了点但应该没问题

然后做完才发现它没法正确判断“A是A”这种自己是自己的情况

这个故事教育我们姿势这种东西能优雅的要尽量优雅一点

另一个问题是

原来我在读到询问句后

不再给新出现的单词nameid

而是直接判断这个单词有没有在陈述句中出现过

如果没有直接判M

然后WA了

改过来之后就过了

所以才有了上面猜想的神坑二

上WA代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          using namespace std;const int maxv = 2100;const int maxe = 20000;struct edge{ int to, next;}E[maxe];int head[maxv];int si;int vis[maxv];void addedge(int u, int v){ E[si].to = v; E[si].next = head[u]; head[u] = si++;}bool dfs(int x, int y){ if(x == y) return true; vis[x] = 1; for(int i = head[x]; i != -1; i = E[i].next) { if(vis[E[i].to] == 1) continue; if(dfs(E[i].to, y)) { return true; } } return false;}char buf[50100][110];map
           
             id;int nameid;int main(){ //freopen("in.txt", "r", stdin); int T; scanf("%d", &T); int kase = 0; while(T--) { printf("Case #%d:\n", ++kase); id.clear(); nameid = 1; si = 0; memset(E, -1, sizeof(E)); memset(head, -1, sizeof(head)); bool kaseend = false; while(!kaseend) { int loc = 0; while(true) { scanf("%s", buf[loc++]); int len = strlen(buf[loc-1]);//the last word's len if(buf[loc-1][len-1] == '!') { printf("\n"); kaseend = true; break; } else if(buf[loc-1][len-1] == '.') { if(loc == 3) { string a = buf[0]; buf[loc-1][len-1] = '\0'; string b = buf[2]; string mode = buf[1]; if(mode == "can") { a = "n" + a; b = "v" + b; } else { a = "n" + a; b = "n" + b; } if(!id.count(a)) { id[a] = nameid++; } if(!id.count(b)) { id[b] = nameid++; } addedge(id[a], id[b]); } else if(loc == 6) { string a = buf[3]; buf[loc-1][len-1] = '\0'; string b = buf[5]; string mode = buf[4]; if(mode == "can") { a = "v" + a; b = "v" + b; } else { a = "v" + a; b = "n" + b; } if(!id.count(a)) { id[a] = nameid++; } if(!id.count(b)) { id[b] = nameid++; } addedge(id[a], id[b]); } break; } else if(buf[loc-1][len-1] == '?') { if(loc == 3) { string a = buf[1]; buf[loc-1][len-1] = '\0'; string b = buf[2]; string mode = buf[0]; if(mode == "can") { a = "n" + a; b = "v" + b; } else { a = "n" + a; b = "n" + b; } memset(vis, 0, sizeof(vis)); if(id.count(a) && id.count(b) && dfs(id[a], id[b])) { printf("Y"); } else printf("M"); } else if(loc == 6) { string a = buf[4]; buf[loc-1][len-1] = '\0'; string b = buf[5]; string mode = buf[0]; if(mode == "can") { a = "v" + a; b = "v" + b; } else { a = "v" + a; b = "n" + b; } memset(vis, 0, sizeof(vis)); if(id.count(a) && id.count(b) && dfs(id[a], id[b])) { printf("Y"); } else printf("M"); } break; } } } } return 0;}