RainAir

分类

学习笔记(12) 题解(9)

/ 注册

全部文章（共21篇）

【题解】牛客练习赛 68 题解

A 注意条件且互不相同，所以一个区间内最小未出现的自然数就等于不在这个区间内最小出现的自然数。预处理前缀后缀最小值就好了。代码链接 B 发现当时答案必为。于是我们只需要预处理的答案就好了。可以推式子或者前缀和处理。代码链接 C 我们考虑单组询问怎么做：实际上就是把所有的所...

2020-08-28

11 829

【每日一题】3月31日

我们考虑一个暴力的做法：每次从这个点找到它上面的第一个比他大的点跳过去。但是这样显然是过不了的。我们先丢掉询问给出的那个权每次就拿这个点上的权来跳答案如何快速处理。我们可以倍增：往上找了个答案之后的点在哪里。问题转化为处理这个也可以利用我们前面已经求出的f来计算：观察到随着 ...

2020-04-02

0 830

【每日一题】3月30

单调队列经典模板题。详细可以看代码。 #include<bits/stdc++.h> #define fi first #define se second #define U unsigned #define P std::pair<int,int> #define LL ...

模板 trivial

2020-04-02

0 757

【每日一题】4月1日

树形dp 直接表示为根的子树处理完的代价转移的时候枚举是断掉当前的边还是断子树的边即可。 #include <algorithm> #include <iostream> #include <cstring> #include <climits>...

trivial

2020-04-02

0 836

【每日一题】4月2日

序列自动机模板题。建出后直接看能不能被自动机接受就可以了。 #include<bits/stdc++.h> #define fi first #define se second #define U unsigned #define P std::pair<int,int> ...

trivial

2020-04-02

0 847

【每日一题】4月3日

注意到每对点一定是在某一个点（它们的lca）处合并。于是可以dp。设表示已经处理完了的子树当前是否剩余一个还没有配对的点（实际上等价于的奇偶性）。转移合并两个子树的时候考虑一下要不要两边的点配个对就好了。 #include<bits/stdc++.h> #define f...

trivial

2020-04-02

0 765

FFT 学习笔记

快速傅里叶变换 (Fast Fourier Transform, FFT) 是一种的时间复杂度内完成离散傅里叶变换 (DFT) 的算法，OI 中通常用来优化多项式乘法。常见题目类型链接：给定一个次多项式和一个次多项式。求出它们的卷积。 FFT 就可以在的时间复杂度内解决该类...

FFT

2020-02-28

2 1059

多项式相关简单入门

多项式算法学习笔记定义形如的式子被称为多项式。定义多项式中每个单项式叫做这个多项式的项，定义多项式的次数为项的最高次数。显然个点可以唯一确定一个次数为的多项式。接下来我们首先来看一下多项式的基本运算怎么实现（要不然谁用啊）多项式加减直接对齐相同次数然后系数直接加减就可以了吧。。。...

多项式

2020-02-28

1 791

KDTree 学习笔记

K-D Tree，全名k-dimensional Tree，是一种分割k维数据空间的数据结构。主要应用于***空间关键数据的搜索（如：范围搜索和最近邻搜索）。K-D Tree是二进制空间分割树的特殊的情况，以下是一棵二维空间上的 k-d tree：建树 K-D Tree 的建树过程类似于平衡树：对...

KD-Tree

2020-02-28

0 1104

斐波那契数列初探

定义一些小性质一些 simple 的运算运算 1 证明：拆开算就可以了运算2 证明：数学归纳法一下就可以了。咕咕咕~ 运算3 我们如果把斐波那契数列扩展到负数，那么有公式运算4 证明：首先验证小范围的 k 发现是正确的。那么我们设是正确的，现在尝试证明是正确的。一些正常...

斐波那契数列

2020-02-28

0 796