CR Blog

怕什么真理无穷，进一寸有进一寸的欢喜

信奥集训营笔记：Day 10

初赛知识

一、数据结构 1.栈 特点：1.先进后出 2.数据从栈顶压入、删除 2.队列 特点：1.先进先出 2.数据从队尾插入，队头删除 3.树 基本概念 结点拥有的子树数量叫做结点的度。 度为0的结点叫做叶子结点或终端结点。 度不为0的结点叫做非终端结点或分支结点。 树的度是树内各结点度的最大值。 结点的层次从根开始定义起，根为第一层，根的孩子为第二层。 树中结点的最大层...

Posted by CR on August 15, 2018

信奥集训营笔记：Day 9

初赛知识

一、计算机基础知识 1.ENIAC（埃尼阿克），第一台电子计算机，150千瓦，5000次每秒，弹道计算，1946.2.14，宾夕法尼亚大学。 2.计算机：运算分为：算术运算和逻辑运算，采用存储程序工作方式。 3.计算机的发展史   起止年代 主要元件 第一代 40年代末-50...

Posted by CR on August 14, 2018

信奥集训营笔记：Day 8

搜索

搜索 一、深度优先搜索 图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。 它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶...

Posted by CR on August 13, 2018

信奥集训营笔记：Day 7

图论与并查集

图论 一、基本概念 转载自saltriver的csdn博客 图（graph）是数据结构和算法学中最强大的框架之一（或许没有之一）。图几乎可以用来表现所有类型的结构或系统，从交通网络到通信网络，从下棋游戏到最优流程，从任务分配到人际交互网络，图都有广阔的用武之地。 而要进入图论的世界，清晰、准确的基本概念是必须的前提和基础。下面对其最核心和最重要的概念作出说明。关于图论的概念异乎寻常的...

Posted by CR on August 12, 2018

信奥集训营笔记：Day 6

高精度运算

高精度运算 1.定义 高精度算法，属于处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。对于非常庞大的数字无法在计算机中正常存储，于是，将这个数字拆开，拆成一位一位的，或者是四位四位的存储到一个数组中， 用一个数...

Posted by CR on August 11, 2018

信奥集训营笔记：Day 5

动规进阶：区间动规与多重背包

动规进阶 一、区间动规 1.定义 在一段区间上的动态规划。 它既要满足dp问题的最优子结构和无后效性外，还应该符合在区间上操作的特点。往往会对区间进行合并操作。抑或是单个元素（可看成一个小区间）跨区间进行操作。 例1：合并石子 有一排石子，每次合并相邻两堆石子，代价为两堆石子之和，求合并成一堆的最小总代价 Sample Input 5 1 2 3 4 5 Sampl...

Posted by CR on August 8, 2018

信奥集训营笔记：Day 4

动态规划

动态规划 ##一、定义 动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。 动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。...

Posted by CR on August 7, 2018

信奥集训营笔记：Day 3

递归与二分查找

递归 一、定义 程序调用自身的编程技巧称为递归（recursion）。 递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。 递归的能力在于用有限的语句来定义对象的...

Posted by CR on August 6, 2018

信奥集训营笔记：Day 2

博弈

博弈 一、巴什博奕 1.定义 巴什博弈：只有一堆n个物品，两个人轮流从这堆物品中取物， 规定每次至少取一个，最多取m个。最后取光者得胜。 例：两人取n张牌，每次最少取1张，最多取m张,取到最后一张的赢。输入n和m，输出谁必胜 #include <iostream> using namespace std; int main() { int n,m; ...

Posted by CR on August 5, 2018

信奥集训营笔记：Day 1

分治

一、分治 定义 把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 解题步骤 1.分解 2.求解 3.合并 例子 1.归并排序 百度百科 算法实现 示例代码 #include <iostream> using namespace std; #define MAX 10000 int...

Posted by CR on August 4, 2018

FEATURED TAGS
闲聊 数学 科普 预告 足球 概率 信奥 学习 笔记
ABOUT ME

Goals determine what you going to be!

✉️ caorayking@gmail.com

FRIENDS