POJ 2493 - Rdeaalbe

http://poj.org/problem?id=2493

概要

人は，ある単語に対して，最初と最後の一文字ずつを変えなければ，他の文字を自由に変えても認識できるという．

N 個の単語からなる辞書が与えられるので，それを元に M 個の文に関して何通りの解釈が可能かを答える．

ただし，答えは符号付き32bit整数に収まることが保証されている．

制約

解法

単語の最初と最後の一文字を除いてソートすることで正規化して数えるだけ．

 1 #include <iostream>
 2 #include <sstream>
 3 #include <map>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9   ios::sync_with_stdio(false);
10   int T;
11   cin >> T;
12   for (int Ti = 1; Ti <= T; Ti++) {
13     int N;
14     cin >> N;
15     map<string, int> dict;
16     for (int i = 0; i < N; i++) {
17       string word;
18       cin >> word;
19       if (word.size() > 2) {
20         sort(word.begin()+1, word.begin()+word.size()-1);
21       }
22       ++dict[word];
23     }
24     int M;
25     cin >> M;
26     cin.ignore();
27     cout << "Scenario #" << Ti << ":" << endl;
28     while (M-- > 0) {
29       string line;
30       getline(cin, line);
31       int ans = 1;
32       istringstream iss(line);
33       string word;
34       while (iss >> word) {
35         if (word.size() > 2) {
36           sort(word.begin()+1, word.begin()+word.size()-1);
37         }
38         ans *= dict[word];
39       }
40       cout << ans << endl;
41     }
42     cout << endl;
43   }
44   return 0;
45 }
poj/2493.cc