Kur1su

分类

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

/ 注册

TA的专栏 146篇文章 2人订阅

Kurisu与牛客的每日一题

105篇文章 1475人学习

9篇文章 1648人学习

2篇文章 6632人学习

课余学习(*^▽^*)

5篇文章 920人学习

一些比赛的题解

25篇文章 8297人学习

全部文章（共214篇）

【每日一题】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

【每日一题】The XOR Largest Pair 题解(01Trie) 来自专栏

Description Solution 建立01Trie,对于每一个数字都从最高位开始建立字典树，并且贪心地从最高位开始在字典树上走，优先走该位不同的路线，最后取最大的答案。 Code #include <bits/stdc++.h> using namespace std; typ...

2020-10-30

4 799

【每日一题】Quasi Binary 题解来自专栏

Description A number is called quasibinary if its decimal representation contains only digits 0 or 1. For example, numbers 0, 1, 101, 110011 — are qua...

2020-10-15

7 828

【每日一题】筱玛爱线段树题解来自专栏

Description 筱玛是一个热爱线段树的好筱玛。筱玛的爷爷马爷在游戏中被筱玛吊打了，于是他恼羞成怒，决定给筱玛出这样一道数据结构题：给定一个长度为nn的数组AA，刚开始每一项的值均为00。支持以下两种操作，操作共mm次 mm次操作结束后，你要告诉马爷AA数组变成什么样子了。由于答案可能会很大，...

2020-10-15

5 690