Kur1su

分类

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

/ 注册

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

Kurisu与牛客的每日一题

105篇文章 1475人学习

9篇文章 1648人学习

2篇文章 6632人学习

课余学习(*^▽^*)

5篇文章 920人学习

一些比赛的题解

25篇文章 8297人学习

全部文章（共214篇）

【每日一题】Treepath 题解来自专栏

Solution 一开始感觉是个树形dp 因为偶数总能从奇数转换过来但是这个思路我连样例都过不了(真菜我们考虑下从深度角度出发, 以 1 为根求出全部深度那么偶数层到偶数层距离为偶数奇数到奇数层距离距离也为偶数那么我们求出奇数层节点为l, 偶数层节点个数为rans = (l - 1) * l ...

2020-04-14

4 902

【每日一题】Xorto题解来自专栏

Solution 这是一道数组上的异或问题, 这类问题一般要使用前缀异或和作为辅助, 即sum[i] = a[1] ^ a[2] ..... ^ a[i];它具有这样的性质sum[i] ^ sum[j - 1] = a[j] ^ a[j + 1] .... ^ a[i]; (i >= j)其次...

2020-04-14

4 1094

【每日一题】树学和 Accumulation Degree题解来自专栏

树学 Solution 题目求最小的, 考虑找树的重心, 其所有的子树中最大的子树节点数最少。能保证每一个子树中的点深度和是最小的, 然后从重心开始给每个点赋深度, 求一下和即可。那么问题就转化为如何求重心, 这是树形dp的一个经典应用, 用cnt[i] 表示 i 点的子树的节点有 dp[u] = ...

2020-04-13

2 779

算法课读书笔记之字符串算法学习体会及其应用-后缀自动机来自专栏

后缀自动机——一种解决字符串问题的强力数据结构[^5] 后缀自动机的引入后缀自动机(Suffix automaton, SAM)是IOI国家队成员陈立杰在2012年的冬令营从国外引进的一种数据结构, 它能在线性时间内解决许多字符串问题。字符串的 SAM 可以理解为给定字符串的所有子串的压缩形式...

2020-04-13

2 1156

牛客练习赛61 题解

A. 打怪 Solution 签到题,我是直接模拟,一开始我的做法是令cnt > 1e4 的输出直接输出 -1, 没想到超时了,出题人没给 t 的大小,上当了..于是考虑下 -1 的情况,显然当我们的攻击大于等于小怪的血量时,我们每次都能先手的情况下,可以秒杀小怪不会掉血所以, 当 h <...

2020-04-11

3 860

算法课读书笔记之字符串算法学习体会及其应用-后缀数组来自专栏

后缀数组 [^3] 一点题外话好久之前就想学习后缀数组相关算法,但是苦于自己的基础知识不够扎实,而且这个算法对初学者来说难度过高。要大致理解其中的思想其实不难,但是要进行代码实现需要花很大的功夫去理解,静下心来参透每一步的细节。借着这次读书笔记作业的任务，我花了一天的时间对资料进行整理,对代码进...

2020-04-10

0 874

算法课读书笔记之字符串算法学习体会及其应用-AC自动机来自专栏

另一个问题的提出我们注意到KMP算法所能优化的是一种单模式串的匹配,那么考虑多模式串的匹配下,KMP算法的复杂度是多少呢？显然，对于每个模式串,我们都要进行一次KMP算法,当有k个模式串时,它们的长度分别是m1,m2....mk,那么我们需要做k次KMP算法,时间复杂度是此时复杂度不再优秀。基...

2020-04-09

1 774

【每日一题】黑白树题解来自专栏

Solution 太菜了,看了雨巨的题解才发自己读错题了自闭了一天题目提到如果我们选择i点i点到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑那么我们就可以考虑从叶子开始取,因为取非叶子节点永远无法将叶子节点染黑这样显然就可以用dfs递归从叶子往根染黑其次,我们发现从叶子节点往...

2020-04-08

3 780

【每日一题】Running Median 题解来自专栏

Solution 分析题意,要求我们求出每一个奇数长度前缀的中位数对于每一个奇数长度前缀,设长度为len,求中位值其实就是求区间第(len + 1) / 2大那么显然这就是一道求区间第k大的模板题了我们直接上主席树,秒掉这个问题这里简单介绍下主席树主席树又叫可持久化线段树，它是基于线段树发展而来的一...

2020-04-08

2 922

牛客算法周周练1 题解

A. Maximize The Beautiful Value Solution 看了半天才看懂,forward向前是从右往左挪动,我们知道一个数字往前挪动k个位后,位置为i - k。注意到i - k 到 i - 1 这个范围的数字他们都会相应往后挪,即我们的答案会加上sum[i - 1] - su...

2020-04-07

7 947