Dawn-K's Blog

「CodeNote」链式前向星

链式前向星介绍链式前向星是一种用于存图的数据结构,比较适用于存稀疏图.其综合了邻接表,邻接矩阵的优缺点,然后在前向星的基础上进行改进. 时间复杂度,空间复杂度,查询复杂度都是O(m) 初始化 1 2 3 4 void CFSInit() { // 链式前向星初始化 cnt = 1; // 其实这里是0也无所谓 memset(head, 0, sizeof(hea...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」训练联盟第一场

训练联盟第一场日拱一卒,功不唐捐 A. 图像压缩四叉树题目描述四叉树把大量坐标数据压缩包存在内存空间中，它总是将给定空间分割成4个，然后以递归形式标识，故得名四叉树。其最著名的应用是对黑白图像的压缩。四叉树会用字符串的形式对 2^N * 2 ^N的黑白图像进行如下压缩。 - 如果所有像素是黑色，无论图像大小是多少，四叉树压缩的结构都是b； - 图像所有像素是白...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」计算几何

计算几何矩阵交判断两个矩阵交及矩阵相交面积给出两个矩形(每个矩形给出左上角坐标和右下角坐标),快速判断两个矩形有没有相交(此处指重合面积大于0) 判断方法(图有点小,凑活着看) 我们假设矩形 a ((x1,y1),(x2,y2)) , b ((x1',y1'),(x2',y2')) 则判断矩形相交的条件为 max(x1,x1') < min(x2,x2') &am...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」背包学习心得

动态规划初步 [TOC] 动态规划认知在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。 01 背包问题有n件物品和一个容量为m的背包，放入第ｉ件物品所需要的空间为ｗi，第ｉ件物品的价值为vｉ，问背包可以放入物品的最大价值为多少？此问题不可用贪心算法，贪心法得到的往往不是最优解。直接暴力穷举n...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」浮点误差

浮点误差参考博客-韬光养晦综述由于计算机存储格式限制,浮点数是存在误差的,这一点在计算几何中尤为突出,以下来探讨这个问题. 浮点数的精度占字节数数值范围十进制精度位数 float 4 -3.4e-38～3.4e38 6~7...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」树的直径

树的直径概念给定一棵树,树中每个边都有权值,树中两点之间的距离定义为连接两点的路径边权和.树中最远的两点之间的距离称之为树的直径,也就是树的最长链(偶尔也指代为一条路径). 树的直径有两种求法,都是O(n)的.一种是基于树形dp(之后再补上).一种是基于搜索. 搜索我们随便找一个节点作为根(之前如果有根就不用换).进行一次搜索,找到距离根最远的节点p,然后再将p作为起点,寻找...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」树状数组

树状数组十年岐路，空负曲江花介绍参考资料树状数组就是以数组的形式来模拟树,在代码很简洁的情况下,能起到部分代替线段树的效果.而且此算法常数较小,空间开销也很小,是一个非常轻量级的数据结构. 思想图中黑色的是原数组,红色的是树状数组.我们发现树状数组的空间开销是O(n)的.我们以八个元素(从1开始记数会比较方便)求和为例.假设原数组是a[],树状数组是c[] ...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」极大团(最大完全子图)

极大团介绍描述：团就是最大完全子图。(极大团) 给定无向图G=(V,E)。如果U包含于V，且对任意u，v属于U且有(u，v)属于E，则称U是G的完全子图。 G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中，即U就是最大完全子图。 G的最大团是指G中所含顶点数最多的团。最大团： V中取K个顶点，两点间相互连接最大独立集： V中取K个顶点，两点间不...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」日期计算

日期计算介绍日期计算问题就是给出一个合法日期，计算此日期是星期几。这个涉及到一些历法和数学的知识，但是有很好用的公式可以使用。蔡勒公式 1582年10月4日之后：w=y1+(y1/4)+(c/4)-2*c+(26*(m+1)/10)+d-1; 1582年10月4日以及之前：w=y1+y/4+c/4-2*c+13*(m+1)/5+d+2; 输出：(w%7+7)%7 （...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」斯特林公式

斯特林公式简介斯特林公式的常见表示形式显而易见,这个公式主要是用来求近似的阶乘的值的,在竞赛中往往只采用第一个形式,其精确度已经足够用来求阶乘位数了. lg(n!)=lg(2πn)/2+n∗(lg(n)−lg(e)) 这个公式就是图中第一个式子左右同时求对数得到的. 不难发现,[10^x,10^(x+1) )之间囊括了所有长度为x+1的数,而lg(m*10^x)=x+l...

Posted by Dawn-K's Blog on August 6, 2019

Dawn-K's Blog

「CodeNote」链式前向星

「CodeNote」训练联盟第一场

「CodeNote」计算几何

「CodeNote」背包学习心得

「CodeNote」浮点误差

「CodeNote」树的直径

「CodeNote」树状数组

「CodeNote」极大团(最大完全子图)

「CodeNote」日期计算

「CodeNote」斯特林公式

FEATURED TAGS

ABOUT ME

FRIENDS

「CodeNote」 链式前向星

「CodeNote」 训练联盟第一场

「CodeNote」 计算几何

「CodeNote」 背包学习心得

「CodeNote」 浮点误差

「CodeNote」 树的直径

「CodeNote」 树状数组

「CodeNote」 极大团(最大完全子图)

「CodeNote」 日期计算

「CodeNote」 斯特林公式

FEATURED TAGS

ABOUT ME

FRIENDS

「CodeNote」链式前向星

「CodeNote」训练联盟第一场

「CodeNote」计算几何

「CodeNote」背包学习心得

「CodeNote」浮点误差

「CodeNote」树的直径

「CodeNote」树状数组

「CodeNote」极大团(最大完全子图)

「CodeNote」日期计算

「CodeNote」斯特林公式