【题目描述】已知线段的两个端点的坐标A(Xa,Ya),B(Xb,Yb)，求线段AB的长度，保留到小数点后3位。【输入】第一行是两个实数Xa，Ya，即A的坐标。第二行是两个实数Xb，Yb，即B的坐标。输入中所有实数的绝对值均不超过10000。【输出】一个实数，即线段AB的长度，保留到小数点后3位。【输入样例】1 1 2 2【输出样例】1.414【源...

NVIDIA 第七届 SkyHackathon 笔记

【概述】越底层的函数，调用越频繁，那么最底层的数学运算函数的优化至关重要。当求逆平方根时，一般做法都是用函数返回 1/sqrt(x)，但在 雷神之锤3 中，有一快速求逆平方根的算法。【知识储备】1.单精度浮点数的存储在计算机中，单精度浮点数使用 32 位来存储，其中，最高位为符号位，后面 8 位为整数位，代表浮点数的指数，再后面 23 位代表小数部分，依次表示、、......

【概述】给定一个有向图与一个起点 S，如果要去掉起点 S 到某个点 p 的中间的某个点 x后无法到达，那么称点 x 支配点 p，x 是 p 的一个支配点。显然支配点 x 可以有多个，支配点的集合记为 {Xp}，对于起点以为的点，它们都有两个平凡的支配点，一个是其自身，一个是起点。在支配 p 的点中，若一个支配点 i≠p，满足 i 被 p 剩下的所有非平凡的支配点支配，则称 i 为...

【本文思路】整理自 CDQ 巨佬的弦图与区间图，具体内容：点击这里【概述】1.基本概念设有图 G=(V,E)，则：当 V'∈V,E'∈E 时，图 G'=(V',E') 是图 G 的子图当 V'∈V,E'={∀x∈V',∀y∈V',(x,y)∈E'} 时，G'(V',E') 是图 G的诱导子图当 G′是图 G的子图，且 G′是关于 V′ 的完全图时，子图 G' 为...

【概述】高斯消元法主要用于求解线性方程组，也可以求矩阵的秩、矩阵的逆等，是一个重要的数学方法。其时间复杂度主要与方程组个数、方程组未知数个数有关，一般来说，时间复杂度为 O(n^3)【线性方程组】线性方程组：有多个未知数，且每个未知数的次数均为一次，这样多个未知数所组成的方程组。其形式为：记为矩阵形式，有：【高斯消元法】高斯消元法的基本思想是：通过一系列的加减...

【基本概念】哈密尔顿通路：经过图中每个结点且仅经过一次的通路。哈密尔顿回路：经过图中每个结点且仅经过一次的回路。哈密尔顿图：存在哈密尔顿回路的图。竞赛图：每对顶点之间都有一条边相连的有向图，n 个顶点的竞赛图称为 n 阶竞赛图。与欧拉回路的对比：欧拉回路是指不重复地走过所有路径的回路；哈密尔顿回路是指不重复地走过所有点并且最后回到起点的回路。【判定】1.哈密尔顿通路的判定...

【基本概念】1.连通图与连通分量1）连通图：无向图 G 中，若对任意两点，从顶点 Vi 到顶点 Vj 有路径，则称 Vi 和 Vj 是连通的，图 G 是一连通图2）连通分量：无向图 G 的连通子图称为 G 的连通分量任何连通图的连通分量只有一个，即其自身，而非连通的无向图有多个连通分量以上图为例，总共有四个连通分量，分别是：ABCD、E、FG、HI。...

NVIDIA 第七届 SkyHackathon 笔记

【问题描述】当 G′是图 G的子图，且 G′是关于 V′ 的完全图时，子图 G' 为图 G 的团；当 G' 是团，且不是其他团的子集时，G' 为图 G 的极大团；当 G' 是极大团时，且点数最多，G' 为图 G 最大团当 G′ 中所有点不相邻，最大点集最大的图 G′ 为图 G 的最大独立集，且最大独立集数=补图的最大团当用个数最少的团覆盖图 G 所有的点时，称为最小团覆盖...