首页 > ACM题库 > HDU-杭电 > HDU 4096-Universal Question Answering System[解题报告]HOJ
2015
04-16

HDU 4096-Universal Question Answering System[解题报告]HOJ

Universal Question Answering System

问题描述 :

  Every student needs help from getting new knowledge by asking questions. Surveys are suggesting that some similar questions are repeated frequently. So it will be nice to develop an automatic question-answering system to answer these questions. Your algorithm should not have any prior knowledge, but it must be able to read sentences and remember the mentioned facts. Whenever the question is asked about such a fact, the system has to answer it properly.

输入:

  The input consists of many dialogues.
  There is a single positive integer T on the first line of input. (T <= 500, but note that 95% of them are relatively small) It denotes the number of following dialogues. Each dialogue includes one or more lines. Each line contains one sentence: either a statement or a question. Statements end with a dot character (.) while questions end with a question mark (?). There is one extra line after each dialogue. That line ends with an exclamation mark (!). The definitions of the statements and questions will be discussed later.

Sentences can contain words, spaces and punctuation characters. All words contain only Latin letters and are case-sensitive. Unlike the normal English writing rules, the first letter of a sentence should keep lowercase unless the first word itself should begin with a capital letter. There are no extra spaces between words. No word will have more than 10 characters. There will be at most 1000 lines per dialogue.
Statements
Each statement has one of the following forms:

noun_phrase are noun_phrase.
noun_phrase can verb_phrase.
everything which can verb_phrase can verb_phrase.
everything which can verb_phrase are noun_phrase.

noun_phrase and verb_phrase are both single word. The meanings of the four forms are:

A are B: If X is A, then X is B.
A can B: If X is A, then X has the ability to B.
everything which can A can B: If X has the ability to A, X has the ability to B.
everything which can A are B: If X has the ability to A, X is B.

Questions
Each question has one of the following forms:

are noun_phrase noun_phrase?
can noun_phrase verb_phrase?
can everything which can verb_phrase verb_phrase?
are everything which can verb_phrase noun_phrase?

They are the question form of the statements.

In each test case, the number of different noun phrases will not exceed 100; the number of different verb phrases will not exceed 100.

输出:

  The input consists of many dialogues.
  There is a single positive integer T on the first line of input. (T <= 500, but note that 95% of them are relatively small) It denotes the number of following dialogues. Each dialogue includes one or more lines. Each line contains one sentence: either a statement or a question. Statements end with a dot character (.) while questions end with a question mark (?). There is one extra line after each dialogue. That line ends with an exclamation mark (!). The definitions of the statements and questions will be discussed later.

Sentences can contain words, spaces and punctuation characters. All words contain only Latin letters and are case-sensitive. Unlike the normal English writing rules, the first letter of a sentence should keep lowercase unless the first word itself should begin with a capital letter. There are no extra spaces between words. No word will have more than 10 characters. There will be at most 1000 lines per dialogue.
Statements
Each statement has one of the following forms:

noun_phrase are noun_phrase.
noun_phrase can verb_phrase.
everything which can verb_phrase can verb_phrase.
everything which can verb_phrase are noun_phrase.

noun_phrase and verb_phrase are both single word. The meanings of the four forms are:

A are B: If X is A, then X is B.
A can B: If X is A, then X has the ability to B.
everything which can A can B: If X has the ability to A, X has the ability to B.
everything which can A are B: If X has the ability to A, X is B.

Questions
Each question has one of the following forms:

are noun_phrase noun_phrase?
can noun_phrase verb_phrase?
can everything which can verb_phrase verb_phrase?
are everything which can verb_phrase noun_phrase?

They are the question form of the statements.

In each test case, the number of different noun phrases will not exceed 100; the number of different verb phrases will not exceed 100.

样例输入:

1
flies can fly.
flies are insects.
everything which can fly are animals.
are everything which can fly insects?
are flies animals?
can flies eat?
everything which can fly can eat.
can flies eat?
Bye!

样例输出:

Case #1:
MYMY

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <vector>
using namespace std;
const int N = 101;
map <string,int> noun;
map <string,int> verb;
int n,m;
string res,wd[20];
vector <int> adj[N*5];
bool visited[N*5];
int getNounId(string str){
    if (noun[str]==0) noun[str] = ++n;
    return noun[str];
}
int getVerbId(string str){
    if (verb[str]==0){
        ++m;
        verb[str] = m + N;
    }
    return verb[str];
}
void statements(int l){
    wd[l-1] = wd[l-1].substr(0,wd[l-1].length()-1);
    int v,u;
    if (l==3){
        v = getNounId(wd[0]);
        if (wd[1]=="are") u = getNounId(wd[2]);
        else u = getVerbId(wd[2]);
    }else{
        v = getVerbId(wd[3]);
        if (wd[4]=="are") u = getNounId(wd[5]);
        else u = getVerbId(wd[5]);
    }
    adj[v].push_back(u);
}
queue <int> q;
bool bfs(int v,int u){
    if (v==u) return true;
    while (!q.empty()) q.pop();
    visited[v] = true;
    q.push(v);
    while (!q.empty()){
        int k = q.front(); q.pop();
        for (int i=0;i<(int)adj[k].size();i++){
            int r = adj[k][i];
            if (r==u) return true;
            if (!visited[r]){
                q.push(r);
                visited[r] = true;
            }
        }
    }
    return false;
}
void questions(int l){
    wd[l-1] = wd[l-1].substr(0,wd[l-1].length()-1);
    int v,u;
    if (l==3){
        v = noun[wd[1]];
        if (wd[0]=="are"){
            if (wd[1]==wd[2]){
                res= res + 'Y';
                return ;
            }
            u = noun[wd[2]];
        }
        else u = verb[wd[2]];
    }else{
        v = verb[wd[4]];
        if (wd[0]=="are") u = noun[wd[5]];
        else{
            if (wd[4]==wd[5]){
                res = res + 'Y';
                return ;
            }
            u = verb[wd[5]];
        }
    }
    if (v==0 || u==0) {res=res+'M';return;}
    memset(visited,false,sizeof(visited));
    if (bfs(v,u)) res = res + 'Y';
    else res = res + 'M';
}
void read(){
    int l;
    char chr[80];
    while (gets(chr)){
        l = 0;
        string str(chr);
        istringstream is(str);
        while (is>>wd[l])   l++;
        //for (int i=0;i<l;i++)   cout<<wd[i]<<' ';puts("");
        if (wd[l-1][wd[l-1].length()-1] == '.') statements(l);
        else if (wd[l-1][wd[l-1].length()-1] == '?') questions(l);
        else break;
    }
}
int main(){
   // freopen("test.in","r",stdin);
    int T; cin>>T;
    char ch = getchar(); while (ch!='\n') ch = getchar();
    for (int it=0;it<T;++it){
        printf("Case #%d:\n",it+1);
        n = m = 0;
        res = "";
        noun.clear();
        verb.clear();
        for (int i=0;i<N*5;i++) adj[i].clear();
        read();
        puts(res.c_str());
    }
    return 0;
}

  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  2. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  3. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。