題目鏈接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3700 Ever Dream

---

Time Limit:?2 Seconds ?????Memory Limit:?65536 KB

---



"Ever Dream" played by Nightwish is my favorite metal music. The lyric (see Sample Input) of this song is much more like a poem. Every people may have their own interpretation for this song depending on their own experience in the past. For me, it is a song about pure and unrequited love filled with innocence, willingness and happiness. I believe most people used to have or still have a long story with someone special or something special. However, perhaps fatefully, life is totally a joke for us. One day, the story ended and became a dream in the long night that would never come true. The song touches my heart because it reminds me the dream I ever had and the one I ever loved.

Today I recommend this song to my friends and hope that you can follow your heart. I also designed a simple algorithm to express the meaning of a song by several key words. There are only 3 steps in this algorithm, which are described below:

Step 1:?Extract all different words from the song and counts the occurrences of each word. A word only consists of English letters and it is case-insensitive.

Step 2:?Divide the words into different groups according to their frequencies (i.e. the number of times a word occurs). Words with the same frequency belong to the same group.?

Step 3:?For each group, output the word with the longest length. If there is a tie, sort these words (not including the words with shorter length) in alphabetical order and output the penultimate one. Here "penultimate" means the second to the last. The word with higher frequency should be output first and you don't need to output the word that just occurs once in the song.?

Now given the lyric of a song, please output its key words by implementing the algorithm above.

Input

The first line of input is an integer?T?(T?< 50) indicating the number of test cases. For each case, first there is a line containing the number?n?(n?< 50) indicating that there are?n?lines of words for the song. The following?n?lines contain the lyric of the song. An empty line is also counted as a single line. Any ASCII code can occur in the lyric. There will be at most 100 characters in a single line.

Output

For each case, output the key words in a single line. Words should be in lower-case and separated by a space. If there is no key word, just output an empty line.

Sample Input

1 29 Ever felt away with me Just once that all I need Entwined in finding you one day Ever felt away without me My love, it lies so deep Ever dream of me Would you do it with me Heal the scars and change the stars Would you do it for me Turn loose the heaven within I'd take you away Castaway on a lonely day Bosom for a teary cheek My song can but borrow your grace Come out, come out wherever you are So lost in your sea Give in, give in for my touch For my taste for my lust Your beauty cascaded on me In this white night fantasy "All I ever craved were the two dreams I shared with you. One I now have, will the other one ever dream remain. For yours I truly wish to be."

Sample Output

for ever with dream 題意：給出一首歌，由n行字符串字符串，每行含有一些單詞，求出這些單詞里面的關(guān)鍵詞。 關(guān)鍵詞由以下規(guī)則生成：1.提取出所有不同的單詞和每個單詞出現(xiàn)的次數(shù)，單詞只有英文字母組成，并且不區(qū)分大小寫。 2.把這些單詞分成若干組，出現(xiàn)相同次數(shù)的單詞分成一個組 3.對于沒一個組，輸出長度最長的單詞；如果有多個單詞長度相同，則先按字典序排序，然后輸出倒數(shù)第二個。 注意：像 I'd 這樣的簡寫認(rèn)為是一個單詞，和題意說的有點不一樣，一直WA在這里。 知道了這些，就可以AC了。 #include <iostream> #include <set> #include <map> #include <string> using namespace std;inline bool Is_alpha(char ch) { // 判斷字符是不是字母if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))return true;return false; }map <string, int> mp; map <string, int>::iterator it; set <string> ans;int main() {int T, n;string s;cin >> T;while(T--) {cin >> n;cin.ignore();mp.clear();int max_cnt = -1;for(int i = 0; i < n; i++) {getline(cin, s);if(s == "") continue;string str = "";for(int j = 0; j < (int)s.size(); j++) {if(!Is_alpha(s[j])) {if(s[j] != '\'') { // 如果不是單引號，I'd 看做一個單詞if(str.length() > 0) {if(mp[str] == 0) mp[str] = 1;else mp[str]++;max_cnt = max(max_cnt, mp[str]);str = "";}}else str += s[j];}else {if(s[j] >= 'A' && s[j] <= 'Z')s[j] = (s[j] + 32);str += s[j];}}if(str.length() > 0) {if(mp[str] == 0) mp[str] = 1;else mp[str]++;max_cnt = max(max_cnt, mp[str]);str = "";}}int flag = 0;for(int i = max_cnt; i >= 2; i--) {ans.clear();int max_len = 0;for(it = mp.begin(); it != mp.end(); it++) {if(it->second == i) { // 找出長度為i的最長字符串if((it->first.length()) > max_len) {max_len = it->first.length();ans.clear();ans.insert(it->first);}else if(it->first.length() == max_len)ans.insert(it->first);}}if(ans.size() == 1) {if(flag) cout << " ";cout << *ans.begin();flag = 1;}else {if(ans.size() >= 2) {set <string> ::iterator sit = ans.end();sit--;sit--;if(flag) cout << " ";cout << *sit;flag = 1;}}}cout << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的ZOJ 3700 Ever Dream（模拟）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。