boxxxx

分类

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

/ 注册

全部文章（共55篇）

hdu4514 并查集+树直径

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

2019-09-12

0 478

ST表的动态规划方程解释

在我学st表的时候，对于动态规划方程总是有点不理解，我相信肯定也有人会遇见同样的问题，我就把我现在对于这个方程的理解说一说。ST表的数组st[i][j]是指以i为左端点，含有2^j个数的闭区间（包含了i）；那么对于st[i][j]所代表的区间就是 [i,i+2^j-1]；（如果不减1就多了一个数了，...

2019-08-27

0 452

洛谷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