A 注意条件 且 互不相同，所以一个区间内最小未出现的自然数就等于不在这个区间内最小出现的自然数。预处理前缀后缀最小值就好了。 代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44866335 B 发现当 时答案必为 0。 于是我们只需要预处理 n < 199999 的答案就好了。可以推式子或者前缀和处理。 代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44866341 C ...

A 注意条件 且 互不相同，所以一个区间内最小未出现的自然数就等于不在这个区间内最小出现的自然数。预处理前缀后缀最小值就好了。代码链接 B 发现当 时答案必为 。 于是我们只需要预处理 的答案就好了。可以推式子或者前缀和处理。代码链接 C 我们考虑单组询问 怎么做：实际上就是把所有 的所有边都加进去 询问互相可达点对，可以用并查集维护。 那么多组询问就可以都离线下来，把询问和边放在一起排序然后处理就好了。 其实在线也可以做：处理处加入每条边后的答案，询问的时候只需要找到最后一个 的边，拿加入这个边后的答案作为这次询问的答案就行了。代码链接 D 首先我们发现每个位置本质是一样的，...

我们考虑一个暴力的做法：每次从这个点找到它上面的第一个比他大的点 跳过去。但是这样显然是过不了的。我们先丢掉询问给出的那个权 每次就拿这个点上的权来跳 答案如何快速处理。我们可以倍增： 往上找了 个答案之后的点在哪里。问题转化为处理 这个也可以利用我们前面已经求出的f来计算：观察到 随着 的递增而递增。所以我们可以用类似询问倍增的方式来做：每次枚举 比较 和当前点的权 决定跳不跳。 对于询问 题解里有一个很巧妙的做法：将每个点接在起点的下面就可以了（也可以每一次都先倍增找到第一个比它大的） #include<bits/stdc++.h> #define fi fir...

单调队列经典模板题。详细可以看代码。 #include<bits/stdc++.h> #define fi first #define se second #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) fo...

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

序列自动机模板题。建出后直接看能不能被自动机接受就可以了。 #include<bits/stdc++.h> #define fi first #define se second #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FO...

注意到每对点一定是在某一个点（它们的lca）处合并。于是可以dp。设 表示已经处理完了 的子树 当前是否剩余一个还没有配对的点（实际上等价于 的奇偶性）。转移合并两个子树的时候考虑一下要不要两边的点配个对就好了。 #include<bits/stdc++.h> #define fi first #define se second #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #d...

今天又变菜了这周：啥都没干下周目标：尽量别啥都不干

快速傅里叶变换 (Fast Fourier Transform, FFT) 是一种 的时间复杂度内完成离散傅里叶变换 (DFT) 的算法，OI 中通常用来优化多项式乘法。 常见题目类型链接：给定一个 次多项式 和一个 次多项式 。求出它们的卷积。 FFT 就可以在 的时间复杂度内解决该类问题。 先来学习一些 FFT 前备知识。 多项式 系数表示法 设 表示一个 次的多项式，则 利用系数直接运算多项式乘法的时间复杂度是 。（即每个系数都要枚举相乘） 点值表示法 将这个多项式 看成一个函数，就是说代入 个互不相同的 ,会得到 个不同的取值 。 那么这个多项式就被这 个...

多项式算法学习笔记 定义 形如 的式子被称为多项式。定义多项式中每个单项式叫做这个多项式的项，定义多项式的次数为项的最高次数。显然 个点可以唯一确定一个次数为 的多项式。接下来我们首先来看一下多项式的基本运算怎么实现（要不然谁用啊） 多项式加减 直接对齐相同次数然后系数直接加减就可以了吧。。。时间复杂度 ，难度：普及组 T1（虽然这个级别已经不存在了233） 多项式乘法 首先我们考虑一下我们平时如何手算多项式算法。显然我们都是 暴力算的，所以就有了一个枚举所有可能的二元组然后统计答案的暴力做法。当然在常规题目中我们会使用一种叫做 FFT（快速傅里叶变换） 的 的优秀算法来计算，详情...

K-D Tree，全名k-dimensional Tree，是一种分割k维数据空间的数据结构。主要应用于***空间关键数据的搜索（如：范围搜索和最近邻搜索）。K-D Tree是二进制空间分割树的特殊的情况，以下是一棵二维空间上的 k-d tree： 建树 K-D Tree 的建树过程类似于平衡树：对于已知点集，求出其在某一维度上排序后的中间点，作为这个空间的分割点，然后把空间一分为二，再对每个部分递归建树，返回子部分分割点的编号，作为当前部分分割点的左右儿子。关于每次按照哪个维度排序，最好的方案是按照方差大小，但是为了简便我们就遍历每一维来建立。 inline int build(int l,...

定义 一些小性质 一些 simple 的运算 运算 1 证明：拆开算就可以了 运算2 证明：数学归纳法一下就可以了。咕咕咕~ 运算3 我们如果把斐波那契数列扩展到负数，那么有公式 运算4 证明：首先验证小范围的 k 发现是正确的。那么我们设 是正确的，现在尝试证明 是正确的。 一些正常的小性质 性质 1 证明：考虑辗转相减法： 性质 2 我们首先证明从左到右：我们将 表示为 ，现在需要证明 考虑 的情形： 同理：当 的时候，借助上面的结论，显然也有 归纳证明命题正确。现在我们证明从右到左，首先我们来观察一个引理： 引理 1：$$ 证明：我们不妨设 ，则 。 所以有 $$ 即...

网络流题目中，如果一种物品有两种状态（选或不选），告诉你每一种状态产生的收益/代价，我们就可以通过使用最小割模型来解决这个问题。但是如果物品的状态扩展到了 种，我们就需要用一种新的建图方法。我们拿两道题目举例： RatingProgressAward *TCO2017 Semifinal题目链接如果对于积分做了前缀和之后我们发现题目就是要求在满足限制的条件下最大化区间和。对于一个点 如果我们知道了答案区间在哪 我们可以有三种状态：在答案区间左边，在大安区间内，在答案区间右边。这就是三种状态了。我们发现在同一区间内 他们的顺序我们是不需要考虑的（内部顺序可以自己排），我们只需要考虑区间与区间的...

轮廓线 dp 也是一种状压，适用于一维特别大而另一维特别小的情况。我们来从一道经典例题入手：求 的骨牌填满 的矩形的方案数。如果 那么当然可以轻松状压了，但是如果 ，我们就要考虑使用轮廓线 dp 了。设 表示我们填到第 行，我们在状压的状态中记录下图红线上的格子的状态。 （圆圈为现在要填的格子）发现对于一个格子 我们只需要考虑这个格子上是放向上的骨牌，还是向左还是不放。如果上面是空格子那么必须要放向上的格子，否则向左和不放都可以。考虑放了向上的格子后变成了什么： 发现只有填的那个位置变成了 直接简单位运算操作一下就可以了。其他状态可以尝试自己推一下，实在不懂了可以去看代码（ ...