GenmCai

题解

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

/ 注册

全部文章 / 题解（共23篇）

题解 | 《算法竞赛进阶指南》最短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

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

【题目】从这个整数中随机选取任意多个，输出所有可能的选择方案。每行一种方案。同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。对于没有选任何数的方案，输出空行。本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。【题解】 DFS，即深度优先搜索。深度、优先、搜索。即可以把单行...

DFS 递归枚举和暴力

2019-08-29

1 759

题解 | 《算法竞赛进阶指南》整数的一个小问题

【题目】给定长度为N的数列A，然后输入M行操作指令。第一类指令形如“C l r d”，表示把数列中第l~r个数都加d。第二类指令形如“Q X”，表示询问数列中第x个数的值。对于每个询问，输出一个整数表示答案。【题解】区间更新，单点查询，第一反应要么树状数组，要么线段树。个人更擅长线段树，就说说...

线段树

2019-08-27

0 547

题解 | 《算法竞赛进阶指南》没有上司的舞会

【题目】 Ural大学有N名职员，编号为1~N。他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数 HiHi 给出，其中。现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员...

树形dp

2019-08-27

0 821

题解 | 《算法竞赛进阶指南》你能回答这些问题吗（三）

【题目】给定长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：“1 x y”，查询区间 [x,y] 中的最大连续子段和，即 “2 x y”，把 A[x] 改成 y。对于每个查询指令，输出一个整数表示答案【题解】刚开始看的时候，单点更新，区间修改，第一反应就是线段树，但问题就出在求...

线段树

2019-08-27

1 796