蓝桥杯备赛练习题01

一、栈

1.单调栈

P2947 [USACO09MAR] Look Up S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

典型的单调栈题型。

#include <iostream>
using namespace std;
#include <algorithm>
#include<map>
#include <unordered_map>
#include <vector>
#include <queue>
#include <stack>stack<int> s;//存入的是下标
vector<int> nums;int main(){int n;cin>>n;vector<int> result(n,0);for(int i=0;i<n;i++){int x;cin>>x;nums.push_back(x);while(!s.empty()&&x>nums[s.top()]){result[s.top()]=i+1;s.pop();}s.push(i);}for(int i=0;i<n;i++){cout<<result[i]<<endl;}return 0;
}

2.栈

1363 -- Rails (poj.org)（栈的出栈顺序问题）

题目大意： A站有编号为1到N，N最大1000，的车厢，车厢进入中转station了就不能回到A，只能停在station内或者进入B站，问能不能按照给定的顺序排成那样的车厢号。

解题：每次一个新车厢进入station前，检查栈内栈顶元素是否与B站没有匹配的车厢头是否相等（如果有，则弹栈，重复此步骤），没有匹配的直接入栈。最后栈为空则可以排成给定次序。

举个例子：（2,1,3,5,4）能不能排成这样。

#include <iostream>
using namespace std;
#include <algorithm>
#include<map>
#include <vector>
#include <queue>
#include <stack>
#include<string>
int N;
string StackOrder(vector<int> seq){stack<int> s;int cnt=0;for(int i=1;i<=N;i++){while(!s.empty()&&s.top()==seq[cnt]){s.pop();cnt++;}s.push(i);}while(!s.empty()&&s.top()==seq[cnt]){s.pop();cnt++;}if(s.empty()){return "Yes";}else{return "No";}}int main(){while (true) {cin >> N; // 读取 Nif (N == 0) break; // 如果 N 是 0，结束输入while (true) {vector<int> Seq(N);cin >> Seq[0]; // 读取排列的第一个数if (Seq[0] == 0) break; // 如果第一个数是 0，结束当前块// 读取排列的剩余部分for (int i =1; i < N; i++) {cin >> Seq[i];}cout<<StackOrder(Seq)<<endl;}cout<<endl;}return 0;
}

2.1686 -- Lazy Math Instructor (poj.org)

我的主要想法就是中缀表达式转换为后缀表达式（逆波兰）

中缀表达式 : a + b

前缀表达式： + a b

后缀表达式 : a b +

转换过程：（中缀转后缀）
- 遇到操作数（如 a,b,c,2a,b,c,2），直接添加到输出列表。
- 遇到运算符，与栈顶的运算符比较优先级：
  - 如果栈顶运算符优先级较高或相等，则弹出栈顶运算符并添加到输出列表，重复此过程直到栈顶运算符优先级较低或栈为空。
  - 将当前运算符压入栈中。
- 遇到左括号 (，压入栈中。
- 遇到右括号 )，弹出栈中的运算符并添加到输出列表，直到遇到左括号 (，左括号弹出但不输出。
- 表达式扫描完毕后，将栈中剩余的运算符依次弹出并添加到输出列表。

当转换为逆波兰表达式后就可以求值（类似题目）：150. 逆波兰表达式求值 - 力扣（LeetCode）

class Solution {
public:bool isNumber(string& token) {return !(token == "+" || token == "-" || token == "*" || token == "/");}int evalRPN(vector<string>& tokens) {stack<int> nums;for(int i=0;i<tokens.size();i++){if(isNumber(tokens[i])) nums.push(atoi(tokens[i].c_str()));else{int num2=nums.top();nums.pop();//注意后入的在后int num1=nums.top();nums.pop();if (tokens[i] == "+") {nums.push(num1 + num2);} else if (tokens[i] == "-") {nums.push(num1 - num2);} else if (tokens[i] == "*") {nums.push(num1 * num2);} else if (tokens[i] == "/") {nums.push(num1 / num2);}}}return  nums.top();}};

还可以写的更优雅：

class Solution {
public:int evalRPN(vector<string>& tokens) {unordered_map<string,function<int(int,int)>> map={{"+",[](int a,int b){return a+b;}},{"-",[](int a,int b){return a-b;}},{"*",[](int a,int b){return a*b;}},{"/",[](int a,int b){return a/b;}}} ;stack<int> st;for(string& s:tokens){if(map.count(s)){int right=st.top();st.pop();int left=st.top();st.pop();st.push(map[s](left,right));}elsest.push(stoi(s));}return st.top();}
};

对于此题：

1.转化为逆波兰表达式2.计算比较

#include <iostream>
using namespace std;
#include <algorithm>
#include<map>
#include <vector>
#include <queue>
#include <stack>
#include<string>
map<char,int> m;
string transform_str(string str){string re="";stack<char> punc;for(int i=0;i<str.size();i++){if(isalnum(str[i])) re+=str[i];else{switch(str[i]){case '(': punc.push(str[i]);break;case ')':while(punc.top()!='('){re+=punc.top();punc.pop();}punc.pop();break;case '+':case '-':case '*':while(!punc.empty()&&m[str[i]]<=m[punc.top()]){re+=punc.top();punc.pop();}punc.push(str[i]);break;}}}while(!punc.empty()){re+=punc.top();punc.pop();}return re;
}
int result(string nt){stack<int> nums;for(int i=0;i<nt.length();i++){char c=nt[i];if(isalnum(c)){if(isdigit(c)) {nums.push(c-'0');}else{nums.push(c);//字母用其ASCII代替}}else{int num2=nums.top();nums.pop();int num1=nums.top();nums.pop();switch(c){case '+': nums.push(num1+num2);break;case '-': nums.push(num1-num2);break;case '*': nums.push(num1*num2);break;}}}return nums.top();
}
//void test(){
//    string s;
//    cin>>s;
//    string r=transform_str(s);
//    cout<<r<<endl;
//    cout<<result(r)<<endl;
//};
int main(){m['(']=0;m['+']=m['-']=1;m['*']=2;int T;cin>>T;cin.get();while(T--){string str1,str2;getline(cin,str1);getline(cin,str2);string n1=transform_str(str1); string n2=transform_str(str2);if(result(n1)==result(n2)) cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}

oj平台有些问题，还在等待。

3.2106 -- Boolean Expressions (poj.org)

F是0，V是1，运算符有& ! | ( )这五个，优先级为! > & > |当然有括号肯定先算括号里的，中间会有若干空格。

我的思路与上题一模一样，就是现将输入的式子去除空格，然后根据优先级去掉括号形成后缀表达式，然后直接利用栈进行计算结果。

#include <iostream>
using namespace std;
#include <algorithm>
#include<map>
#include <vector>
#include <queue>
#include <stack>
#include<string>
map<char,int> m;
string transform_str(string str){string re="";stack<char> punc;for(int i=0;i<str.size();i++){if(isalnum(str[i])) re+=str[i];else{switch(str[i]){case '(': punc.push(str[i]);break;case ')':while(punc.top()!='('){re+=punc.top();punc.pop();}punc.pop();break;case '|':case '&':case '!':while(!punc.empty()&&m[str[i]]<=m[punc.top()]){re+=punc.top();punc.pop();}punc.push(str[i]);break;}}}while(!punc.empty()){re+=punc.top();punc.pop();}return re;
}
char result(string nt){stack<bool> nums;for(int i=0;i<nt.length();i++){char c=nt[i];if(c=='V'){nums.push(1);}else if(c=='F'){nums.push(0);}else{bool log1, log2;switch(c){case '|':log1=nums.top();nums.pop();log2=nums.top();nums.pop();nums.push(log1|log2);break;case '&':log1=nums.top();nums.pop();log2=nums.top();nums.pop();nums.push(log1&log2);break;case '!':log1=nums.top();nums.pop();nums.push(!log1);break;}}}return nums.top()==1?'V':'F';
}
string getNoSpace(string s){string line="";for (char c : s) {if (!isspace(c)) { // 如果不是空格line+=c;}}return line;
}
//void test(){
//    string s;
//    getline(cin,s);
//    s=getNoSpace(s);
//    string r= transform_str(s);
//    cout<<r<<endl;
//    cout<<result(r);
//};
int main() {m['('] = 0;m['|'] = 1;m['&'] = 2;m['!'] = 3;string str1;//test();int cnt=1;while(getline(cin, str1)) {string str = getNoSpace(str1);string n1 = transform_str(str1);cout << "Expression " << cnt++ << ": " << result(n1) << endl;}return 0;
}

同样：

二、队列

1.基础知识

1.3210 A Stack or A Queue? - ZOJ Problem Set (pintia.cn)（基础主要是队列与栈结构（简单））

#include <iostream>
using namespace std;
#include <algorithm>
#include<map>
#include <unordered_map>
#include <vector>
#include <queue>
#include <stack>
#include<string>
int N;bool isStack(vector<int> in,vector<int> out){int i=0,j=N-1;for(;i<j;i++,j--){if(in[j]!=out[i]) return false;}return true;
}
bool isQueue(vector<int> in,vector<int> out){for(int i=0;i<N;i++){if(in[i]!=out[i]) return false;}return true;
}
int main(){int T;cin>>T;while(T--){cin>>N;int x;vector<int> in;vector<int> out;for(int i=0;i<N;i++){cin>>x;in.push_back(x);}for(int i=0;i<N;i++){cin>>x;out.push_back(x);}bool a= isStack(in,out),b=isQueue(in,out);if(a&&b){cout<<"both"<<endl;}else if(b){cout<<"queue"<<endl;}else if(a){cout<<"stack"<<endl;}else{cout<<"neither"<<endl;}}return 0;
}

2.1948 Team Queue - ZOJ Problem Set (pintia.cn)（队列的小变化（模拟））

#include <iostream>
using namespace std;
#include <algorithm>
#include<map>
#include <unordered_map>
#include <vector>
#include <queue>
#include <stack>
#include<string>
#define MAX 1001int main(){int cnt=1;while(1){queue<int> teamQueue[MAX];//每个元素是队列的数组queue<int> team;map<int,int> m;int t;cin>>t;if(t==0) break;cout<<"Scenario #"<<cnt++<<endl;while(t--){int num;cin>>num;for(int i=0;i<num;i++){int x;cin>>x;m[x]=t;//倒序}}while(true){string op;cin>>op;if(op=="ENQUEUE"){int x;cin>>x;int t=m[x];if(teamQueue[t].empty()) team.push(t);teamQueue[t].push(x);}else if(op=="DEQUEUE"){if(!team.empty()){int t=team.front();cout<<teamQueue[t].front()<<endl;teamQueue[t].pop();if(teamQueue[t].empty()) team.pop();}}else{cout<<endl;break;}}}return 0;
}

3.P1540 [NOIP2010 提高组] 机器翻译 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

（模拟题，用数组其实更简单，本来我想用queue，但是无法遍历，利用deque（双端队列）就可以遍历）

#include <iostream>
using namespace std;
#include <algorithm>
#include<map>
#include <unordered_map>
#include <vector>
#include <queue>
#include <stack>
#include<string>
deque<int> q;bool findQ(int x){for(int val:q){if(x==val) return true;}return false;
}
int main(){int N,M;cin>>M>>N;int cnt=0;for(int i=0;i<N;i++){int x;cin>>x;if(q.empty()){q.push_back(x);cnt++;continue;}if(!findQ(x)){if(q.size()<M){q.push_back(x);cnt++;}else{q.pop_front();q.push_back(x);cnt++;}}}cout<<cnt;return 0;
}

4.3629 -- Card Stacking (poj.org)

思路：利用队列模拟过程。

代码：

#include <iostream>
using namespace std;
#include <algorithm>
#include<map>
#include <vector>
#include <queue>
#include <stack>
#include<string>queue<int> q;
vector<int> result;
//void test(){//};
int main() {int N,K,P;cin>>N>>K>>P;//K=nN,P is card,M=n,K-n=n(N-1)for(int i=1;i<=K;i++){q.push(i);}int cnt=1;while(!q.empty()){if(cnt%N==0){result.push_back(q.front());}q.pop();//给右边for(int i=0;i<P;i++){int c=q.front();q.pop();q.push(c);//P张}cnt++;}sort(result.begin(),result.end());for(int i=0;i<result.size();i++){cout<<result[i]<<endl;}return 0;
}

5. 3125 -- Printer Queue (poj.org)

思路：首先我们建立一个队列，然后建立一个结构体，用一个flag标记位表示我们关注的作业，然后我们按照要求模拟队列，解决问题。

#include <iostream>
using namespace std;
#include <algorithm>
#include<map>
#include <vector>
#include <queue>
#include <stack>
#include<string>//void test(){//};
struct work{int prior;int flag;
};
int maxnum(queue<work> q){int maxv=-1;queue<work> temp = q;while (!temp.empty()) {maxv = max(maxv, temp.front().prior);temp.pop();}return maxv;
}
int main() {int T;scanf("%d",&T);queue<work> q;int n,m;while(T--){cin>>n>>m;int maxv=-1;for(int i=0;i<n;i++){int c;cin>>c;if(i==m) q.push({c,1});else q.push({c,0});maxv = max(maxv, c);}int time=0;while(!q.empty()){if(q.front().prior>=maxv){time++;if(q.front().flag) break;//更新maxvq.pop();maxv=maxnum(q);}else{work c=q.front();q.pop();q.push(c);}}cout<<time<<endl;// 清空队列while (!q.empty()) {q.pop();}}return 0;
}

6.p12207.pdf (onlinejudge.org)

思路：

模拟一个队列系统，处理两种特定的队列操作。每个测试用例有一个队列，队列中有初始的一系列任务编号（从1到p），并且接下来有一系列操作。操作可以是两种类型：

N（Next）：打印当前队列的队首元素，并将队首元素移到队尾。这相当于处理队列中的下一个任务，完成之后将其重新排队。
E x（Enter）：将元素 x 移动到队首。如果队列中已有这个元素，则首先移除它，然后将它重新插入到队首。这个操作可以视作将某个任务优先处理。

通过使用 deque（双端队列）来高效实现这两种操作，因为 deque 允许从队列两端高效地插入和删除元素。每次执行完操作后，根据需求输出队列的状态。程序通过 scanf 和 getchar 读取输入并执行相应的操作，最后输出每个操作后的结果。

#include <iostream>
using namespace std;
#include <algorithm>
#include<map>
#include <unordered_map>
#include <vector>
#include <queue>
#include <stack>
#include<string>const int C = 1000;int main()
{int p, c, caseno = 0;while(~scanf("%d%d", &p, &c) && (p || c)) {deque<int> dq;printf("Case %d:\n", ++caseno);for(int i = 1; i <= p && i <= C; i++) dq.push_back(i);while(c--) {char c = getchar();if((c = getchar()) == 'N') {printf("%d\n", dq.front());dq.push_back(dq.front());dq.pop_front();} else if(c == 'E') {int x;scanf("%d", &x);for(deque<int>::iterator iter = dq.begin(); iter != dq.end(); iter++)if(*iter == x) {dq.erase(iter);break;}dq.push_front(x);}}}return 0;
}

uva账户邮箱一直没有验证码，没有注册。

2.滑动窗口

1.P1886 滑动窗口 /【模板】单调队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
利用优先队列结合队列解决。

#include <iostream>
using namespace std;
#include <algorithm>
#include<map>
#include <unordered_map>
#include <vector>
#include <queue>
#include <stack>
#include<string>
priority_queue<int,vector<int>,greater<int>> q_min;
queue<int> q;
vector<int> v;
vector<int> min_num;
vector<int> max_num;
int main() {int n,k;cin>>n>>k;for(int i=0;i<n;i++){int m;cin>>m;v.push_back(m);}for (int i=0;i<k;i++){q.push(v[i]);}//find the minfor(int i=k;i<=n;i++){queue<int> q_temp;while (!q.empty()) {q_min.push(q.front());q_temp.push(q.front());q.pop();}min_num.push_back(q_min.top());while (q_min.size()!=1) {q_min.pop();}max_num.push_back(q_min.top());q_min.pop();//update the new,and pop the oldwhile (!q_temp.empty()) {q.push(q_temp.front());q_temp.pop();}q.pop();q.push(v[i]);}for(auto it=min_num.begin();it!=min_num.end();it++){cout<<*it<<" ";}cout<<endl;for(auto it=max_num.begin();it!=max_num.end();it++){cout<<*it<<" ";}return 0;
}int main(){return 0;
}

会超时

还可以利用其他办法：（单调队列）

#include <iostream>
using namespace std;
#include <algorithm>
#include<map>
#include <unordered_map>
#include <vector>
#include <queue>
#include <stack>
#include<string>const int N=1e6+10;
#include <deque>
deque<int> dq;
int a[N];
int n,m;int main(){scanf("%d%d",&n,&m);//最小值for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){while(dq.size()&&a[dq.back()]>a[i])  dq.pop_back();dq.push_back(i);if(i>=m){if(dq.front()<=i-m&&dq.size()) dq.pop_front();//为了限制这个数必须在这个滑动窗口里面cout<<a[dq.front()]<<" ";}}cout<<endl;dq.erase(dq.begin(),dq.end());//最大值for(int i=1;i<=n;i++){while(dq.size()&&a[dq.back()]<a[i])  dq.pop_back();dq.push_back(i);if(i>=m){if(dq.front()<=i-m&&dq.size()) dq.pop_front();cout<<a[dq.front()]<<" ";}}return 0;
}