寒假集训3——栈

1.P1996 约瑟夫问题

题目描述

n 个人围成一圈，从第一个人开始报数,数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 n−1 名小朋友，而该题是全部出圈。

输入格式

输入两个整数 n,m。

输出格式

输出一行 n 个整数，按顺序输出每个出圈人的编号。

输入输出样例

输入 #1复制

10 3

输出 #1复制

3 6 9 2 7 1 8 5 10 4

说明/提示

1≤m,n≤100

#include<iostream> #include<queue> using namespace std; int n,m; int main() { queue <int>q; cin>>n>>m; for(int i=1;i<=n;i++) q.push(i); while(q.size()) { //把队头移到队尾 //类似循环队列 //注意是移动m-1次，不是m次 for(int j=1;j<m;j++) { int mov=q.front(); q.pop(); q.push(mov); } //淘汰队头 cout<<q.front()<<" "; q.pop(); } return 0; }

2.B3616 【模板】队列

题目描述

请你实现一个队列（queue），支持如下操作：

• push(x)：向队列中加入一个数 x。
• pop()：将队首弹出。如果此时队列为空，则不进行弹出操作，并输出ERR_CANNOT_POP。
• query()：输出队首元素。如果此时队列为空，则输出ERR_CANNOT_QUERY。
• size()：输出此时队列内元素个数。

输入格式

第一行，一个整数 n，表示操作的次数。

接下来 n 行，每行表示一个操作。格式如下：

• 1 x，表示将元素x加入队列。
• 2，表示将队首弹出队列。
• 3，表示查询队首。
• 4，表示查询队列内元素个数。

输出格式

输出若干行，对于每个操作，按「题目描述」输出结果。

每条输出之间应当用空行隔开。

输入输出样例

输入 #1复制

13 1 2 3 4 1 233 3 2 3 2 4 3 2 1 144 3

输出 #1复制

2 1 2 233 0 ERR_CANNOT_QUERY ERR_CANNOT_POP 144

说明/提示

样例解释

首先插入2，队首为2、队列内元素个数为1。
插入233，此时队首为2。
弹出队首，此时队首为233。
弹出队首，此时队首为空。
再次尝试弹出队首，由于队列已经为空，此时无法弹出。
插入144，此时队首为144。

数据规模与约定

对于 100% 的测试数据，满足 n≤10000，且被插入队列的所有元素值是 [1,1000000] 以内的正整数。

#include<iostream> using namespace std; const int N=1e5+10; int q[N]; int front,back,size; void Push(int x) { back++; q[back]=x; } int Size() { return back-front; } void Pop() { if(Size()>0) front++; else cout<<"ERR_CANNOT_POP"<<endl; } void Query() { if(Size()>0) cout<<q[front+1]<<endl; else cout<<"ERR_CANNOT_QUERY"<<endl; } int main() { int n; cin>>n; int input=0; while(n--) { cin>>input; if(input==1) { int x; cin>>x; Push(x); } else if(input==2) Pop(); else if(input==3) Query(); else if(input==4) cout<<Size()<<endl; } return 0; }

3.B3656 【模板】双端队列 1

题目背景

Aya 衷心祝愿大家不再因为std::deque重蹈覆辙。

题目描述

请你实现 m 个双端队列，支持如下的 q 次操作：

• push_back(a,x)：在第 a 个双端队列中从尾部插入一个元素 x；
• pop_back(a)：在第 a 个双端队列中从尾部弹出一个元素。
• push_front(a,x)：在第 a 个双端队列中从头部插入一个元素 x；
• pop_front(a)：在第 a 个双端队列中从头部弹出一个元素。
• size(a)：查询第 a 个双端队列的元素个数；
• front(a)：查询第 a 个双端队列的队首元素；
• back(a)：查询第 a 个双端队列的队尾元素；

对于pop_back，pop_front，front和back操作，若当前双端队列为空则不进行，直接跳过该次操作。

输入格式

输入的第一行是一个正整数 q，表示操作次数。

接下来 q 行，每行先是一个字符串，保证为push_back或者pop_back或者push_front或者pop_front或者size或者front或者back之一。接下来是 1 或 2 个正整数，分别表示 a 和 x。

输出格式

对于每个size或者front或者back操作，输出一行表示答案。

输入输出样例

输入 #1复制

10 pop_back 2 push_back 1 1 push_front 1 3 push_front 2 2 push_front 2 3 pop_back 1 size 1 push_back 2 3 back 1 front 1

输出 #1复制

1 3 3

说明/提示

【数据范围】

对于所有数据，1≤m,q≤106，1≤x≤109。

这一题得用链表写。因为双向链表只用维护头尾指针，而双端队列就算里面没有元素，还是会预留空间。我用动态数组套个双端队列，即使用哈希表优化，还是因为内存超限过不了。

#include<vector> #include<deque> #include<list> #include<cstring> #include<unordered_map> #include<iostream> using namespace std; const int N = 1e4 + 10; unordered_map <int, list<int>> dq; int main() { int q; cin >> q; string s; int x; int a; while (q--) { cin >> s; cin >> a; if (s == "push_back") { cin >> x; dq[a].push_back(x); } else if (s == "push_front") { cin >> x; dq[a].push_front(x); } else if (s == "pop_back") { if (dq[a].size() > 0) dq[a].pop_back(); } else if (s == "pop_front") { if (dq[a].size() > 0) dq[a].pop_front(); } else if (s == "size") { cout << dq[a].size() << endl; } else if (s == "front") { if (dq[a].size() <= 0) continue; else cout << dq[a].front() << endl; } else if (s == "back") { if (dq[a].size() <= 0) continue; else cout << dq[a].back() << endl; } } return 0; }

4.P1044 [NOIP 2003 普及组] 栈

题目背景

栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作，即 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。

栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

题目描述

宁宁考虑的是这样一个问题：一个操作数序列，1,2,…,n（图示为 1 到 3 的情况），栈 A 的深度大于 n。

现在可以进行两种操作，

1. 将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push 操作）
2. 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop 操作）

使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由1 2 3生成序列2 3 1的过程。

（原始状态如上图所示）

你的程序将对给定的 n，计算并输出由操作数序列 1,2,…,n 经过操作可能得到的输出序列的总数。

输入格式

输入文件只含一个整数 n（1≤n≤18）。

输出格式

输出文件只有一行，即可能输出序列的总数目。

输入输出样例

输入 #1复制

3

输出 #1复制

5

说明/提示

【题目来源】

NOIP 2003 普及组第三题

这一题用卡特兰数做。需要结合组合数。

#include<iostream> using namespace std; typedef unsigned long long LL; LL c[50][50]; LL calc(int n) { //组合数 for (int i = 0;i <= 2 * n;i++) { c[i][0] = 1; c[i][i] = 1; } for (int i = 1;i <= 2*n;i++) { for (int j = 1;j <= i;j++) c[i][j] = c[i - 1][j] + c[i - 1][j - 1]; } //卡特兰数 return c[n * 2][n] - c[2 * n][n - 1]; } int main() { int n; cin >> n; cout << calc(n) << endl; return 0; }