题解 P1044 【栈】
world_execute
·
·
题解
[ 更好的阅读体验 ]
[ 原题面 ]
第零部分 —— 阅读题目
-
题目大意：有 n 个元素和1个栈
-
如果栈非空，可以选择将栈顶元素弹出
-
如果有数未进过栈，可以选择将一个数入栈
-
已知所有数的入栈顺序，求有多种可能的出栈序列
- 明显，每个数只能进出栈一次，进出栈共 $ 2n $ 次
---
### 第一部分 —— 开始分析
- 这看起来很像卡特兰数，但是，这篇题解不是来教你卡特兰数的（卡特兰数的题解，似乎进不了题解界面 $ QAQ $ ）
- 我们今天要用 **暴力+剪枝+卡常** 过了这道题
- 我们发现暴力的代码似乎很好写，时间复杂度也没那么高，大概 $ O(2^{2n} ) $
- $ Therefore ,$ 一份纯暴力的代码就出现了：
```cpp
//#pragma GCC optimize ("O2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
int n,Ans;
inline void Doit(const int x,const int y) {
if (y == n) { //边界条件，所有数都出栈了
++ Ans;
return;
}
if (x+y < n) Doit(x+1,y); //递归操作1，条件：还有数没有入过栈
if (x) Doit(x-1,y+1); //递归操作2，条件：栈里还有数
}
signed main() {
scanf("%d",&n);
Doit(0,0);
printf("%d\n",Ans);
}
```
- 代码中的 $ x $ 表示栈里面有 $ x $ 个数，
- $ y $ 表示出栈了 $ y $ 个数
- 边界条件就是所有数都出栈
第二部分 —— 深入思考
优化1：
-
我们发现，当所有数都入栈之后，出栈的顺序似乎只有一种，就是一直出栈
-
-
具体实现就是将边界条件的判断， y == n 改成 x+y == n
-
同时，可以将下面判断是否有数没进过栈的条件也可以省略，进一步优化常数
优化2：
常数优化：
- 经过上述优化，在加上洛谷的玄学 $ O2 $，我们成功把时间控制在 $ 0.5Sec $ 以内，足以过掉此题，若没有 $ O2 $ ，时间大约在 $ 0.9Sec $左右，有些吃力，可也能通过
### 第三部分 —— 代码实现
- 我相信，大家都能写出这道题的代码（毕竟已经出示了重要优化的核心代码了），但还是放上一份本人的代码吧（自认为码风不错 $ QuQ $）
```cpp
//#pragma GCC optimize ("O2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
int n,Ans;
inline void Doit(const int x,const int y) {
if (x+y == n-1) { //优化1+优化2
Ans += x+1; //优化2
return;
}
Doit(x+1,y), //常数优化
(x) && (Doit(x-1,y+1),0); //常数优化
}
signed main() {
scanf("%d",&n);
Doit(n>1,0); //特判n<=1
printf("%d\n",Ans);
}
```
### 第四部分 —— 延伸阅读①
- 前面讲过 $ C++ $ 的短路运算符 &&，但什么是短路运算符呢？
- 短路，就是说形如 (表达式)&&(表达式) 的形式，如若前者为假，那么是不是不需要计算后者，就可以知道，这整个表达式的值为假
- 当然，后者必须是一个表达式才可以进行这种运算，当我们发现我们要执行的语句为一个无返回值的 $ void $ 函数时，我们可用逗号，强制加上一个表达式作为需要，同时，这个表达式可以简单到 $ 0 $ 和 $ 1 $ 这样的纯数值
#### 第五部分 —— 后记
- 不知不觉就写了这么多了呢，如果这篇题解中有任何错误，欢迎在评论区，或私信支出，若是你觉的这篇题解还不错，那就点一个赞吧 （ヽ(”`▽´)ﾉ ）