boxxxx

算法

学习(10) 并查集(1) 数位dp(1) 概率dp(1) 线性dp(1) 题解(3)

/ 注册

全部文章 / 算法（共38篇）

洛谷p1233 sort+贪心

题目描述一堆木头棍子共有n根，每根棍子的长度和宽度都是已知的。棍子可以被一台机器一个接一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的：第一根棍子的准备时间为1分钟；如果刚处理完长度为L，宽度为W的棍子，那么如果下一个棍子长度为Li，宽度为Wi，并且满足L>＝Li...

2019-09-19

0 323

poj3169 差分约束

关于差分约束，我强推这位大佬的博客。https://blog.csdn.net/consciousman/article/details/53812818 题目是有的牛互相之间最多只能有一个距离，有的牛最少要达到一个距离。很容易写出不等式，由于是要求最大值，所以是要化为小于等于号，求最短路。 F[...

2019-09-19

0 407

洛谷p1993 差分约束+dfs版spfa

这道题算作是差分约束模板题了，关于差分约束，我强推这位大佬的博客。https://blog.csdn.net/consciousman/article/details/53812818 里面博客这段话就是解决这些题目的精髓了； (下面这段话是上面博客里面的） /******************...

2019-09-18

0 612

poj1655 dfs序+暴力

题意就是给你一棵树，然后去掉一个节点，求去掉哪个节点他的剩下的树的最大节点数最少。输出节点和最大子树节点数。由树dp专题看见这题，但是嘛。。。。。我第一眼都没意识到他是个dp。我的做法是这样的，就跑就只跑一遍dfs序，然后途中记录一下每个节点的父亲是谁。在暴力跑每一个点的答案。遍历每一个点的答...

2019-09-12

0 450

hdu4514 并查集+树直径

这道题题目就是说给你一个图，然后判断能不能成环，不能成环就输出最长的那一条路。首先分析问题。怎么判断环？这是图中一个很常见的问题，在无向图中判环我们可以用并查集，在有向图中可以使用tarjan或者拓扑排序。这个问题是无向图，那么就用并查集就好了，在输入图的过程就可以判断，每当有一条线，我们就找这...

2019-09-12

0 478

洛谷P1972(树状数组+离线)

题目描述 HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实...

2019-08-19

0 518

hdu3974 （dfs序+线段树）

问题：有一家公司有N个员工(从1到N)，公司里每个员工都有一个直接的老板(除了整个公司的领导)。如果你是某人的直接老板，那个人就是你的下属，他的所有下属也都是你的下属。如果你是没有人的老板，那么你就没有下属，没有直接老板的员工就是整个公司的领导，也就是说N个员工构成了一棵树。公司通常把一些任务分配给...

2019-08-18

0 506

hdu1540（线段树+二分）

问题：在抗日战争期间，华北平原广大地区进行了大规模的隧道战。一般来说，通过隧道连接的村庄排成一列。除了两端，每个村庄都与两个相邻的村庄直接相连。入侵者经常对一些村庄发动袭击并摧毁其中的部分隧道。八路军指挥官要求最新的隧道和村庄连接状态。如果某些村庄严重隔离，必须立即恢复连接！输入：输入的...

2019-08-17

0 695