其他专题
PTA
专业词汇
| 单词 | 含义 |
|---|---|
| Orthogonal List | 十字链表 |
| adjacency list | 邻接表 |
| adjacency vertex | 邻接顶点，邻接表中的顶点 |
| AOV | Activity On Vertex Network, 顶点活动网 |
| AOE | Activity on edge network,边活动网 |
| AVL | Adelson-Velsky and Landis Tree，平衡二叉树 |
| BF | Brute Force(暴力搜索) |
| bm | 后缀匹配算法 |
| dp | 动态规划算法 |
| preorder | 先序 |
| inorder | 中序 |
| postorder | 后序 |
| lcm | Least Common Multiple,最小公倍数 |
| gcd | Greatest Common Divisor,最大公约数 |
| DAG | directed acyclic graph，有向无环图 |
小公式
- gcd(a,b) = gcd(b,a mod b)。欧几里得算法，辗转相除法。
欧几里得算法
若 x 和 y 为两个整数，且 x > y，则 x 和 y 的最大公约数与 y 和 x % y 的最大公约数相同。这个原理可以证明如下：
- 设 d 是 x 和 y 的一个公约数，则有 (假设 x = q * y + r，其中 q 是商，r 是余数，即 x % y)：
- d 能整除 x
- d 也能整除 y
- 由于 d 能整除 x 和 y，所以 d 也能整除 r（因为 r = x - q * y）
因此，任何能整除 x 和 y 的数也能整除 y 和 r，反之亦然。所以 x 和 y 的最大公约数等于 y 和 r 的最大公约数。
OJ(Online Judge) 状态术语
| 缩写 | 含义 |
|---|---|
| AC | Accepted ,答案正确 |
| WA | Wrong Answer, 答案错误 |
| TLE | Time Limit Exceeded,运⾏超时 / 时间超限 |
| CE | Compile Error,编译错误 |
| RE | Runtime Error, 运⾏时出错 |
| MLE | Memory Limit Exceeded, 内存超限 |
| PE | Presentation Error, 格式错误 |
英文单词
| 英文 | 中文 |
|---|---|
| permutation | n. [数] 排列；[数] 置换 |
| intersection | 交集 |
| union set | 并集 |
| complementary set /supplementary set | 补集 |
| Palindromic | adj. 回文的；复发的 |
| chopping | v. 切碎; 剁碎; 砍; 劈; (大幅度地)削减，降低; 取消; 终止; 向下猛击 |
| significant digits | 有效数字; 有效位数; 有効数字; 有效数字位数; 有效數字; |
| notation | n. (数学、科学和音乐中的)符号，记号，谱号; |
| fractional | adj. 很小的; 很少的; 微不足道的; 分数的; 小数的; |
| trailing zeros | 尾随零; |
| notorious | adj. 声名狼藉的; 臭名昭著的 |
| unit | adj. 单位 |
| tie | v. （用线、绳等）系；系牢，打结；连接，联合；约束；与……成平局，不分胜负；用连接线连接（音符） n. 领带；鞋带；领结；绳子，金属丝；关系，纽带；束缚；系梁；平局；不分胜负；（英）淘汰赛（尤指足球）；延音线 n. (Tie) （美、澳、马来）狄（人名） |
| quota | n. 定额；限额；配额；指标；（候选人当选所需的）规定票数，最低票数 |
| decimal | adj. 十进位的; $\color{red}{\text{小数的}}$; |
| consecutive | adj. 连续不断的; |
| prime | 质数 |
| transcendental number | 超越数 |
| truncate | v. 截断，删节；把……截成平面 adj. （叶、羽毛等）截形的；截短的 |
| rate | n. 比率，率；速度；价格；等级 vt. 认为；估价；责骂 vi. 责骂；被评价 n. (Rate)人名；(法、塞)拉特 |
| toll | n. 通行费；代价；钟声；伤亡人数 vt. 征收；敲钟 vi. 鸣钟；征税 |
| cents | 分 |
| chronologically | adv. 按年代地 |
| repetition | n. 重复；背诵；副本 |
| pedigree | n. 血统；家谱 adj. 纯种的 |
| ZigZag | n. 之字形，锯齿形线条；急转弯 v. 曲折前进，作之字形行进 adj. 曲折的，之字形的 adv. 曲折地，之字形地 |
| descendant | n. 后裔，子孙；（由过去类似物发展来的）派生物；（机器等）后继型产品 adj. 下降的；祖传的 |
| acyclic | adj. 非循环的；[物] 非周期的 |
| infix | v. 把……植入；插入（中缀）；用力插入 adj. 中缀的 n. 中缀 |
| parentheses | n. 圆括号；插入成分（parenthesis 的复数） |
| precedences | n. 优先；居先 |
| clique | n. 派系；阀；私党；小圈子 vi. 结党 n. (Clique)人名；(法)克利克 |
| radix | n. 根；[数] 基数 n. (Radix)人名；(法、德、西)拉迪克斯；(英)雷迪克斯 |
PAT
Q：为什么using namespace std依然找不到vector？
动态规划 p425
《算法笔记–胡凡》
一般可以使用递归或者递推的写法来实现动态规划，其中递归写法在此处又称作$\color{green}{\text{记忆化搜索}}$。
需要指出，一个问题必须拥有$\color{green}{\text{重子问题}}$和$\color{green}{\text{最优子结构}}$
①分治与动态规划。分治和动态规划都是将问题分解为子问题，然后合并子问题的解得到原问题的解。但是不同的是，分治法分解出的子问题是不重叠的，因此分治法解决的问题不拥有重叠子问题，而动态规划解决的问题拥有重叠子问题。例如，归并排序和快速排序都是分别处理左序列和右序列，然后将左右序列的结果合并，过程中不出现重叠子问题，因此它们使用的都是分治法。另外，分治法解决的问题不一定是最优化问题，而动态规划解决的问题一定是最优化问题。
${\textstyle\unicode{x2461}}$ 贪心与动态规划。贪心和动态规划都要求原问题必须拥有最优子结构。二者的区别在于，贪心法采用的计算方式类似于上面介绍的“自顶向下”，但是并不等待子问题求解完毕后再选择使用哪一个，而是通过一种策略直接选择一个子问题去求解，没被选择的子问题就不去求解了，直接抛弃。也就是说，它总是只在上一步选择的基础上继续选择，因此整个过程以一种单链的流水方式进行，显然这种所谓“最优选择”的正确性需要用归纳法证明。例如对数塔问题而言，贪心法从最上层开始，每次选择左下和右下两个数字中较大的一个，一直到最底层得到最后结果，显然这不一定可以得到最优解。而动态规划不管是采用自底向上还是自顶向下的计算方式，都是从边界开始向上得到目标问题的解。也就是说，它总是会考所有子问题，并选择继承能得到最优结果的那个，对暂时没被继承的子问题，由于重叠子问题的存在，后期可能会再次考虑它们，因此还有机会成为全局最优的一部分，不需要放弃所以贪心是一种壮士断腕的决策，只要进行了选择，就不后悔;动态规划则要看哪个选择到了最后，暂时的领先说明不了什么。
对动态规划可解的问题来说，总会有很多设计状态的方式，但并不是所有状态都具有无后效性，因此必须设计一个拥有无后效性的状态以及相应的状态转移方程，否则动态规划就没有办法得到正确结果。事实上，如何设计状态和状态转移方程，才是动态规划的核心，而它们也是动态规划最难的地方。
0,1背包可以用$\color{green}{\text{滚动数组}}$降低空间复杂度
贪心 p118
并查集 p328
algotithms p232
next_permutation(),如果没有下一个了会返回false
lower_bound()和 upper_bound()需要用在一个有序数组或容器中，在4.5.1中已经讨论过它们的实现。
lower_bound(first，last,val)用来寻找在数组或容器的[first，last)范围内第一个值大于等于val的元素的位置，如果是数组，则返回该位置的指针;如果是容器，则返回该位置的迭代器。
upper_bound(first, last, val)用来寻找在数组或容器的[first, last)范围内第一个值大于val的元素的位置，如果是数组，则返回该位置的指针;如果是容器，则返回该位置的迭代器。
PTA
非技术
- 注意输出的时候特定长度的占位0一定要输出
- 注意看清楚题目的排序要求
- 太多节点的时候慎用dfs,可能会爆栈
技术
- to_string:将int转换为string
- 读取的时候不需要这么麻烦，用一个char把
:吞掉就好了 - 排序的时候不用重写sort方法,vector的排序内置就是符合逻辑的
for (int Time = t1; Time < t2; Time++) fenzhang += danjia[Time % 1440 / 60];//按照当前时间所属小时段，给分账加上一分钟的钱按每一分中来算帐，一行抵百行- numeric的库函数：accumulate,inner_product(计算两个向量的内积),iota(Store increasing sequence 生成递增数列, 很简单的功能, 很奇怪的名字.)
理解
小工具
python可视化递归调用链的小工具：Snoop ，参考文献