Linyk
Linyk
全部文章
分类
未归档(12)
归档
标签
去牛客网
登录
/
注册
Linyk的博客
Dream it possible
全部文章
(共12篇)
【学习笔记】树上启发式合并 概念+基础运用
引入 现在考虑这样一类树上统计问题: 无修改操作,询问允许离线 对子树信息进行统计(链上的信息在某些条件下也可以统计 用什么来做呢?暴力?树上差分?树上莫队? 今天要介绍的这种算法 将吊打以上 有请它闪亮登场——dsu on tree!!! 看到这个名字,嗯?dsu...
树上启发式合并
2020-12-21
0
252
[HAOI2006]数字序列 题解
Solution 题目链接 题目描述 现在我们有一个长度为 n的整数序列 a。但是它太不好看了,于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数,也不希望改变的幅度太大。 输入格式 第一行是一个整数,表示序列长度 n。 第二行有 n个整数,第 i个整数表示...
dp
2020-12-14
0
350
[SHOI2015]自动刷题机 题解
Solution 题目链接 自动刷题机TT(蒟蒻也好想拥有),可惜目前不存在,留着给以后的oier发明吧; 这是本蒟蒻第一次做SHOI,发现是道好水的蓝题 题目大意就是让你求一个最小值n和一个最大值n满足题意能恰好A掉k题; 我们会发现 当n越大的时候 A掉的题目会越少(这很显然吧,想想看...
二分
2020-12-14
0
384
近期计划学习内容
近期计划学习内容 注意计划二字(不过我会加油的!) 图论: 学习内容 完成情况 掌握程度 树链剖分 √ ★★ dsu on tree √ ★★ ...
2020-12-12
0
276
浅谈多种方法求LCA(最近公共祖先)
LCA 首先来看下例题 洛谷 P3379 点这里看题目 相信求LCA是每位Oier学习算法的必经之路 那么啥是LCA呢? 引用OI wiki的定义—— 那么步入正题 如何求LCA呢? 第一种方法·朴素求法 我们选择深度最深的点往上跳 最后两点一定会相遇 相遇的...
树链剖分
RMQ
LCA
倍增
2020-12-11
0
367
洛谷P1021 邮票面值设计 题解
首先,看到这题,大家肯定首先想到暴力+dfs吧! 可是这题暴力会超时; 好吧我们还是来认真思考下正解 思路应该是枚举出所有种类的邮票,最后判断一下,并记录最大值 暴搜,不行的话,可以剪枝? 1.使a数组保持单调递增,dfs中每次从a[k-1]+1开始搜索,以此来消除重复的搜索;(常规思路)...
dp
dfs
2020-11-05
0
282
NOIP2013 火柴排队 题解
题解 首先的话,上个题目链接 https://www.luogu.com.cn/problem/P1966 读懂了题目大意,稍微有点头绪 我们发现要求这个和的最小值 即min{∑(ai-bi)^2 (1<=i<=n)} 展开,得min{∑(ai^...
排序
2020-11-04
0
246
蒟蒻的CSP-J/S 2020游记
初赛 Day 0 学校还在上whk啊啊啊要疯,反正明天要请假今天作业干脆别写了。 回到家里花了一个晚上水题,初赛的题就稍微看了几眼 Day 1 这次是第一次参加提高(才学了一年OI的蒟蒻) 上午: 感觉难度还行,和去年差不多(?) 可是有些细节没注意啊啊啊,到了收考卷时候才...
2020-10-12
0
358
数据结构篇_线段树(引入+概念)
线段树 首先,如果你在这之前不知道线段树的话,那么希望我的文章对你有帮助; 如果您已经会了,那么请移步,这里只介绍线段树最基本的概念; 引入 ~先来看引入: 给定一个整数序列,每次操作会修改序列上某个位置的数,或者是询问序列中某个区间内的所有数和。 如果我们采取暴力的话...
数据结构
线段树
2020-08-28
0
449
洛谷P6745 『MdOI R3』Number 题解
Solution 这个题没啥好说的,一道裸的高精加 如果说你不会高精的话,其实会点数学稍微思考下也会做了, 想学高精可以去做一做洛谷1601; 好吧,这么水的题,代码: #include<bits/stdc++.h> using namespace std; string...
2020-08-26
0
298
首页
上一页
1
2
下一页
末页