【STL】Saving the Universe
http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=575
Description
The urban legend goes that if you go to the Google homepage and search for "Google", the universe will implode. We have a secret to share... It is true! Please don't try it, or tell anyone. All right, maybe not. We are just kidding.
The same is not true for a universe far far away. In that universe, if you search on any search engine for that search engine's name, the universe does implode!
To combat this, people came up with an interesting solution. All queries are pooled together. They are passed to a central system that decides which query goes to which search engine. The central system sends a series of queries to one search engine, and can switch to another at any time. Queries must be processed in the order they're received. The central system must never send a query to a search engine whose name matches the query. In order to reduce costs, the number of switches should be minimized.
Your task is to tell us how many times the central system will have to switch between search engines, assuming that we program it optimally.
Input
The first line of the input file contains the number of cases, N. N test cases follow.
Each case starts with the number S -- the number of search engines. The next S lines each contain the name of a search engine. Each search engine name is no more than one hundred characters long and contains only uppercase letters, lowercase letters, spaces, and numbers. There will not be two search engines with the same name.
The following line contains a number Q -- the number of incoming queries. The next Q lines will each contain a query. Each query will be the name of a search engine in the case.
Limits:
0 < N ≤ 20
2 ≤ S ≤ 100
0 ≤ Q ≤ 1000
Output
For each input case, you should output:
Case #X: Y
where X is the number of the test case and Y is the number of search engine switches. Do not count the initial choice of a search engine as a switch.
Sample Input
Original
Transformed
2
5
Yeehaw
NSM
Dont Ask
B9
Googol
10
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol
5
Yeehaw
NSM
Dont Ask
B9
Googol
7
Googol
Dont Ask
NSM
NSM
Yeehaw
Yeehaw
Googol
Sample Output
Original
Transformed
Case #1: 1
Case #2: 0
#if __GNUC__>2
#include <ext/hash_set>
#include <ext/hash_map>
using namespace __gnu_cxx;
#else
#include <hash_set>
#include <hash_map>
using namespace stdext;
#endif
//hash_set
#include<cstdio>
#include<string>
using namespace std;
/*-------------------------------------------*/
/*
* hash_map hash
*string hash
*/
class str_hash
{
public:
size_t operator()(const string& str) const
{
unsigned long __h = 0;
for (size_t i = 0 ; i < str.size() ; ++i)
__h = 5*__h + str[i];
return size_t(__h);
}
};
/*-------------------------------------------*/
/*
* hash_map )
*( key hash
*/
class str_compare
{
public:
bool operator()(const string& str1,const string& str2)const
{
return str1==str2;
}
};
/*-------------------------------------------*/
int main()
{
int T,n,m;
string s;
char ch[105];
scanf("%d", &T);
for(int t=1; t<=T; ++t)
{
scanf("%d", &n);
getchar();
for(int i=0; i<n; ++i)
gets(ch);
scanf("%d", &m);
getchar();
hash_set<string,str_hash,str_compare> st;
int count = 0;
for(int i=0; i<m; ++i)
{
gets(ch);
s=string(ch);
if (st.find(s) == st.end())
{
if (st.size() == n-1)
{
st.clear();
count++;
}
st.insert(s);
}
}
printf("Case #%d: %d
", t, count);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Access Request, Session and Application in Struts2If we want to use request, Session and application in JSP, what should we do? We can obtain Map type objects such as Req...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.