Rewinner

未归档

ACM(1) dfsdd(1) DP(6) hash(1) STL(1) 图论(24) 小技巧(4) 思维(6) 搜索(2) 数学(5) 数据结构(16)

/ 注册

全部文章 / 未归档（共69篇）

欧拉图【模板+例题】

例题：UOJ 117 欧拉回路参考博客：https://www.cnblogs.com/Ash-ly/p/5397702.html （其中有向图的入度和出度好像写反了） https://blog.csdn.net/yzyyylx/article/details...

2019-03-04

0 568

曼哈顿最小生成树【模板题】

模板题：POJ 3241 曼哈顿最小生成树：给定二维平面上的N个点，在两点之间连边的代价为其曼哈顿距离，求使所有点连通的最小代价。朴素的算法可以用O(N2)的Prim，或者处理出所有边做Kruskal，但在这里总边数有O(N2)条，所以Kruskal的复杂度变成了O(N2logN)。结论：以...

2019-03-03

0 949

POJ 1679 The Unique MST【次小生成树模板】

传送门 Description Given a connected undirected graph, tell if its minimum spanning tree is unique. Definition 1 (Spanning Tree): Consider a connected...

2019-03-02

0 445

【LCA模板】Tanjar + 倍增LCA

Tanjar+并查集（离线查询）参考博客：https://www.cnblogs.com/jsawz/p/6723221.html #include<cstdio> #define N 420000 struct hehe{ int next; int to; ...

2019-02-28

0 516

Power OJ 2826 有趣的游戏【Tanjar缩点+DAG最长路】

传送门 Description 一天wangshu迷上了一个十分有趣的游戏，名为sdfsfgdsfsdfsdfse，在在游戏里你需要从一个起始补给点开始去寻找装备，每一个补给点都有一定价值的装备，最后从出口补给点出去，这个游戏十分有趣，所以当你离开一个补给点后这个补给点会重生和原来一样...

2019-02-26

0 503

强连通图的算法【Tarjan】+ 【HDU1269】迷宫城堡

参考博客：https://blog.csdn.net/justlovetao/article/details/6673602 https://blog.csdn.net/qq_16234613/article/details/77431043 （代码含有注...

2019-02-23

0 721

HDU 5040 Instrusive 【BFS+优先队列】

题意：你需要从M走到T，‘ # ’表示障碍不能走，‘ . ’表示道路，路上有W E N S的四种摄像头,每一秒钟会顺时针旋转一次，你拥有一个纸盒子（藏在纸盒子里不会被看到），你可以藏在纸盒子走需要花费3s，藏在纸盒子里原地不动1s，移动一步1s.到达T点所需要的时间。思路：很容易想到 bfs+...

2019-02-08

0 434

【HDU 4348】 To the moon 可持久化线段树

题目链接：传送门简述题意：一个长度为n的数组，4种操作：　　　　（1）C l r d：区间[l,r]中的数都加1，同时当前的时间戳加1 。　　　　（2）Q l r：查询当前时间戳区间[l,r]中所有数的和。　　　　（3）H l r t：查询时间戳t区间[l,r]的和。　...

2019-01-25

0 595

树形DP求树的直径讲解+例题

例题：HDU 2196 Computer（树形dp经典）传送门证明：原文：https://blog.csdn.net/shuangde800/article/details/9732825 把无根树转化成有根树分析，对于上面那棵树，要求距结点2的最长距离，那么，就需要知道以2...

2019-01-21

0 620

树形DP求树的直径【模板】

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int const MAX = 100005; int head[MAX], dp[MAX][2]...

2019-01-21

0 432