uva 409 - Excuses, Excuses!
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid;=8&page;=show_problem&problem;=350 题意:给出k个key word,e个借口...找出包含key word最多的借口,即为最坏的借口。匹配补区分大小写&&同一个key word算多次。 思路:需要注意的是因为不区分大小写,需要都转化成大写或者小写。。但是输出的时候要输出原始的。。所以要另外存一份。
/* ***********************************************
Author :111qqz
Created Time :2016年01月22日 星期五 17时58分02秒
File Name :code/uva/409.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6string str[50];
7int k,e;
8int num[50];
9set<string>se;
1struct node
2{
3 string exc;
4 string ori;
5 int num;
6 bool operator<(node b)const
7 {
8 return num>b.num;
9 }
10}ex[50];
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("code/in.txt","r",stdin);
5 #endif
6 int cas = 0 ;
7 while (scanf("%d %d",&k,&e)!=EOF)
8 {
9 se.clear();
10 ms(num,0);
11 printf("Excuse Set #%d\n",++cas);
1 for ( int i = 0 ; i < k ; i++)
2 {
3 cin>>str[i];
4 int len = str[i].length();
5 for ( int j = 0 ; j < len ;j++)
6 {
7 str[i][j] = tolower(str[i][j]);
8 }
9 se.insert(str[i]);
10 }
11 getchar();
12// for ( int i = 0 ; i < k ;i++) cout<<"str[i]:"<<str[i]<<endl;
13 for ( int i = 0 ; i < e ; i++)
14 {
15 getline(cin,ex[i].exc);
16 ex[i].ori=ex[i].exc;
17 int len = ex[i].exc.length();
18 for ( int j = 0 ; j < len ; j++)
19 {
20 ex[i].exc[j] = tolower(ex[i].exc[j]);
21 if (ex[i].exc[j]<'a'||ex[i].exc[j]>'z')
22 ex[i].exc[j]=' '; //把非字母部分都转化成空格.
23 }
24 }
// for ( int i = 0 ; i < e ; i++) cout<<"exc[i]:"<<ex[i].exc<<endl;
int ans = -1;
1 for ( int i = 0 ; i < e ;i++)
2 {
3 int cnt = 0 ;
4 string cpy = ex[i].exc;
5 int pos = 0 ;
6 while (pos!=-1)
7 {
8 pos = cpy.find(' ');
9 string tmp = cpy.substr(0,pos-0);
10 if (se.count(tmp)==1) cnt++;
11 cpy.erase(0,pos+1);
12 //cout<<i<<"cpy:"<<cpy<<cpy.length()<<endl;
13 }
1 ex[i].num=cnt;
2 }
3// for ( int i = 0 ; i < e ; i++) cout<<"num[i]:"<<ex[i].num<<endl;
4 sort(ex,ex+e);
5 for ( int i = 0 ; i < e ; i++)
6 {
7 if (ex[i].num==ex[0].num)
8 {
9 cout<<ex[i].ori<<endl;
10 }
11 }
12 cout<<endl;
13 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}