- 博客(32)
- 收藏
- 关注
RSS订阅原创 树的直径&基环树&单调队列
树的直径定义：树中最远的两个节点之间的距离被称为树的直径。 怎么求呢？有两种官方的算法（不要问官方指谁我也不晓得）：1.两次搜索。首先任选一个点，从它开始搜索，找到离它最远的节点x。然后从x开始搜索，找到离x最远的点y，那 么E(x, y)的长度就是树的直径。时间复杂度为O(n)。2.树形dp。这种其实更好写。我们可以对于某个节点x，分别求出经过它的最长链的长度。怎么求呢？首先，枚举x...
2019-03-21 19:18:35
586
原创 位运算:lowbit运算
位运算里有一种十分基础的运算：lowbit运算。 lowbit(n)定义为非负整数n在二进制表示下“最低为的1及其后边所有的0”构成的数值。例如n=10的二进制表示为（2）1010， 则lowbit(n)=2=(2)10。 ————摘自《算...
2018-11-22 22:03:26
1701
原创 位运算:最短Hamilton路径
描述给定一张 n(n≤20) 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。输入格式第一行一个整数n。接下来n行每行n个整数，其中第i行第j个整数表示点i到j的距离（一个不超过10^7的正整数，记为a[i,j]）。对于任意的x,y,z，数据保证 a...
2018-11-18 21:51:13
517
1
原创 DP的三种常见做法
1.记忆化搜索是最容易写,也是效率较高的一种做法.虽然本质上是搜索,但是对搜索过的状态就不再搜索就相当于由已知的来推导未知的,实际上也是DP.通常我们用DFS做,并用一个dp数组来存状态.例题:>记忆化搜索 : 滑雪< 2.填表法是最常用的做DP题的方法.即以未知的量为基础,通过已知的量来刷新当前的未知量.这种方法用循环就能做.比如背包问题就是填表...
2018-10-15 23:55:33
564
1
原创 质数:试除法
若单判定一个数是不是质数,我们通常会用到试除法.这个算法会从2~√N枚举每一个数,若有一个数能整除N,那么N就是合数,反之是质数.#include <iostream>using namespace std;bool is_prime(const int &n){ for(int i = 2; i * i <= n; i++) if(n ...
2018-10-12 19:52:53
493
原创 质数:线性筛法
对于之前的Eratosthenes,它的时间复杂度是O(NloglogN),虽然十分接近线性,但是仍有合数被多次标记的情况.比如12,就算从x²开始检索,12也会被2和3同时标记.因此并不是最优解. 本篇题解要讲的线性筛法,基本思路即通过质因子来标记合数,首先像其它筛法一样从2~N枚举每个数.如果这个数是质数,那就将它存起来.然后无论它是不是质数,都扫描每个不大于...
2018-10-12 19:39:52
458
原创 质数:Eratosthenes筛法
筛出1~n之间的所有质数. Eratosthenes筛法,即找到一个质数x后,把x的倍数2x,3x...(n/x)*x都标记为质数.当扫描到一个数时,若没有被标记过就说明它是质数,反之不是质数.大致过程如下:2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1...
2018-10-11 00:06:13
218
原创 算法模板:广度优先搜索BFS
广度优先搜索,就是从一个节点开始搜索,搜索完毕后,再从它四周的未访问过的节点开始搜索,重复之前的操作.它就像水波扩散一样. 广搜的基础问题就是:给定一个迷宫,求最短多少步可以走到终点.其中'S'为起点,'T'为终点,'.'为道路,'*'为墙.很显然有墙的地方就不能走.为了我们在搜索完一个节点后将节点周围的点存起来准备搜索,同时又不能打乱搜索的顺序,所以我们可以用q...
2018-10-10 21:44:21
289
原创 基础数据结构：队列queue
队列(queue)在c++中是一种线性的基础数据结构,它的操作受算法的限制.队列就好比生活当中的排队,不考虑插队的情况下你总是先进入队列的先离开,后进入队列的就后离开.所以队列每次只能取队首的值,每次只能从队尾加入数据. 关于队列的基本操作:1.入队(push);2.出队(pop);3.判断队列是否为空(empty);4.统计队列元素的个数(size)...
2018-10-10 00:08:48
129
原创 洛谷：P1434【滑雪】
题目描述Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 ...
2018-10-09 21:58:40
491
原创 高精度乘法
与高精度加法一样,将乘法模拟着竖式来做:#include <iostream>#include <cstring>#define maxn 10000000 + 5using namespace std;int a[maxn], b[maxn], c[maxn];string in;int l1, l2, l3;bool tmp; ...
2018-10-03 19:09:54
138
原创 洛谷：P1853 【投资的最大效益】
题目背景约翰先生获得了一大笔遗产，他暂时还用不上这一笔钱，他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券，每一种债券都能在固定的投资后，提供稳定的年利息。当然，每一种债券的投资额是不同的，一般来说，投资越大，收益也越大，而且，每一年还可以根据资金总额的增加，更换收益更大的债券。题目描述例如：有如下两种不同的债券：①投资额$4000，年利息$400；②投资额$3000，年...
2018-10-03 16:21:45
414
原创 洛谷：P1616 【疯狂的采药】
题目背景此题为NOIP2005普及组第三题的疯狂版。此题为纪念LiYuxiang而生。题目描述LiYuxiang是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一...
2018-10-03 16:19:41
172
原创 洛谷：P1507 【NASA的食物计划】
题目背景NASA(美国航空航天局)因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋,因此在各方压力下终止了航天飞机的历史,但是此类事情会不会在以后发生，谁也无法保证,在遇到这类航天问题时,解决方法也许只能让航天员出仓维修,但是多次的维修会消耗航天员大量的能量,因此NASA便想设计一种食品方案,让体积和承重有限的条件下多装载一些高卡路里的食物.题目描述航天飞机的体积有限,当然如果载过重...
2018-10-03 16:17:58
236
原创 洛谷：P1504 【积木城堡】
题目描述XC的儿子小XC最喜欢玩的游戏用积木垒漂亮的城堡。城堡是用一些立方体的积木垒成的，城堡的每一层是一块积木。小XC是一个比他爸爸XC还聪明的孩子，他发现垒城堡的时候，如果下面的积木比上面的积木大，那么城堡便不容易倒。所以他在垒城堡的时候总是遵循这样的规则。小XC想把自己垒的城堡送给幼儿园里漂亮的女孩子们，这样可以增加他的好感度。为了公平起见，他决定把送给每个女孩子一样高的城堡，这样可...
2018-10-03 16:15:46
789
原创 洛谷:P1060 【开心的金明】
题目描述金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过NN元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的NN元。于是，他把每件物品规定了一个重要度，分为55等：用整数1-51−5表示，第55等最重要。他还从因特网上查到了每件物品的价格...
2018-10-03 16:12:25
345
原创 01背包
01背包Description一个旅行者有一个最多能装 M 公斤的背包，现在有 n 件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn，求旅行者能获得最大总价值。Input第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；第2..N+1行：每行二个整数Wi，Ci，表示每个物品的重量和价值。Output仅一行，...
2018-10-03 16:09:46
181
原创 高精度加法（A+B问题）
A+B，作为算法竞赛中最难的一题（雾），总是吸引着广大程序员想尽一切算法想要去AC它：这里提供一种高精度的做法：#include <iostream>#define maxn 10000000 + 5using namespace std;string in;int a[maxn], b[maxn], c[maxn];//分别为两个加数、和int l1, l2, ...
2018-09-30 20:55:34
601
原创 位运算：a^b
手写快速幂函数。 由于这里需要对p取模，而且p在int范围内，所以不需要高精度。所以就用位运算吧。这里仍然要用到二进制的思想，将b转为2进制来做。eg. ∵11 = 1011(2) = 1 * 2^3 + 0 * 2 ^2 + 1 * 2^1 + 1 * 2^0，∴2^11 = 2^(1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0) = 2...
2018-09-24 00:10:11
344
原创 位运算：64位整数的乘法
由于有对p取模的操作，就显然不是高精度算法，而且p的范围在long long以内。所以我们不妨试试位运算，并结合一下快速幂的思想。我们可以将b转成2进制数。eg. ∵11 =1011(2) = 1 * 2^3 + 0 * 2^2 + 1 * 2^1 +1 * 2^0，∴2*11 = 2*(1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0) = 2*(2^3) +...
2018-09-23 23:55:14
482
原创 浅谈位运算
位运算是计算机的底层运算，让计算机来还做是相当快的。 那么随之而来的就是位运算的运算符，类似于逻辑门电路。取反对一个二进制数的每一位进行逻辑去反，符号为 ~。 eg. ~0111（十进制7） = 1000（十进制8）。但是如果这样写：printf("%d", ~7);则会得到-8。但是并没有任何问题。因为每个整数实数变量的第一个二进制位都是用来存符号的，代表...
2018-09-23 23:37:52
129
原创 采药
题目描述辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是...
2018-07-27 19:04:24
364
原创 计蒜客：逃生
逃生Description小信在玩一款逃生的游戏。在一个 n×m 的矩形地图上，小信位于其中一个点。地图上每个格子有加血的药剂，和掉血的火焰，药剂的药效不同，火焰的大小也不同，每个格子上有一个数字，如果格子上的数字是正数说明是一个药剂代表增加的生命值，如果是负数说明是火焰代表失去的生命值。小信初始化有 v 点血量，他的血量上限是 c，任何时刻他的生命值都不能大于血量上限，如果血量为 0...
2018-07-23 18:51:34
305
1
原创 计蒜客：杨辉三角
Description杨辉三角是二项式系数在三角形中的一种几何排列。它的每个数等于它上方两数之和，每行数字左右对称，由 1 开始逐渐变大。 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1请求出杨辉三角的第 ...
2018-07-21 12:58:27
213
原创 结构体和排序
结构体，即将一个或者多个变量打包起来的整体。定义结构体的格式如下：struct 结构体名称{ 变量类型 变量名;}结构体变量名；或者：struct 结构体名称{ 变量类型 变量名;}结构体名称 结构体变量名;例如，一个学生的姓名、年龄、身高可以这样包装：struct node{ string name; int age; fl...
2018-07-21 08:11:57
3025
原创 计蒜客：墙壁涂色
墙壁涂色Description蒜头君觉得白色的墙面好单调，他决定给房间的墙面涂上颜色。他买了 3 种颜料分别是红、黄、蓝，然后把房间的墙壁竖直地划分成 nn 个部分，蒜头希望每个相邻的部分颜色不能相同。他想知道一共有多少种给房间上色的方案。例如，当 n=5 时，下面就是一种合法方案。蓝|红|黄|红|黄由于墙壁是一个环形，所以下面这个方案就是不合法的。蓝|红|黄|红|蓝Inp...
2018-07-21 00:08:33
507
原创 函数与递归
说到函数，相信大家对此并不陌生。在c++中有许多函数，比如abs()、fabs()、sort()等等。我们自己也可以写函数。基本结构如下：函数类型 函数名(参数类型 参数名){ 语句; return 与函数类型相同的变量的值;}这里的函数类型可以是int、float、char、bool、string等等，对应的返回值类型与函数的类型应该相同。如果函数不需要返回值，则函数...
2018-07-19 00:06:19
352
原创 二分查找
二分是一种十分高效的工具，使用二分可以节省大量的时间。我们首先通过一个小练习来初步熟悉一下二分（转自YCOJ）：请问最后将输出什么呢？ 答案是4343（两个43）。通过这些，相信读者已经对二分有了初步的认识。接下来做一些二分的习题：查找Description给出一个有 n 个元素的数列 a 和两个整数 k 和 s，其中数列 a 的元素是按照升序排列的。请你在数列...
2018-07-18 19:36:12
556
1
原创 字符串
本篇将介绍一种新的变量类型：字符串。字符串与字符数组不同的地方就在于：字符数组的大小在声明时就已经定了下来；而字符串的大小是可以改变的，当你往字符串里面添加元素时，字符串的大小也会相应地改变。下面介绍对于字符串的操作（转载自YCOJ）：s.size(); // 得到字符串长度s.find(); // 查找字符或子串所在位置,若存在子串则返回子串开头字符下标，否则返回-1 s...
2018-07-18 15:57:17
1795
1
原创 循环
循环，即重复执行命令。c++中常见的循环有三种：for循环、while循环和do-while循环。基本的结构如下：for循环：for(变量;条件;命令){ 语句;}while循环：while(条件){ 语句;}do-while循环：do{ 语句;}while(条件);下面给出一个例子：int sum = 0;for(int i...
2018-07-18 13:31:20
753
原创 条件分支
这篇文章将总结一下c++的条件分支。在这之前，我先总结一下c++的判断符。c++判断符有：>, <, ==, >=, <=, !=。其中，==的用处是判断符号两边是否相等，>=用来判断符号左边是否大于等于右边，<=用来判断符号左边是否小于等于右边，!=用来判断两边是否不等。这里要特别注意，判断相等是用==而不是=，一个等号是用来赋值的。这里你可以在编译器...
2018-07-18 12:27:28
1641
原创 c++入门
本来很不想写这个的，但是又不想自己的博客有头没尾，所以就写一点，，，c++最基础的数据类型有整数类型（int）、实数类型（float）、字符类型（char）和布尔类型（bool）。在定义的时候只需要写上“变量类型 变量名”就可以了。说道变量又不得不谈谈精度的问题。int和float都是有精度之分的。单精度的整数变量类型就叫做int，双精度的叫做long long（顾名思义， 就是很长的数的...
2018-07-18 12:27:18
1759
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人