Kattis - whatdoesthefoxsay —— 字符串

题目：

Determined to discover the ancient mystery—the sound that the fox makes—you went into the forest, armed with a very good digital audio recorder. The forest is, however, full of animals’ voices, and on your recording, many different sounds can be heard. But you are well prepared for your task: you know exactly all the sounds which other animals make. Therefore the rest of the recording—all the unidentified noises—must have been made by the fox.

Input

The first line of input contains the number of test cases TT. The descriptions of the test cases follow:

The first line of each test case contains the recording—words over lower case English alphabet, separated by spaces. Each contains at most 100 letters and there are no more than 100 words. The next few lines are your pre-gathered information about other animals, in the format <animal> goes <sound>. There are no more than 100 animals, their names are not longer than 100 letters each and are actual names of animals in English. There is no fox goes ... among these lines.

The last line of the test case is exactly the question you are supposed to answer: what does the fox say?

Output

For each test case, output one line containing the sounds made by the fox, in the order from the recording. You may assume that the fox was not silent (contrary to popular belief, foxes do not communicate by Morse code).

Sample Input 1	Sample Output 1
1 toot woof wa ow ow ow pa blub blub pa toot pa blub pa pa ow pow toot dog goes woof fish goes blub elephant goes toot seal goes ow what does the fox say?	wa pa pa pa pa pa pow

题解：

难度不大，就是如果用C写的话，处理字符串时很烦，细节要搞好。

把其他动物的叫声放到一个队列里，对于那堆叫声，如果不能在队列里找到，则证明是狼的叫声，直接输出。

C代码如下：

 #include<cstdio>//E - E Kattis - whatdoesthefoxsay

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #include<set>

 using namespace std;

 typedef long long ll;

 char s[],a[];

 char voice[];

 char m[][];

 int main()

 {

     int t,vsum,len,cnt;

     scanf("%d",&t);

     getchar();

     while(t--)

     {

         vsum = ;

         gets(s);//读取动物的叫声

         while()

         {

             gets(a);

             if(!strcmp(a,"what does the fox say?")) break;

             len = strlen(a);

             cnt = ;

             for(int i = len-; a[i]!=' '; i--)//倒着读取动物声音，跳过无用信息

                 voice[cnt++] = a[i];

             voice[cnt] = ;

             char tmp;//处理动物声音

             len = strlen(voice);

             for(int i = ; i<=(len-)/; i++)//把动物声音调回正序

             {

                 tmp = voice[i]; voice[i] = voice[len--i]; voice[len--i] = tmp;

             }

             strcpy(m[vsum],voice);//将非狼声音放到队列中

             vsum++;

         }

         cnt = ;

         s[strlen(s)] = ' ';

         s[strlen(s)] = ;

         for(int i = ; s[i]!=; i++)

         {

             if(s[i]==' ')

             {

                 voice[cnt] = ;

                 cnt = ;

                 int j;

                 for(j = ; j<vsum; j++)

                 if(strcmp(voice,m[j])==) break;

                 if(j==vsum)

                     printf("%s ",voice);

             }

             else

                 voice[cnt++] = s[i];

         }

         putchar('\n');

     }

     return ;

 }

C++代码如下（使用STL则简便多了）：

 #include<iostream>//E - E Kattis - whatdoesthefoxsay

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #include<set>

 #include<string>

 #include<set>

 #define LL long long

 using namespace std;

 char a[],s[];//C语言开250可以过，为什么C++就不行了？而要开2500

 set<string>m;

 string voice;

 int main()

 {

     int t;

     scanf("%d",&t);

     getchar();

     while(t--)

     {

         gets(s);

         m.clear();

         while()

         {

             gets(a);

             if(!strcmp(a,"what does the fox say?")) break;

             voice = "";

             for(int i = strlen(a)-; a[i]!=' '; i--)//倒着读取动物声音，跳过无用信息

                 voice += a[i];

             char tmp;

             for(int i = ,len = voice.size(); i<=(len-)/; i++)//把动物声音调回正序

             {

                 tmp = voice[i]; voice[i] = voice[len--i]; voice[len--i] = tmp;

             }

             m.insert(voice);

         }

         s[strlen(s)] = ' ';

         s[strlen(s)] = ;

         voice = "";

         for(int i = ,len = strlen(s); i<len; i++)

         {

             if(s[i]==' ')

             {

                 if(m.find(voice)==m.end())

                     cout<<voice<<' ';

                 voice = "";

             }

             else

                 voice += s[i];

         }

         putchar('\n');

     }

     return ;

 }

Fox