http://codeforces.com/gym/100443
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=602&page=show_problem&problem=4420

考验码农功底的时刻到了!

时间有点多。。换成hash会快不少。

(只贴出与题目有关的代码,宏定义见 GitHub

const int mx = 25;
const char token[] = ".,:;?!";

char s[mx], ts[mx];
set<string> word, stsd; // 单词字典,句子字典
string w, psts; // 单词,子句子
vector<string> sts, ans; // 句子,要输出的原句子

int main()
{
    int n, i;
    bool learn, Q;
    while (~SI(n))
    {
        if (cas) Pn();
        Pcas();
        learn = Q = false;
        word.clear(), stsd.clear(), sts.clear(), psts.clear(), ans.clear();
        word.insert("joe"), stsd.insert(" joe");
        while (SS(s), s[0] != '#')
        {
            if (s[0] == '*' || strchr(token, s[0]))
            {
                if (s[0] == '*') learn = true;
                else if (learn && Q && ans.size() >= 2)
                {
                    printf("What does the sentence \"");
                    cout << ans[0];
                    Forr(i, 1, ans.size()) cout << ' ' << ans[i];
                    printf("\" mean?\n");
                }
                Q = false;
                sts.clear(), psts.clear(), ans.clear();
            }
            else
            {
                ans.PB(s);
                for (i = 0; s[i]; ++i) ts[i] = tolower(s[i]);
                ts[i] = 0;
                w = string(ts);
                if (word.find(w) == word.end())
                {
                    if (learn) printf("What does the word \"%s\" mean?\n", s);
                    word.insert(w);
                }
                sts.PB(w);
                psts.clear();
                For(i, sts.size())
                {
                    if (i == n) break;
                    psts += " " + sts[sts.size() - 1 - i]; // 倒着取子句子
                    if (stsd.find(psts) == stsd.end())
                    {
                        Q = true;
                        stsd.insert(psts);
                    }
                }
            }
        }
    }
    return 0;
}

Comments

comments powered by Disqus