GenmCai

分类

ACM(1) C++(2) C\C++(1) Git(1) Linux(1) Python(2) shell(3) 算法和数据结构(6) 题解(23)

/ 注册

全部文章（共40篇）

排序算法——希尔排序

希尔排序我对希尔排序进行学习的博客：希尔排序–简单易懂图解前言可以说是一个加强版的插入排序。在插入排序中，最好的时间复杂度是 O ( ...

2020-01-02

0 563

排序算法——桶排序

桶排序前言桶排序是一个在时间复杂度和空间复杂度十分极端的算法，它的时间复杂度可以达到 O ( N ...

2020-01-02

0 2941

排序算法——基数排序

基数排序基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部分资讯，将要排序的元素分配至“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为...

2020-01-02

0 438

排序算法——快速排序

快速排序基本做法在此我们使用递归的快速排序。既然使用了递归，自然就是要解决一些重复的子任务，然后完成最后的大任务，而大任务自然就是让整个数组整体有序，那需要重复的小任务是什么呢？快排的一个个子任务，就是要在各自范围内的数组中取一个数当基准数（一般取范围内的最左边、最右边或中间的数），...

2020-01-02

0 611

题解 | 《算法竞赛进阶指南》最短Hamilton路径

【题目】给定一张个点的带权无向图，点从标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。【题解】状压dp裸题，即用状压思想压缩所有的可能的状态，把其变为二进制。而二进制上的第位，则代表第个点，而位置上...

状压dp

2019-09-08

0 616

题解 | 《算法竞赛进阶指南》interval GCD

【题目】给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。2、“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。对于每个询问，输出一个整数表示答案。【题解】 ...

线段树

2019-09-08

0 857

题解 | 《算法竞赛进阶指南》直方图中最大的矩形

【题目】 A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have differ...

单调栈

2019-09-05

4 683

题解 | 《算法竞赛进阶指南》快速幂基础

【题目】 People are different. Some secretly read magazines full of interesting girls' pictures, others create an A-bomb in their cellar, others like usin...

快速幂

2019-08-30

1 696

题解 | 《算法竞赛进阶指南》递归实现排列型枚举

【题目】把这个整数排成一行后随机打乱顺序，输出所有可能的次序。按照从小到大的顺序输出所有方案，每行1个。首先，同一行相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。【题解】循环遍历1-N个数，优先遍历小的数，让其尽可能的选遍历到的数。并需...

DFS 递归枚举和暴力

2019-08-29

0 742

题解 | 《算法竞赛进阶指南》递归实现组合型枚举

【题目】从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。, , 。按照从小到大的顺序输出所有方案，每行1个。首先，同一行内的数升序排列，相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 9 12排在1 3 10 11前...

DFS 递归枚举和暴力

2019-08-29

2 695