codesonic

分类

题解(7)

/ 注册

全部文章（共7篇）

题解 | 信息学奥赛一本通-最敏捷的机器人

既然要最快，本文只介绍线性做法最简单的做法当然是滑动窗口，单调队列维护单调队列中的元素单调上升/下降，主要的思想就是如果位置i比位置j靠后，且比j大/小，那j就是没用的，可以弹出 #include<iostream> #include<cstdio> const i...

2019-09-19

0 697

题解 | 算法竞赛进阶指南-Balanced Lineup

给定一个序列，每次询问一个区间的极差。其实就是RMQ最大值和最小值一减即可维护最值显然有ST表(O(nlogn)-O(1))，线段树(O(n)-O(logn))，笛卡尔树(O(n)-O(1))等等多种方法。我们维护一个线段树，每个节点维护对应区间的最大值和最小值，询问循规蹈矩询问即可。 #in...

2019-09-03

0 691

题解 | 算法竞赛进阶指南 - 选课

考虑树形DP，这题其实是把背包搬到了树上，使得选一个物体需要经过他的前置物体才能选那么我们只要在原有的树形DP上加一个背包即可那么有方程，其中to是所有的儿子，第二维存的就是一维背包的东西详细见代码... #include<bits/stdc++.h> using namespa...

2019-09-02

0 716

题解 | 算法竞赛进阶指南-普通平衡树

WBLT 全称Weight Balanced Leafy Tree.是一种常数较小，代码较简单的平衡树实现方式。在看本文之前，推荐您先学习treap等平衡树这篇文章对于有平衡树基础的人较为友好定义和引入 WBLT是二叉搜索树的一种。不同的是，他同时是一个大根堆（也可以是小根堆），每个非叶节点都...

2019-09-02

0 1166

题解 | 信息学奥赛一本通 - 数列区间最大值

本题是经典的静态序列区间最大值问题 (RMQ)，可以用ST表等数据结构解决其中ST表较为优秀，它只需要Onlogn的预处理时间，查询为O1 我们令st[i][j]表示序列的第i个元素到中的最大值，然后从1到logn遍历j，预处理所有的st 其中，这是一个倍增的过程那么接下来对于每个询问区间，都可...

2019-09-02

0 730

题解 | 信息学奥赛一本通 - 小Z的袜子

简要题意给定一个长度为n的序列，每次询问一个区间[l,r]中，随机抽取两个数字，这两个数字相同的概率既然是静态的，不妨考虑莫队。我们发现这题的性质满足莫队所需的性质，我们只需要考虑状态的转移，即插入一个点和删除一个点即可考虑一个颜色对答案的贡献，设s[i]表示区间内第i种颜色的数量，很容易推出...

2019-09-02

0 615

题解 | 信息学奥赛一本通 - 玩具装箱

斜率优化DP 前置姿势 1. 单调队列，DP，以及单调队列优化DP 单调队列用来维护一个滑动区间的最大值，因为最多滑动不超过2n次，复杂度O(n). P1886 滑动窗口是单调队列的模板题。在线性DP很常用 P3957 跳房子就是一道经典的单调队列优化动归... （当时在考场上遇到这道题毫无头绪...

2019-08-19

1 706