Rewinner

分类

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

/ 注册

全部文章（共136篇）

树链剖分【学习 + 洛谷P3384】

树链剖分 LCA: Nearest Common Ancestors 【POJ 1330】求树上两个结点的最近公共祖先(LCA) 树上差分： Network【POJ 3417】 DFS序：Apple Tree【POJ 3321】要求要求你进行上述五种操作...

2019-03-31

0 472

CodeForces - 1051F 【LCA + 最短路】

传送门大概题意给你一个包含n个点m条无向边的图，多次询问最短路(保证每两个点都连通，m - n ≤ 20 )思路我们要注意题面上给你的条件( m - n ≤ 20 )，这是一个很重要的信息。我们知道含有n个结点的树包含 n - 1 条边，这道题相当于在树上又多加了几条边。如果给我们一棵树，多...

2019-03-30

0 611

HDU - 3830 Checkers【思维+LCA】

传送门 Problem Description Little X, Little Y and Little Z are playing checkers when Little Y is annoyed. So he wants to make the chessboard m...

2019-03-29

0 465

POJ 3728 The merchant 【在线LCA+细节】

传送门题意：一个国家有N个城市，每对城市之间只有一条简单的道路。商人选择了一些道路，并希望在每条道路上赚尽可能多的钱。当他沿着一条道路移动时，他可以选择一个城市购买一些商品，然后在一个城市中出售。所有城市的商品都一样，但价格不同。现在，您的任务是计算每条路径上可能的最大利润。解析：这道题...

2019-03-28

0 447

POJ3417 Network【LCA+树上差分】

传送门 Description Yixght is a manager of the company called SzqNetwork(SN). Now she's very worried because she has just received a bad news which deno...

2019-03-28

0 484

DFS序学习+例题

什么是DFS序? DFS序就是指一棵树被DFS时所经过的节点的顺序 DFS序就是将树形结构转化为线性结构，用DFS遍历一遍这棵树，进入到x节点有一个in时间戳，递归退出时有一个out时间戳，x节点的两个时间戳之间遍历到的点，就是根为x的子树的所有节点。时间戳时间戳记录第一...

2019-03-27

0 569

POJ 3694 Network【Tanjan+LCA+并查集】

题目链接题目描述网络管理员管理大型网络。该网络由N台计算机和成对计算机之间的M链路组成。任何一对计算机都通过连续的链接直接或间接连接，因此可以在任何两台计算机之间转换数据。管理员发现某些链接对网络至关重要，因为任何一个链接的故障都可能导致某些计算机之间无法转换数据。他把这种联系称为桥梁。他计划...

2019-03-26

0 521

二分题解

二分做的人不是特别多，可能是我讲的不够好，大家都没有听明白。。。。我挂的题都不是特别难，只要你能够理解二分的思想，并能够应用的话，解决这些题应该不难。题解只提供思想，代码靠你们自己去实现 Doors Breaking and Repairing 给你一个n个们，每个人有一个防御值，每...

2019-03-23

0 412

图的割点学习+模板题【Tanjan】

什么叫做割点？在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。图中c就是一个割点，剩下{A,B}和{C,D}两个连通分量实现原理：在学习割点的基础上应该了解什么是连通分量和T...

2019-03-22

0 649

【2-SAT初学+模板题讲解】POJ3683 Priest John's Busiest Day

什么是2-SAT? SAT是适定性(Satisfiability)问题的简称。一般形式为k-适定性问题，简称 k-SAT。可以证明，当k>2时，k-SAT是NP完全的。因此一般讨论的是k=2的情况，即2-SAT问题。我们通俗的说，就是给你n个变量ai，每个变量能且只能取0...

2019-03-21

0 635