zd的小窝
0%

传智杯 终端 题解

发表于

题意简述

实现四种字符串操作，具体请看题面。

题目分析

模拟题，按题意实现即可。

代码使用了 map 实现，具体地：

  • map<string,int>mp 定义一个从 string 到 int 的映射，你可以理解为定义了一个支持 mp["zd"]=1 这么访问的数组。
  • mp.find(s1) 寻找有没有下标为 s1 的数据，如果没有返回 mp.end()。
  • mp.erase(s1) 从映射里把下标为 s1 的数据删除。
  • 映射的迭代器有两部分，一部分是 ->first 代表的是下标，->second 是值。
  • 还需要实现一个按创建顺序排序，这里用了优先队列。

如果你知道了这些那代码一定就会很简单了。

代码时间

时间复杂度 $\Theta(mn \log n)$，其中 $m$ 是 ls 操作的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

/*
	Author:zd
	Status:Accept
*/

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define OK cerr<<"OK"<<endl;
int n,m,k;
map<string,int>mp;
struct node{
	int d;
	string s;
	bool operator<(const node &x)const{
		return x.d<d;//按字符串输入顺序排序 
	}
};

signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		if(s=="touch"){
			string ss;
			cin>>ss;
			mp[ss]=i;//记录顺序 
		}
		if(s=="rm"){
			string ss;
			cin>>ss;
			if(mp.find(ss)!=mp.end())//找到了，删除 
			mp.erase(ss);
		}
		if(s=="rename"){
			string s1,s2;
			cin>>s1>>s2;
			if(mp.find(s1)!=mp.end()){
				mp[s2]=mp[s1];//记录顺序，注意题面是按创建时间，也就是输入顺序排序 
				mp.erase(s1);
			}
		}
		if(s=="ls"){
			priority_queue<node>q;//排序 
			for(auto it=mp.begin();it!=mp.end();it++){//遍历
				q.push(node{it->second,it->first});//找到所有未被删除的字符串 
			}
			while(!q.empty()){
				cout<<q.top().s<<endl;//输出 
				q.pop();
			}
		}
	}
	return 0;
}

//数组开大了没有 ？开不开 long long ？多测清空了吗 ？