转眼间四周过去了，终于忙完了考试，军训，生病的事情，今天开始复更GitHub博客，主要记录这段时间里我利用零碎时间学习的内容
数据结构对于算法的重要性不言而喻，这段时间就针对数据结构进行了系统性学习
主要的学习分为了四个模块，线性表（包括vector数组，stack栈，queue列队，链表），以及二叉树，集合，还有图
最先复习的是线性表里的vector数组，这里附上一道vector数组的题目，巧妙利用vector数组相比C风格数组的长度可变性
附上题目出自洛谷P3613 寄包柜
超市里有 $n(1\le n\le10^5)$ 个寄包柜。每个寄包柜格子数量不一，第 $i$ 个寄包柜有 $a_i(0\le a_i\le10^5)$ 个格子，不过我们并不知道各个 $a_i$ 的值。对于每个寄包柜，格子编号从 1 开始，一直到 $a_i$。现在有 $q(1 \le q\le10^5)$ 次操作：
1 i j k：在第 $i$ 个柜子的第 $j$ 个格子存入物品 $k(0\le k\le 10^9)$。当 $k=0$ 时说明清空该格子。2 i j：查询第 $i$ 个柜子的第 $j$ 个格子中的物品是什么，保证查询的柜子有存过东西。已知超市里共计不会超过 $10^7$ 个寄包格子，$a_i$ 是确定然而未知的，但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。
第一行 2 个整数 $n$ 和 $q$，寄包柜个数和询问次数。
接下来 $q$ 个行，每行有若干个整数，表示一次操作。
对于查询操作时，输出答案，以换行隔开。
5 4
1 3 10000 118014
1 1 1 1
2 3 10000
2 1 1
118014
1
$\text{upd 2022.7.26}$：新增加一组 Hack 数据。
从题目里可以看到，存放内容k的范围是到10的9次方，也就是一个int，最多可以有10的5次方个寄包柜，一个寄包柜最多有10的5次方个格子，虽然说了最多总共只有10的7次方个格子
但是由于不知道到底是哪个寄包柜有最多的格子，传统C风格数组只能开10的5次方 *10的5次方的int数组，内存简单计算10的10次方 *4 /1024 /1024，得到40000MB显然必定MLE
而使用STL的vector数组就可以用10的7次方大小的二维vector数组，占内存为40MB，已经达到要求（<400MB），这里附上解答
#include<iostream>
using namespace std;
#include<vector>
int main()
{
vector<vector<int> > gui;
int n,q;
cin>>n>>q;
gui.resize(n+1);
for(int a=0;a<q;a++)
{
int judge;
int i=0,j=0,k=0;
cin>>judge;
if(judge==1)
{
cin>>i>>j>>k;
/* if(1+j>gui[i].size())
{
gui[i].resize(j+1);
gui[i][j]=k;
}这段代码错误，因为柜子够大时不能存入包裹！*/
if(gui[i].size()<j+1)
{
gui[i].resize(j+1);
}
gui[i][j]=k;
}
else if(judge==2)
{
cin>>i>>j;
cout<<gui[i][j]<<endl;
}
}
return 0;
}
写题中产生的一个错误已经用注释在代码里写出来了，接下来就轮到stack栈了
下面这题出自洛谷P1241括号序列
这道题的问题在于题目已经讲的蛮清晰了但是依然语文令人难懂，我也没法解释更清楚了，这道题的关键在于stack记录的是位置，而不是括号的种类，因为stack这题的核心作用在于判断某个括号是否得到匹配，而非判断剩下什么种类括号
下面是题目和我的代码（这题难度因为语文很离谱，看了题解之后写的
定义如下规则：
例如，下面的字符串都是平衡括号序列：
()，[]，(())，([])，()[]，()[()]而以下几个则不是：
(，[，]，)(，())，([()现在，给定一个仅由 (，)，[，]构成的字符串 $s$，请你按照如下的方式给字符串中每个字符配对：
配对结束后，对于 $s$ 中全部未配对的括号，请你在其旁边添加一个字符，使得该括号和新加的括号匹配。
输入只有一行一个字符串，表示 $s$。
输出一行一个字符串表示你的答案。
([()
()[]()
([)
()[]()
对于全部的测试点，保证 $s$ 的长度不超过 $100$，且只含 (，)，[，] 四种字符。
下面是我的代码
#include<iostream>
using namespace std;
#include<stack>
#include<string>
#include<vector>
int main()
{
stack<int> s;
string str;
getline(cin,str);
int len=str.length();
vector<int> v(len,0);
if(str=="")
{
cout<<endl;
return 0;
}
else
{
for(int i=0;i<len;i++)
{
if(str[i]=='('||str[i]=='[')
{
s.push(i);
}
else if(str[i]==')')
{
if(s.empty())
{
continue;
}
int tp=s.top();
if(str[tp]=='(')
{
s.pop();
v[tp]=1;
v[i]=1;
}
//else
//{
// s.push(i);
//}
}
else if(str[i]==']')
{
if(s.empty())
{
continue;
}
int tp=s.top();
if(str[tp]=='[')
{
s.pop();
v[tp]=1;
v[i]=1;
}
//else
//{
// s.push(i);
//}
}
}
}
for(int i=0;i<len;i++)
{
if(v[i]==1)
{
cout<<str[i];
}
else
{
if(str[i]=='['||str[i]==']')
{
cout<<"[]";
}
else if(str[i]=='('||str[i]==')')
{
cout<<"()";
}
}
}
return 0;
}
这道题的测试用例里面绝对有空格我服了，因为我else if(str[i]==’(‘……原本是else，测试得到了全wrong，然后把getline改成cin也对了，估计是最前面都有个空格什么的
下一题依旧是stack，出自洛谷P1449后缀表达式，没啥好说的，遇到点号就把数据存进stack，遇到数字就乘10加进去，遇到运算符就弹出两个顶栈内容做运算，把结果再存进去，最后看stack里剩下的那个数字，注意这里@不在ASCII里面，char读不到，直接在循环中减一次次数
附上题目及解题代码
所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。
本题中运算符仅包含 $\texttt{+-*/}$。保证对于 $\texttt{/}$ 运算除数不为 0。特别地，其中 $\texttt{/}$ 运算的结果需要向 0 取整（即与 C++ / 运算的规则一致）。
如：$\texttt{3(5-2)+7}$ 对应的后缀表达式为：$\texttt{3.5.2.-7.+@}$。在该式中，@ 为表达式的结束符号。. 为操作数的结束符号。
输入一行一个字符串 $s$，表示后缀表达式。
输出一个整数，表示表达式的值。
3.5.2.-*7.+@
16
10.28.30./*7.-@
-7
| 数据保证，$1 \leq | s | \leq 50$，答案和计算过程中的每一个值的绝对值不超过 $10^9$。 |
#include<iostream>
using namespace std;
#include<stack>
#include<string>
int main()
{
stack<int> s;
string str;
cin>>str;
int len=str.length(),num=0;
for(int i=0;i<len-1;i++)
{
if(str[i]=='.')
{
s.push(num);
num=0;
}
else if(str[i]>='0'&&str[i]<='9')
{
num*=10;
num+=str[i]-48;
}
else
{
int a=s.top();
s.pop();
int b=s.top();
s.pop();
char k=str[i];
switch(k)
{
case '+':
s.push(a+b);
break;
case '-':
s.push(b-a);//先前这里写a-b错了
break;
case '*':
s.push(a*b);
break;
case '/':
s.push(b/a);//当时这里也写成a/b
}
}
}
cout<<s.top();
return 0;
}
最后要注意好是后弹出栈的减去/除以先弹出栈的，就没有问题了
再接下来轮到了queue列队，FIFO特点，这里的机械翻译是道简单列队题，我利用了手写数组+双指针代替而没有用STL的queue，明天我会再写一版用STL写法的，STL方法方便，且可读性强，题目出自洛谷P1540机器翻译
下面附上题目及代码
NOIP2010 提高组 T1
小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。
这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。
假设内存中有 $M$ 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 $M-1$，软件会将新单词存入一个未使用的内存单元；若内存中已存入 $M$ 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。
假设一篇英语文章的长度为 $N$ 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。
共 $2$ 行。每行中两个数之间用一个空格隔开。
第一行为两个正整数 $M,N$，代表内存容量和文章的长度。
第二行为 $N$ 个非负整数，按照文章的顺序，每个数（大小不超过 $1000$）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。
一个整数，为软件需要查词典的次数。
3 7
1 2 1 5 4 4 1
5
整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：
1：查找单词 1 并调入内存。1 2：查找单词 2 并调入内存。1 2：在内存中找到单词 1。1 2 5：查找单词 5 并调入内存。2 5 4：查找单词 4 并调入内存替代单词 1。2 5 4：在内存中找到单词 4。5 4 1：查找单词 1 并调入内存替代单词 2。共计查了 $5$ 次词典。
#include<iostream>
using namespace std;
int article[10000];
int main()
{
int memory,lenth,search=0,word;
cin>>memory>>lenth;
int fir=0,sec=0;
for(int i=0;i<lenth;i++)
{
int insi=0;
cin>>word;
for(int j=fir;j<sec;j++)
{
if(word==article[j])
{
insi=1;
break;
}
}
if(insi==1)
{
continue;
}
else
{
search++;
if(sec-fir<memory)
{
article[sec]=word;
sec++;
}
else{
article[sec]=word;
sec++;
fir++;
}
}
}
cout<<search<<endl;
return 0;
}
现在写的变量名已经越来越正常了，不再出现极难懂的魔术变量