一、栈基础函数下次一定写好看点。准备草稿纸和笔时刻准备模拟7.3 T231954 【栈】火车进出站训练层级变式题知识版块栈目标确定火车能不能用给你的顺序出站约束入栈顺序数据规模0n,m1000候选算法和依据模拟复杂度预判O(n*m)实现结构/核心思路下意识用模拟了中途改过来用栈偶然发现b站上这题有讲解诶这个栈相当于交通枢纽#include bits/stdc.h using namespace std; bool check(vectorint inOrder, vectorint outOrder) { stackintmystack;//创建一个栈 int index0;//进栈下标 for(int newelement : outOrder) { while(mystack.empty()||mystack.top()!newelement) { if(inOrder.size()index)//如果火车都进栈了还没有出栈的就顺序不匹配 { return false; } mystack.push(inOrder[index]);//按给的顺序进栈 } mystack.pop(); } return true; } int main() { int n, m; cin n m; vectorint inOrder(n); for (int i 0; i n; i) { cin inOrder[i]; } for (int i 0; i m; i) { vectorint outOrder(n); for (int j 0; j n; j) { cin outOrder[j]; } if (check(inOrder, outOrder))//第一次未AC是因为这里条件判断不够准确 { cout Yes endl; } else { cout No endl; } } return 0; }解题后外化从会一次到稳定会逻辑思路BUG/代码实现BUG思路bug思路不清晰没有事先在草稿纸上模拟清楚写的很混乱错因回溯边界和易错点empty下次看到什么信号我应该想到这个方法后进先出7.3 P1044 [NOIP 2003 普及组] 栈训练层级变式题知识版块栈目标用栈实现数字排列记录组合数量数据规模n1≤n≤18候选算法和依据模拟复杂度预判O(n*n)实现结构/核心思路三种方法卡特兰数递归和动态规划递归会超时依旧是逻辑思路不清晰总有情况没考虑到总是会卡不能很通顺的理清思路并模拟出来,(注意long long)b站上有讲解递归还可以不用ll他是把情况推了一下发现规律有些节点是重复的就是把卡特兰数逻辑拆解了一下#include bits/stdc.h using namespace std; typedef long long ll; int n; ll cnt 0; // pos: 准备入栈第pos个数 // st: 当前栈 void dfs(int pos, stackint st) { if(pos n st.empty()) { cnt; return; } // 操作1能入栈就入栈 if(pos n) { st.push(pos); dfs(pos 1, st); st.pop(); // 回溯 } // 操作2栈非空就出栈 if(!st.empty()) { int top st.top(); st.pop(); dfs(pos, st); st.push(top); } } int main() { cin n; stackint s; dfs(1, s); cout cnt endl; return 0; }//这个递推也超时 #include bits/stdc.h using namespace std; int f[20][20]; int fun(int x,int y) { if(y0) return f[x][0]1; else if(x0) return f[0][y]fun(x1,y-1); else { if(f[x][y]!0) return f[x][y]; else return fun(x-1,y)fun(x1,y-1); } } int main() { int n; cin n; f[0][n]fun(0,n); cout f[0][n] endl; return 0; }第三种动态规划没做出来依旧WA卡特兰数可以全部AC#include iostream using namespace std; typedef long long ll; int main() { int n; cin n; ll f[20] {1}; for(int i 1; i n; i) for(int j 0; j i; j) f[i] f[j] * f[i-1-j]; cout f[n] endl; return 0; }不行啊先放放这个专题我去写更基础点的see you later二、队列基础函数我后面写个好看点的补上。7.4 T242808 取牌游戏训练层级变式题知识版块队列目标用队列实现数字排列记录组合数量数据规模 K 张 N≤K≤1×10^5 N ∣ K即 K 是 N 的倍数候选算法和依据模拟复杂度预判O(k)实现结构/核心思路//未全部ac第一个情况re #includebits/stdc.h using namespace std; int main() { int N,K,P; cinNKP; queueint q; for(int i1;iK;i) q.push(i); vectorint res; int cnt0; while(!q.empty()) { int outq.front();q.pop(); cnt; if(cnt%N0) res.push_back(out); for(int i0;iP;i) { int tq.front();q.pop(); q.push(t); } } sort(res.begin(),res.end()); for(auto x:res) coutx\n; return 0; }睡了睡了。