申屠志刚

申屠志刚的ACM之路

ACM(1) C(128) C++(380) C.++(1) CTF(44) C语言(34) DP(4) JAVA(2) Python(1) 博弈论(1) 并查集(2) 最小生成树(1) 最短路(2) 未归档(435) 浙江理工大学2018年10月赛(2) 生成树(1) 申屠志刚的CTF之路(2) 矩阵(1) 线段树(1) 经典问题(1) 背包问题(1) 语法(1)

/ 注册

全部文章 / 申屠志刚的ACM之路（共37篇）

扫描线

扫描线是一种用来处理矩形相交的面积问题的算法渐近时间复杂度约为O(nlogn)O(nlogn) Q1. 在坐标系给定n个矩形(以左下/右上角坐标给出) 求这些矩形面积的并例如下图 n=2 矩形1: (1,1) (3,3) 矩形2: (2,2) (4,4) A1. 扫描线的过程大...

2018-10-29

0 548

背包问题-C++

第一讲 01背包题目给定物品个数n,背包容量v,每个物品都有一个体积c和价值w,要求向背包中装物品使得总价值最高. 基本思路状态表示:f(i,j)表示前i个物品试图装入一个容量为j的背包的最大价值. 边界情况:f(0,j)=0. 状态转移:f(i,j)=max(f(i-1,j)...

2018-10-20

0 768

sort()函数

用于C++中，对给定区间所有元素进行排序。头文件是 #include <algorithm> using namespace std sort函数见下表: 函数名功能描述 sort 对给定区间所有元素进行排...

2018-10-17

0 0

哈夫曼树

1、哈夫曼树的基本概念 ---- 哈夫曼（Huffman）树又称作最优二叉树，它是n个带权叶子结点构成的所有二叉树中，带权路径长度最小的二叉树。 ---- “路径”就是从树中的一个结点到另一个结点之间的分支构成的部分，而分支的数目就是路径长度。 ---- 树的路径长度：就是从树根到每一结点的...

2018-10-14

0 498

DFS(深度优先搜索算法)

深度优先搜索算法（英语：Depth-First-Search，简称DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。...

2018-10-07

0 394

斐波那契数列的前n项值

Description 输入n，求斐波那契数列前n项的值。斐波那契数列规律如下：1， 1， 2， 3， 5， 8， 13，21， 34，55…,从第三项开始，每一项都是前面两项的和。 Input 输入正整数n。 Output 输出斐波那契数列的前n项值 Sample Input 1 3 5 8...

2018-09-26

0 625

九九乘法表

Description 还记得以前小学时的九九乘法口诀吧。现在要求你编写程序打印出乘法口诀。不过现在的乘法口诀表跟以前稍微有点区别，我告诉你一个数字n( 1 <= n <= 9),你要给我打出相应的nn乘法口诀表。 Input 多个测试数据。每个测试数据一行，输入整数n. Outp...

2018-09-25

0 814