首页 > ACM题库 > HDU-杭电 > hdu 2698 URL[解题报告]C++
2014
02-13

hdu 2698 URL[解题报告]C++

URL

问题描述 :

WHU ACM Team is working on a brand new web browser named "Whu-Super-Browser". You’re in response for a
powerful feature: recording the previous addresses. Moreover, when a string is inputted, the browser will display all the
addresses start with it. The addresses shall be sorted by visited times, in descending order. This feature is very useful to
users.
Can you complete it?

There’re two kinds of operations:
Visit [url_str] : visit a website with the URL: [url_str].
Display [str] : display all addresses start with [str] and sort them by visited times, in descending order. If two addresses
have the same visited times, then sort them in the lexicographical order.

输入:

The input consists of multiple test cases. The first line of input contains an integer T, which is the number of test cases.

Each test case is on several lines.
The first line of each test case consists of an integer N.
Each of the following N lines consists of an operation, Visit or Display.

[Technical Specification]
T is an integer, and T <= 10.
N is an integer, and 1 <= N <=100.
There’s NO blank line between test cases.
[url_str] and [str] only contains lower case letters ‘a’ – ‘z’, ‘.’, ‘/’, ‘:’.
The length of [url_str] and [str] is greater than 0 and won’t exceed 100.

输出:

The input consists of multiple test cases. The first line of input contains an integer T, which is the number of test cases.

Each test case is on several lines.
The first line of each test case consists of an integer N.
Each of the following N lines consists of an operation, Visit or Display.

[Technical Specification]
T is an integer, and T <= 10.
N is an integer, and 1 <= N <=100.
There’s NO blank line between test cases.
[url_str] and [str] only contains lower case letters ‘a’ – ‘z’, ‘.’, ‘/’, ‘:’.
The length of [url_str] and [str] is greater than 0 and won’t exceed 100.

样例输入:

1 
10 
Visit http://acm.whu.edu.cn 
Visit http://acm.pku.edu.cn 
Visit http://acm.timus.ru 
Visit http://acm.whu.edu.cn 
Visit http://acm.whu.edu.cn 
Visit http://acm.pku.edu.cn 
Display http://acm 
Visit baidu.com 
Visit www.whu.edu.cn 
Display b 

样例输出:


http://acm.whu.edu.cn


http://acm.pku.edu.cn


http://acm.timus.ru

baidu.com 


http://acm.hdu.edu.cn/showproblem.php?pid=2698
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
//#include<fstream>
using namespace std;
struct comp
{
string a;
int b;
}val;
bool inorder(comp a,comp b)
{
if(a.b!=b.b) return a.b>b.b;
return a.a<b.a;
}
int main()
{
//ifstream cin("aaa.txt");
int t,n;
cin>>t;
while(t–)
{
map<string,int> a;
map<string,int>::iterator it;
string c,d;
int i;
cin>>n;
while(n–)
{
cin>>c>>d;
vector<comp> e;
if(c=="Visit") ++a[d];
if(c=="Display")
{
for(it=a.begin();it!=a.end();it++)
{
if((*it).first.find(d)==0)
{
val.a=(*it).first,val.b=(*it).second;
e.push_back(val);
}
}
sort(e.begin(),e.end(),inorder);
for(i=0;i<e.size();i++)
{
cout<<e[i].a<<endl;
}
cout<<endl;
}
}
}
return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=2698 解题转自:http://hi.baidu.com/wtkqmvvybcbgnpd/item/59bfed3ce58a70fa2784f4b7


  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。