本期主要讲解 vector
、map
两个 STL
容器。
知识点:
首先,引入两种数组的区别:
-
静态数组,指提前声明需要多少内存的数组,是连续的;
-
而动态数组则是在插入元素时临时指定存储空间,不要求连续。
STL vector
是一个动态数组,下标默认从 \(0\) 开始。它支持的操作如下:
-
定义:一维
vector<TYPE> NAME
,二维vector<TYPE> NAME[SIZE]
,一般不定义vector
套vector
。 -
插入:
NAME.push_back(VAL)
。 -
长度:
NAME.size()
。 -
访问:
NAME[POS]
。(注意不是 \(O(1)\))
STL map
则是一个有序键值对,在数学上被称为映射,其中的键(\(key\))唯一,而值(\(value\))不唯一。同时 map
具有去重的性质。
它支持的操作如下:
-
定义:
map<TYPE,TYPE> NAME
; -
赋值:
map[KEY]=VAL
; -
长度:
NAME.size()
; -
统计:
NAME.count(VAL)
。
(更多 vector
和 map
的操作请访问 zh.cppreference.com)
例题
T1
维护一个 map
,记录每个字符串的编号,最后输出长度即可。
#include<bits/stdc++.h>
using namespace std;
int n;
map<string,int> m;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
string s; cin>>s;
m[s]=i;
}
cout<<m.size();
return 0;
}
T2
题目有点绕,其实就是要你求出字符串 \(s\) 中最短的子串 \(t\) 的长度。因为 \(n\) 很小,所以考虑 \(O(n^3)\) 的枚举。
循环 \(1 \sim n\) 枚举 \(t\) 的长度 \(k\),同时循环 \(1 \sim n-k+1\) 枚举 \(t\) 的起点,利用 substr
\(O(n)\) 地求出 \(t\),若 \(t\) 自始至终只出现了一次,则当前的 \(k\) 即为答案。
#include<bits/stdc++.h>
using namespace std;
int n,ans;
string s;
map<string,int> m;
int main(){
cin>>n>>s;
for(int i=1;i<=n;i++){
bool f=0;
for(int j=0;i+j-1<n;j++){
string t=s.substr(j,i);
if(m[t]!=0){
f=1;
break;
}
m[t]++;
}
if(!f){
cout<<i<<'\n'; break;
}
}
return 0;
}
T4
维护一个 map
,对于每个字符串,若它在 map
中未出现,则输出 YES
,反之输出 NO
,同时将其插入 map
中。
我用的是 set
,更为简便。
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
set<string> x;
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>s,cout<<(x.count(s)?"YES\n":"NO\n"),x.insert(s);
return 0;
}
习题
T5
开个结构体,记录名称 \(s\) / 地址 \(ip\) / (针对命令的)指向的服务器地址 \(p\)。
遍历每条命令,循环查找与其对应的服务器,将服务器名称存入 \(p\) 中。
最后按格式输出每条命令的 \(s\)、\(ip\) 和 \(p\)。
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
string name,p,ip;
}a[2031];
int main(){
cin>>n>>m;
for(int i=1;i<=n+m;i++)
cin>>a[i].name>>a[i].ip;
for(int i=n+1;i<=n+m;i++){
for(int j=1;j<=n;j++){
string t=a[j].ip+";";
if(t==a[i].ip)
a[i].p=a[j].name;
}
}
for(int i=n+1;i<=n+m;i++)
cout<<a[i].name<<" "<<a[i].ip<<" #"<<a[i].p<<"\n";
return 0;
}
T6
我们令原字符串为 \(s\):
-
对于操作
1
,令新字符串为 \(t\),则输出 \(s+t\); -
对于操作
2
,令 \(s \gets s.\text{substr}(a,b)\),并输出 \(s\); -
对于操作
3
,令新字符串为 \(t\),则 \(s.\text{insert}(a,b)\),并输出 \(s\); -
对于操作
4
,令新字符串为 \(t\),若 \(s.\text{find}(t) \neq \text{string::npos}\),则输出 \(s.\text{find}(t)\),否则输出 \(-1\)。
#include<bits/stdc++.h>
using namespace std;
int q,op,a,b;
string f,s;
int main(){
cin>>q>>f;
while(q--){
cin>>op;
if(op==1)
cin>>s,f+=s,cout<<f<<'\n';
else if(op==2)
cin>>a>>b,f=f.substr(a,b),cout<<f<<'\n';
else if(op==3)
cin>>a>>s,f.insert(a,s),cout<<f<<'\n';
else{
cin>>s;
if(f.find(s)!=string::npos) cout<<f.find(s)<<'\n';
else cout<<"-1\n";
}
}
return 0;
}
T7
运用 map
存储每一个数,若它是第一次出现则输出并标记。
用 unordered_map
更佳。
#include<bits/stdc++.h>
using namespace std;
int T;
unordered_map<int,bool> ump;
int main(){
ios::sync_with_stdio(0); cin.tie(nullptr);
cin>>T;
while(T--){
ump.clear();
int n; cin>>n;
for(int i=1;i<=n;i++){
int x; cin>>x;
if(ump[x]==false){ cout<<x<<' '; ump[x]=true; }
}
cout<<'\n';
}
return 0;
}
标签:Living,NAME,map,int,cin,笔记,vector,Dream,cout
From: https://www.cnblogs.com/XOF-0-0/p/18062549