GenmCai

分类

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

/ 注册

全部文章（共40篇）

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

【题目】从这个整数中随机选取任意多个，输出所有可能的选择方案。每行一种方案。同一行内的数必须升序排列，相邻两个数用恰好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

题解 | 《算法竞赛进阶指南》蒙德里安的梦想

【题目】 Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his 'toilet series' (where ...

状压dp

2019-08-26

0 802

题解 | 《算法竞赛进阶指南》最大子序和

【题目】输入一个长度为n的整数序列，从中找出一段不超过m的连续子序列，使得整个序列的和最大。例如 1,-3,5,1,-2,3当m=4时，S=5+1-2+3=7当m=2或m=3时，S=5+1=6 【题解】一开始没有想到可以用单调队列，以为能用dp之类的过过掉，但是莫得成功，寻思之后再想想。而单调队...

单调队列

2019-08-26

0 677

题解 | 《算法竞赛进阶指南》前缀统计

【题目】给定N个字符串，接下来进行M次询问，每次询问给定一个字符串T，求中有多少个字符串是T的前缀。输入字符串的总长度不超过，仅包含小写字母。【题解】 Trie的裸题，用C++11(clang++ 3.9)疯狂出现段错误，结果C++14(g++ 5.4)提交就A了，莫得找到原因在哪。这道题的Tr...

trie

2019-08-26

0 528

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

【题目】 You have N integers,.You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given i...

线段树

2019-08-26

0 682

题解 | 《算法竞赛进阶指南》64位整数乘法

【题目】求 a 乘 b 对 p 取模的值，其中【题解】普通的，在这个数据范围肯定是超出的，就算可以取余，但最坏的情况下，精度还是会溢出，在这种情况下我们就会想到快速幂。做法跟快速幂差不多，也是使用类似的反复翻倍法，即，,时间复杂度为，网上很戏谑的称这种做法是龟速乘，跟快速幂成鲜明对比。听说还...

龟速乘

2019-08-26

0 766

题解 | 《算法竞赛进阶指南》a^b

【题目】求 a 的 b 次方对 p 取模的值，其中【题解】因为数字过大，不管是精度还是时间都不够，所以得用快速幂。即利用,例:,。来简化的过程，要注意的是p=0的情况。时间复杂度： #include<iostream> #include<cstring> #inc...

快速幂

2019-08-26

0 731