弓长九日

分类

CDQ(1) codeforces(1) DP(9) SSM框架(3) 《算法竞赛进阶指南》杂谈(14) 二分(1) 分块(1) 动态规划(1) 图论(11) 基本算法(5) 字符串(6) 差分(2) 并查集(2) 思维(18) 搜索(7) 数学(16) 数据结构(17) 未归档(128) 树型结构(4) 树套数(1) 模拟(2) 爬虫(6) 系统配置记录(1) 线段树(8) 计算机网络(2) 贪心(2) 面试(3) 题解(4) 题集(45)

/ 注册

全部文章（共313篇）

差分总结三练习题闇の連鎖+2015沈阳网络赛 HDU 5452 Minimum Cut

下面2题差不多都是边差分闇の連鎖 https://www.acwing.com/problem/content/354/ 这个题删一个树边和一个非树边让树不连通那样删一个经过边是 0 的树边和删一个经过边是 1 的树边才能成功前置是 m0 * m 数量后者是...

2019-09-12

0 599

差分总结二树上差分

树上差分模板题 P3128 [USACO15DEC]最大流Max Flow https://www.luogu.org/problem/P3128 找这个树上重复经过的最多点经过几次看这名字就醉了orz 这题是树上差分模板题点差分点差分的话由于 lca 本身是有贡献的那么d...

2019-09-12

0 659

差分总结一技巧和思维

P1083 借教室 https://www.luogu.org/problem/P1083 二分位置我们可以用差分数组确定每天用多少教室 #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10...

2019-09-11

0 567

回文树总结二 2019徐州网络赛 Colorful String 和湖南大学第十五届程序设计竞赛 H.Longest Common Palindrome Substring

Colorful String 问你每个回文串有多少不同字符累和输出回文树统计回文串 DFS遍历所有回文串统计 https://nanti.jisuanke.com/t/41389 #include <bits/stdc++.h> using namespace st...

2019-09-10

0 640

回文树总结一模板+20142015-acmicpc-asia-xian-regional-contest 回文树上DFS

回文串 HYSBZ - 3676 模板 https://vjudge.net/problem/HYSBZ-3676#author=0 #include <bits/stdc++.h> using namespace std; const int maxn = 300005;// n...

2019-09-10

0 504

[概率期望DP] 2019 南京网络赛 D.Robot 绿豆蛙的归宿

绿豆蛙的归宿 https://www.luogu.org/problem/P4316 首先这道题是在图上dp的一个标准板子题一般意义上我们需要每个点的转移方程但是这是一个图所以我们考虑拓扑同时每个点连的边数也是需要考虑变成转移系数这样就有了我们算法进阶指南书上代码很好理解但...

2019-09-08

0 729

可持久化并查集可持久化数组 + 并查集

可持久化并查集没有想到这么好写就是用可持久化数组维护了我们并查集之前的fa 数字和 dep 数组从历史版本合并查询当然这里我们不能路径压缩只能安秩合并降低复杂度路径压缩复杂度是均摊的，无法可持久化(复杂度可以被卡成暴力) https://www.acwing.co...

2019-09-05

0 694

[树链剖分] P3313 [SDOI2014]旅行(动态开点线段树)

P3313 [SDOI2014]旅行 https://www.luogu.org/problem/P3313 我们单点修改城市的信仰和开销询问路径上同信仰的城市开销的花费和 or路径上最大值显然我们树链剖分完直接建立 1e5 颗线段树是最方便的而且是单点修改确保了我们时间...

2019-09-03

0 878

树链剖分题型总结二

P1505 [国家集训队]旅游 https://www.luogu.org/problem/P1505 这道题是边剖我们要注意的是我们的一条边上路权可以分配给这条树下深度较深的节点上边权转点权就好而且更要注意的是我们的LCA 这个点的权不应该算入因为他算上了他父亲到他的路 ...

2019-09-03

0 418

树链剖分题型总结一

树链剖分模板题首先是树链剖分模板题一般的我将树按轻重儿子建立DFS序列 dfs1 处理轻重儿子子树大小之后的dfs2 就方便处理轻重链的分离了从而线段数维护 dfs序列将一个树上问题转到区间一维的性质1 如果边 ...

2019-09-03

0 427