Home
SSC Studio
Cancel

PAT 1057 Stack

Link #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <string> #include <string.h> #include <vector> #include <st...

C++ 输出二进制数 & 一些 bitset 用法

C++ 输出二进制数 #include <iostream> #include <bitset> using namespace std; int main() { int a = 0b1010; cout << a << endl; // 10, 十进制 cout << bitset<8>(a...

「绘画病」的科普

Bubbles 患有一种叫做「绘画病」的疾病. 这种病十分罕见, 因为它需要满足以下几个要求: 患者必须有绘画病史. 光是这一点很多人就无法满足了. 因为在这个世界里, 当你第一次觉得自己患上绘画病的时候, 你就肯定不会有绘画病史. 满足这个初始条件对于普通人来说极其困难, 但是 Bubbles 生活在一个循环的世界. 绘画病的症状是对绘画具有一种病态的热情. 例如, 当 Bub...

PAT 1051 Pop Sequence

Link 思路: 由于入栈顺序是 1, 2, …, n, 因此每次出栈的一定是栈顶元素, 且栈顶元素一定比所有的栈中元素大. 要维护栈中元素大个数 (不能超过 m) 以及栈顶元素 (当前 pop 出来的不能比上一个栈顶元素小). 在代码中, 我用 top 记录栈顶元素, 更新方式是从当前输入的元素 a 开始向下寻找第一个没有 pop 出来的元素 (用数组 v 记录是否被 pop), 如果...

Catalan Number 卡特兰数

卡特兰数 卡特兰数是组合数学中的一个常出现在各种计数问题中的数列, ​这个数列的前几项为: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, … 经典的卡特兰问题有: 进出栈序列、括号序列、满二叉树等. 进出栈序列 题目描述: n 个元素的进栈序列为: 1, 2, 3, 4, …, n, 则有多少种出栈序列? 思路: 我们将进栈表示为 +1, 出栈...

AcWing 278 数字组合

Link 题意: 给定 N 个正整数 A1,A2,…,AN,从中选出若干个数,使它们的和为 M,求有多少种选择方案。 最直观的思路就是 DFS, 但是显然会超时. 按照这道题的数据, DFS 可以过 10/11 个测试点, 最后一个 TLE 了. 不过 DFS 的代码先摆出来: #include <iostream> #include <cstdio> #in...

PAT 1145 Hashing - Average Search Time

Link (正向的) 平方探测法. #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <string> #include <string.h> #include <vector> #...

PAT 1131 Subway Map

Link 个人认为关键思路在于 line 的确定. 我是想到两点确定一条直线, 所以用 line[i][j] 表示 i 和 j 同在的那条线路的编号. 接下来就比较模式化了, 用 DFS 找最优解, 有点麻烦 (但也不足以为难) 的是, 需要记录 DFS 的过程 (我记录在了 tempPath 中), 然后通过各种比较得出 minPath, 这和之前用 Dijkstra 求最短路并记录路...

PAT 1153 Decode Registration Card of PAT

Link 思路不难, 但是很难做对. 必须用 printf 输出, 否则测试点 3 会超时. 要把 string 类型通过 s.c_str() 转换成 C 字符串. 可以在输入了 type 之后进行计算. #include <iostream> #include <cstdio> #include <cstdlib> #include <al...

PAT 1148 Werewolf - Simple Version

Link 用 wolf[i]=0 表示这个玩家的状态不确定, wolf[i]=1 表示这个玩家是狼, wolf[i]=2 表示这个玩家是人. 最外面的两层循环枚举两个 liars, 并且保证 i<j. 首先判断这两个 liars 的言论是否相悖, 是就直接 continue. 判断方法是: 如果 liar i 说 abs(a[j]) 是狼, 则记录 abs(a[j]) 是人, 即 ...