首页 > 其他分享 >Living-Dream 系列笔记 第2期

Living-Dream 系列笔记 第2期

时间:2024-03-09 12:55:50浏览次数:26  
标签:Living NAME map int cin 笔记 vector Dream cout

本期主要讲解 vectormap 两个 STL 容器。

知识点:

首先,引入两种数组的区别:

  • 静态数组,指提前声明需要多少内存的数组,是连续的;

  • 而动态数组则是在插入元素时临时指定存储空间,不要求连续。

STL vector 是一个动态数组,下标默认从 \(0\) 开始。它支持的操作如下:

  • 定义:一维 vector<TYPE> NAME,二维 vector<TYPE> NAME[SIZE],一般不定义 vectorvector

  • 插入: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)

(更多 vectormap 的操作请访问 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

相关文章

  • Living-Dream 系列笔记 第3期
    本期主要讲解二分查找。知识点二分查找:思想:分治。使用场景:在一个有序序列中,反复查找不同目标。时间复杂度:\(O(n\logn)\)。实现:对数列排序;确定二分边界(通常为L=最小下标-1,R=最大下标+1);伪代码:intL=左边界-1,R=右边界+1;while(L+1<R){intmid=(L+R)......
  • Living-Dream 系列笔记 第1期
    本期主要讲解模拟、枚举算法。例题T1简单模拟题。利用scanf/cin以int形式读入分和秒,并令秒循环累加,逢\(60\)归\(0\)并向分进\(1\),分则是逢\(24\)归\(0\)。在循环的过程中若分秒合起来是回文数字,则退出循环,按照题目格式输出当前时间。注意开始时间不算。#includ......
  • Living-Dream 系列笔记 第17期
    ProblemT1/*思路:分类讨论:若k=0,则输出x+1;若k>tot(x的位数),则输出1+k-tot个0+x;否则输出10^k+x。*/#include<bits/stdc++.h>usingnamespacestd;longlongk,x,tot,ans=1;//开longlongintmain(){ cin>>k>>x; if(k==0){cout<<x+1;return0;}//情况1......
  • Living-Dream 系列笔记 第14期
    本期主要讲解差分技巧。知识点我们令原数组为\(a_i\),则当且仅当\(d_i=a_i-a_{i-1}\)时,我们称\(d_i\)是\(a_i\)的差分数组。特别的,\(d_1=0\),\(d_{n+1}=-n\)。差分数组\(d_i\)有以下三个性质:\(d_i\)的前缀和数组为\(a_i\)。将\(a_{L\simR}\)这个区间统一加......
  • Living-Dream 系列笔记 第15期
    模拟赛爆炸祭。T1把所有连通块依次求出,若某个连通块的数量已经出现过,则说明它与以前的连通块属于同一星系,直接将星系大小加上连通块大小并取\(\max\);否则将星系数量\(+1\)。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,m;intans=-1e9,num,......
  • Living-Dream 系列笔记 第11期
    本期主要讲解与上期相同内容(雾。例题T1在整个矩阵外加一圈\(0\),使得包围圈外的\(0\)形成一整个连通块。求出这个连通块并标记为\(1\),然后输出即可。#include<bits/stdc++.h>usingnamespacestd;intn;intdx[]={-1,0,1,0},dy[]={0,1,0,-1};inta[31][31],g[31][31];......
  • Living-Dream 系列笔记 第12期
    本期主要讲解一维前缀和技巧。知识点我们令\(a_i\)表示原数组的第\(i\)个元素,则\(sum_i\)表示\(a_i\)前\(i\)个元素之和,即:\[sum_i=\sum^{i}_{j=1}a_j\]我们知道,\(a\)数组前\(i\)个元素的和\(=\)前\(i-1\)个元素的和\(+a_i\)。于是便可得到\(sum\)数组的......
  • Living-Dream 系列笔记 第13期
    本期主要讲解二维前缀和。知识点我们令\(a_{i,j}\)表示原数组,则\(sum_{i,j}\)为\(a\)的二维前缀和数组。根据容斥原理,得到递推式:\[sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}+a_{i,j}\]二维前缀和适用于求静态矩阵的子矩阵元素和。若我需要求一个左上角坐标为......
  • Living-Dream 系列笔记 第10期
    本期主要讲解进阶\(\text{DFS}\)。知识点\(\text{DFS}\)求解连通块问题:定义:若一个点集中的所有点都能互达,且与集合外的点无法互达,则称此点集为一个连通块。考查方式:求连通块数量/大小/周长。例题T1在\(\text{DFS}\)函数中传入参数\(x\)和\(str\),分别表示......
  • Living-Dream 系列笔记 第8期
    本期主要讲解的与上期相同。例题T1上课的时候调这个题感觉要吐了\(qwq\)。。。首先读入\(n\)行字符串,可以采取忽略中间无关单词的方式来直接读取\(X\)和\(Y\)。将所有名字存入\(a\)数组,对\(a\)数组按字典序排序后就可以开始\(\text{DFS}\)了,这里建议使用next_pr......