题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4096
神坑一：名词和动词可能拼写相同，所以要区分一下词性
神坑二（猜想）：提问中可能有问一些诸如“are Z Z?” 然后在原文中却压根没提到Z的...
个人的具体做法：
通过map来给每一个读进来的单词一个数字编号
词性的区分通过在单词前面加前缀v和n来实现【网上很多博客的写法是用两个map来搞 都可以】
对于每个询问 直接暴力dfs【本来想求传递闭包后来发现那样复杂度更高】
上AC代码：
#include <cstring> #include <iostream> #include <algorithm> #include <set> #include <map> 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<string, int> id; int nameid; int main() { //freopen("in.txt", "r", stdin); int T; scanf("%d", &T); int kase = 0; while(T--) { printf("Case #%d: ", ++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(" "); kaseend = true; //kase终止标记 break; } else if(buf[loc-1][len-1] == '.')//事实陈述句 { if(loc == 3) { string a = buf[0]; buf[loc-1][len-1] = ' ';//去掉那个标点 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] = ' '; 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] = ' '; 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] = ' '; 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 <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <set> #include <map> 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<string, int> id; int nameid; int main() { //freopen("in.txt", "r", stdin); int T; scanf("%d", &T); int kase = 0; while(T--) { printf("Case #%d: ", ++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(" "); kaseend = true; break; } else if(buf[loc-1][len-1] == '.') { if(loc == 3) { string a = buf[0]; buf[loc-1][len-1] = ' '; 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] = ' '; 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] = ' '; 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] = ' '; 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; }