拓扑排序
拓扑排序要解决的问题是给一个有向无环图的所有节点排序。
一个有向无环图的拓扑排序可能不唯一
每次排序入度为0的节点,更新与之相连的结点入度,后面没记上 好像是直到排序完成
运算符优先级
1.*
2.%
1.++,--
2.<<,>>
3.&
4.^(异或)
5.|
6.&&
7.||
十进制小数转二进制
乘2取整,整数部分正序排列
e.g.
文件读写
* filename:要打开的文件名。
* mode:打开文件的模式,可以是"w","r","a"......
* stream:要重新定向的流,可以是stdin,stdout 当然也可以用自定义文件指针
"等下。。。有ofstream我用freopen干嘛"
"c"[1]
对拍
"对拍" 是一种测试算法或程序的方法。它的基本思想是使用两个或多个不同的算法对相同的输入进行运算,然后检查输出是否一致。
1. 运行第一种算法,输出到1.out
2. 运行第二种算法,输出到2.out
3. 比较1.out和2.out是否相同,不相同就退出
4. 更换输入,继续循环
动态规划
动态规划是一种表格处理法,或记忆递归法,在对问题求解时,通过把原问题分解为相对简单的子问题的方式求解复杂问题的一种方法。
拿一道非常神奇甚至没法贪心的找零题来:
原题链接(2024集训营的)
这道题直接贪心会这样:
比如找15钱,贪心先拿11,后面拿4张1 。
但实际上可以直接拿3张5钱 。
但使用动态规划:
来打个表——
0元 1元 2元 ... 5元 0张 1张 2张 ... ?张
此时5元和0元,4元相关联
在四张上加,要5张
而从0元上加,只要一张
所以这里的结果是——
5元 1张
动态规划的特点
* 无后效性,一个状态阶段不被未来的状态影响
* 最优子结构,比如将此题的f(i) 划分为f(i - 1),f(i - 5),f(i - 11),则需先知道它们的答案才能得出f(i)。
* 子问题重叠,不想记了
最后是这题的递推AC代码 (虽然你们也交不了)
火了我就发题面
又有一题
打表,习惯了......
编号 能力 最长长度 1 1 1(第一个,没得递推) 2 5 1 3 3 2 4 4 2 5 6 2,3,3,4->4 6 9 2,3,3,4,5->5 7 7 2,3,3,4,5->5 8 8 2,3,3,4,5,6->6
得出结果:666
那么这个过程用代码复现就是——
然后,又是一题。。。。。。
oi
当然,还有。
又来。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
树的存储方式
1. 双亲存储法(父亲存储法)
2. 孩子存储法
3. 树的邻接表存储法
双亲存储法
利用树中除根节点外,每个节点都有唯一的父节点的性质。
tree[i].parent表示编号为i的树节点的父亲.
孩子存储法
每个节点存储自己孩子的位置信息,可以使用vector存储。
tree[i].chile 存储着结点i的孩子的位置信息。
邻接表存储法
邻接表主要是记录一个顶点的邻接点和邻接边信息的结构。
若含有边权,数据节点中增加权重w。
树的直径
树的直径定义为树中最远的两个节点之间的距离。
表达逝树
表达逝树是一种特殊的树,它的非叶结点是操作符,叶节点是操作数。
因为操作符的操作一般为两个,所以表达式树多为二叉树。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 老师说用不了这俩。。。joker ↩︎