回归梦想

分类

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2) 题解(271)

/ 注册

TA的专栏 41篇文章 0人订阅

16篇文章 978人学习

牛客每日一题

6篇文章 776人学习

0篇文章 0人学习

0篇文章 0人学习

0篇文章 0人学习

3篇文章 685人学习

ACwing寒假每日一题（提高组）

3篇文章 780人学习

13篇文章 912人学习

全部文章（共1124篇）

P4178 Tree

P4178 Tree 题意：给定一棵 n 个节点的树，每条边有边权，求出树上两点距离小于等于 k 的点对数量。题解：点分治的模板题是求等于K的路径条数本题是求小于等于K的路径条数，我们只需要改变统计答案即可原本统计答案是对一个路劲长度len，判断K-len在之前的子树中出现多少次，用f数组来记...

**** 点分治

2021-02-23

0 681

P4381 [IOI2008]Island

P4381 [IOI2008]Island 题意：给你一棵基环树森林，求出基环树的直径之和. 题解：对于基环树,我们将环看作根,那么直径有两种情况:: 1.不经过环,也就是环上某个点的子树内部,对于这种情况,直接在子树内部处理直径,更新答案即可; 2.经过环,答案就是i的子树内长度+j的子树内长...

ing **** 基环树

2021-02-22

0 665

P2607 [ZJOI2008]骑士

P2607 [ZJOI2008]骑士题意： n个点n个边，每个点都有权值，相邻的点不能同时选择，问如何选择能使得权值最大题解：这个题很有P1352 没有上司的舞会这个题的感觉，唯一的区别是那个题保证是树，而本题肯定不是树，而是基环树也就是本题中，每一个连通块有且只有一个环，所以我们找到这个环并...

基环树树形dp ***

2021-02-22

0 613

P1352 没有上司的舞会

P1352 没有上司的舞会题意：给你一个树，每个点都有权值，选择一些点使得权值和最大，要求父亲节点和子节点不能同时选择题解：经典树形dpdp[x][0]表示以x为根的子树，且x不参加舞会的最大快乐值dp[x][1]表示以x为根的子树，且x参加了舞会的最大快乐值则dp[x][0] = ∑{ m...

** 树形dp

2021-02-22

0 588

P5049 [NOIP2018 提高组] 旅行

P5049 [NOIP2018 提高组] 旅行题意：一棵树(可能是基环树)，从1出发，每到达一个新的点就记录下编号。求一种走法使得记录下来的编号字典序最小。 1≤n≤500000 m=n−1 或 m=n 题解：如果不是基环树，那直接每次走字典序小的点即可对于基环树：第一个方法：暴力删边将基环...

基环树 ***

2021-02-22

0 518

基环树

@[toc]参考博客概念基环树 = n个点n条边的图 = 1棵树 + 1个环无向树(N点N边无向图) 外向树(每个点入度=1) 内向树(每个点出度=1) 以上三种树有十分优秀的性质，就是可以直接将环作为根。就可以对每个环的子树进行单独处理，最后再处理环找环拓扑排序处理无向图可以找出环...

基环树

2021-02-22

1 786

P3992 [BJOI2017]开车

P3992 [BJOI2017]开车题意：题解：我们要先将问题转换圈是车，x是加油站。红色部分为车移动的路线数组a是车数量的前缀和数组b是加油站的前缀和而a[i]与b[i]的差的绝对值就是对应的红色路被走的次数现在车发生位置移动，b数组没有影响，a数组i到j这段整体减一现在我们要做的就是维护...

*** 分块

2021-02-22

0 561

P4135 作诗

P4135 作诗题意：给定 n 个不大于 c 的正整数 a1...an 和 m 组询问，每次问 [l,r] 中有多少个数出现正偶数次。对于每次询问：设上一个询问的答案为 ans（第一个询问时 ans=0），令L=(l+ans)mod n+1，R=(r+ans)mod n+1，若L>R，交换...

** 分块

2021-02-22

0 586

CF1183H Subsequences (hard version) 来自专栏

题意：长度为n的字符串S，现在要找出k个不同的子序列，使得这些序列的总价值最低一个序列的价值等于删去的字符长度（空串也算子序列）1≤n≤100,1≤k≤10^12^ 题解：一看就是dp，我们先想想串a可以有多少不同的子序列dp[i][j]表示前i个字符构造出来的长度为j的子序列数量转移方程不难得...

*** dp

2021-02-20

0 723

CF1043E Train Hard, Win Easy 来自专栏

CF1043E Train Hard, Win Easy 题意： n个人有Ai和Bi两个属性，给出m个关系：xi yi表示xi和yi不能配对i,j两人规定匹配的价值为min (Ai + Bj , Bi + Aj )回答出每个人跟所有人配对（除开不能和自己匹配的人）的价值总和题解：两两匹配取mi...

** 思维

2021-02-20

0 776