Kur1su

题解

paper(8) 机器学习(2) 生活记录(6) 读书笔记(1)

/ 注册

全部文章 / 题解（共191篇）

【每日一题】Bookshelves 题解(dp, bitmasks) 来自专栏

Description 给出n个数字，要求分成k个连续的子数组，使得每一堆总和按位与的结果是最大的 Solution 思路：dp + 贪心，首先意识到要结果最大需要按位贪心，从高位往低位取。其次，关于某一位是否能够实现，可以用 dp 去解决。具体实现如下：令bool 变量 dp[i][d] 表示到第...

2020-11-23

4 727

【每日一题】dfs序专题 Tree Requests 来自专栏

Description 给一棵树，无修改操作，每次查询给出 (l,r)，查询 l 的子树在深度为 r 的节点对应的字母能不能构成回文串。 Solution 思路：dsu on tree(树上启发式合并)算法的本质其实就是一个优化暴力的过程。按暴力的想法去统计，每次统计所有子树，再删除贡献，时间复杂度...

2020-11-12

5 946

【每日一题】dfs序专题 Colorful Tree 来自专栏

Description 给出一棵树，每个节点都有颜色。对树有两种操作:U x c 更新操作，将x节点的颜色变成cQ c 查询所有颜色为c的节点形成的子图有多少条边 Solution 完全没思路。。。看了其他聚聚的题解通过找规律可以看出加入每条边x的贡献是因此可以用一个set来维护每个颜色的序列，然...

2020-11-11

3 799

【每日一题】dfs序专题 Propagating tree 来自专栏

Description 给定一棵树，根节点为1，给出两种操作：查询x节点当前的val 给出x, val, 修改x节点及其子树的值，注意修改过程是随着深度+-+-进行交替的 Solution 首先处理出dfs序，随后单点查询，区间修改可以用差分树状数组来维护。注意到区间修改的过程是随着深度而改变...

2020-11-10

4 852

【每日一题】dfs序专题选点来自专栏

Description Solution 前置知识：最长上升子序列O(nlogn)的贪心做法, dfs序分析:从题目中可以得出，根 < 右子树 < 左子树，如果要选择最多的点，那么如果能够处理出根 -> 右子树 -> 左子树的dfs序，在序列上取一个最长上升子序列，就能选...

2020-11-09

4 926

【每日一题】dfs序专题求和来自专栏

Description Solution 以前牛客小白赛里也有类似的题目，简单地讲，在树上进行子树区间上的修改和求和问题可以转化为我们熟悉的序列问题。思路：处理出dfs序，然后找到每个节点的子树区间在哪个访问内，剩下的就是树状数组单点修改，区间求和的操作啦。时间复杂度：O(nlogn) Code...

2020-11-09

4 711

【每日一题】dfs序专题 Military Problem 来自专栏

Description 一句话翻译(祈福12月六级考试)给一棵树,m个查询每个查询(u, k) 代表 u 节点dfs序下第k个节点 Solution 令l[i] 表示i节点的起点位置，r[i] 表示i节点的终止位置，a[i] 表示第i个数字是哪个节点。对于每个查询，查找是否在 [l[u], r[u]...

2020-11-07

4 822

【每日一题】金字塔题解(区间dp) 来自专栏

Description 虽然探索金字塔是极其老套的剧情，但是有一队探险家还是到了某金字塔脚下。经过多年的研究，科学家对这座金字塔的内部结构已经有所了解。首先，金字塔由若干房间组成，房间之间连有通道。如果把房间看作节点，通道看作边的话，整个金字塔呈现一个有根树结构，节点的子树之间有序，金字塔有唯一的一...

2020-11-06

6 875

【每日一题】小A与欧拉路题解(树的直径) 来自专栏

Description 小A给你了一棵树，对于这棵树上的每一条边，你都可以将它复制任意（可以为0）次（即在这条边连接的两个点之间再加一条边权相同的边），求所有可能新形成的图中欧拉路的最短长度欧拉路：从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边只通过恰好一次 Solution 考虑欧...

2020-11-04

4 689

【每日一题】奶牛异或题解(01Trie) 来自专栏

Description 农民约翰在喂奶牛的时候被另一个问题卡住了。他的所有N(1 <= N <= 100,000)个奶牛在他面前排成一行(按序号1..N的顺序)，按照它们的社会等级排序。奶牛#1有最高的社会等级，奶牛#N最低。每个奶牛同时被指定了一个不唯一的附加值，这个数在的范围内。...

2020-11-03

2 625