洛谷：线性表

? ? ?今天开始刷洛谷，之前刷leetcode都是核心代码模式，现在突然让我用ACM模式，刚开始还是很不习惯的，但做了几道题好点了，只能说洛谷题的难度是比leetcode大的。

? ? 还有就是，STL牛逼！

1.询问学号(vector）

#include<iostream>
#include<vector>
using namespace std;
int main()
{
   vector<int>ret;
   int n,m,a,b;
   cin>>n>>m;
   while(n--)
  {
    cin>>a;
    ret.push_back(a);
  }
   while(m--)
  {
    cin>>b;
    cout<<ret[b-1]<<endl;
  }
 
}

? ? ? ?这道题还是比较简单的，首先我们要想用什么数据结构来存储数据，我们看到，要存储n名同学的学号，其次要询问第i个进入教室的同学的学号，什么数据结构能让我们在知道下标的情况下快速访问呢，那必然是数组啊，所以我先定义了一个动态变化的vector数组用来存储n名同学的学号，然后就是先获取学生个数和访问次数，然后输入这n名同学的学号，之后就是知道了下标b，直接输出ret[b-1]即可，还是很简单的。

2.寄包柜(map)

#include <iostream>
#include<map>
#include<cstdio>
using namespace std;
map <int, int> mat[100005];  
int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	while (q--) {
		int x, i, j, k;
		scanf("%d", &x);
		if (x == 1) {
			scanf("%d%d%d", &i, &j, &k);  
			mat[i][j] = k;  
		} else {
			scanf("%d%d", &i, &j);
			printf("%d\n", mat[i][j]); 
		}
	} 
	return 0;
}

? ? ?这道题的核心是如何根据给出的第i个寄包柜来获取有多少格子，你肯定会首先想到用二维数组来做，但不好意思，你看看数量级，如果我们要访问第10^5寄包柜，好，我们开辟了这么多空间，前面的用不到啊，这不是在浪费空间还是在干什么？什么？你说vector容器，好家伙，vector容器的下标也是连续的啊，你访问第i个，前面的空间肯定也开辟出来了啊，本质还是数组。那就没有什么办法了？那肯定是没.......肯定有啊，想啥呢？

? ? ? 我们使用map关联容器来做，map主要用来存储和检索集合中的数据元素，里面的数据均成一种映射关系，是一种包含关键字和值的键值对，关键字和值可以是字符串，数字等等，map里面的元素都是一个键值对，所以我们通过寄包柜和格子的映射关系来进行高效地存储和查找，当我们知道第i个寄包柜试，就通过map快速查找有多少个格子，这是离散并非连续的。

? ? ? ?所以我们定义一个map，第一个int是第几个柜子，第二个int是该柜子的格子数量，格子是有序的，当x=1时，我们就往第i个寄包柜的第j个格子里放物品；当x=2时，我们就输出第i个柜子的第j个格子的物品是什么。

3.验证栈序列(stack)

#include<iostream>
#include<stack>
using namespace std;
stack<int>stk;
int q,n;
int main()
{
  cin>>q;
  while(q--)
  {
	cin>>n;
	int a[n+1],b[n+1],cnt=1; 
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=1;i<=n;i++)
	cin>>b[i]; 
	for(int i=1;i<=n;i++)
	{
		stk.push(a[i]);
		while((stk.top())==b[cnt])
		{
			stk.pop();
            cnt++;
			if(stk.empty())break;//这里也要注意，当我们已经比对完所有的元素时，假如都能比对上，则此时栈已经空了，如果我们还继续进行循环执行pop操作是会出错的，所以要对栈是否为空进行判断。
		}
	}
	if(stk.empty()) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
    while(!stk.empty())stk.pop();//如果前面栈不为空一定要清空栈再进入下一次循环
   }
	return 0; 
}

? ? ?这个题已经不能再明显了，肯定栈的题，我们先获取入栈序列和出栈序列，然后对栈进行入栈(push)操作，全部入栈完毕后，我们一个一个元素进行比较，如果相同，则将该栈元素弹出，cnt++，继续比较下一个，需要注意的点我在上面已经写了，栈为空时结束循环，此时也要进行判断，如果栈为空说明出栈序列是对的输出"Yes"，否则输出"No"，最后一定要把栈清空再进入下一次循环！

4.约瑟夫问题(queue)

#include<iostream>
#include<queue>
using namespace std;
int main()
{
  queue<int>q;
  int n,m;
  int num=1;
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
    q.push(i);
  }
   while(!q.empty())
  {
     if(num==m)
     {
       cout<<q.front()<<" ";
       q.pop();
       num=1;
     }
     else
     {
        num++;
        q.push(q.front());//队首的人压到队尾
        q.pop(); //删除队首的人 
      }
   }
   cout<<endl;
   return 0;
}

? ? ?这道题第一次在leetcode没做出来，在洛谷上用queue容器秒了。

? ? ?约瑟夫问题也是一个很经典的问题，n个人围成一个圈圈，给定一个数字k，从第一个人开始报数，数到k的人出圈，其他人依旧围成一个圈，同时出圈的人的下一个人从1开始报数，最后所有人都会出圈，我第一次想到循环队列，其实也可以用链表做，但个人认为循环队列超级简洁。

? ? ?首先定义一个队列，用num来记录编号到哪个人时num=m，然后就是向队列中插数，当队列不为空时，如果我的num不等于m的话，说明不是这个人，那我们就把队首的人压到队尾，同时删除队首的人，一直到num=m时，我们找到了第一个出局的人，把它输出并删除，同时令num=1，寻找下一个人。

5.机器翻译(queue)

#include<iostream>
#include<queue>
using namespace std; 
queue<int>q;
int m,n;
int cnt[1005]={0};//如果把数组放在主函数外，全部初始化为0，放在主函数内就是随机值，这时候就要初始化为0
int main()
{
  int ans=0;
  cin>>m>>n;
  int word;
  while(n--)
  {
    cin>>word;
    if(cnt[word])continue;
    else
    {
       if(q.size()>=m)
       { 
        cnt[q.front()]=0;//顺序不能调换，一旦调换就获取不到原来的队首元素了
        q.pop();
       }
        q.push(word);
        ans++;
        cnt[word]++;
    }
  }
    cout<<ans;
    return 0;
}

? ? ?这道题看前面的文字描述可能有点头皮发麻，直接看样例解释我们可以清楚这是一个在一端插入元素，在另一端删除元素的队列问题，需要注意的是，队列并没有count函数哦，我们需要用一个cnt数组来统计单词是否在字典中，输入单词，如果出现过就continue跳过，如果没有出现过，进一步判断队列是否已满，没满直接插入，ans++，cnt[word]++即可；如果已经满了，就先令队首元素在cnt数组的值为0，因为此时这个单词已经被删除了，查询结束返回ans即可。

? ? 还有一点就是在定义数组的时候一定要定义在主函数外面啊，如果定义在主函数里面而且你不初始化，数组里面就全是随机值，因为这个卡了一些时间，定义在主函数外面就是全局变量，你自己忘了初始化，系统也会自动给你初始化为0的，但在主函数里面就不会，需要自己进行初始化。