problem 有n头牛在吃花，第i头牛每分钟吃的花，John每次可以运走一头牛，运走第i头牛需要的时间是。设计一种运牛的顺序，使得被吃掉的花最少。 solution 非常经典贪心题。 先考虑只有两头牛的情况。如果先运走，那么被吃掉的花就是，同理如果先运走被吃掉的花就是。所以我们按照排序，然后统计答案就行了。 code /* * @Author: wxyww * @Date: 2020-05-27 22:08:27 * @Last Modified time: 2020-05-27 22:09:59 */ #include<cstdio> #include<iostrea...

solution 想起当年noip赛场上没做出来这道降智题就来气。。。 这个题目其实讲的也就是去掉最多的元素，使得剩下的元素可以组成原来可以组成全部数字。 仔细想一下，其实就是将原数组排序之后，如果比较大的那个可以被比较小的表示出来，那么这个元素我们就可以删去了。所以我们用表示前i个元素是不是可以组成，然后做完全背包。在背包的过程中如果一个元素不能被组成就将答案加1。 code /* * @Author: wxyww * @Date: 2020-05-26 14:11:31 * @Last Modified time: 2020-05-26 14:29:43 */ #include<...

solution 显然的，越小的就应该越优先考虑。所以我们先按照从小到大排序。 然后我们用记录下现在已经选择的建筑所需要花费的时间。如果加上当前建筑的不大于当前建筑的。那么就直接将这个建筑修复即可。 那么如果应该怎么办呢？有两种选择，一种是从前面选的里面踢掉一个(只会踢掉一个，因为每个建筑的贡献都是1)，换成当前的。另一种是不选当前的这个。第二种选择的话就直接跳过处理下一个就行了。对于第一个选择我们就要考虑应该踢掉哪一个，因为每个建筑的贡献都是1，所以显然我们踢掉花费时间最大的那个更优秀。所以就用一个堆来维护出当前选择的建筑中花费时间最大的那个，如果踢掉最大的那个之后可以加入当前的这个新的并且...

A 怪盗-1412 problem 用个，个，个进行排列，求最多有多少个子序列。 solution 显然让所有的4和2分别相邻答案会更大。然后就是将1分成两份，分别放在4两边。如果前面的有个，那么答案就是，这是一个二次函数，当时取得最大值。 code /* * @Author: wxyww * @Date: 2020-05-22 18:59:57 * @Last Modified time: 2020-05-22 19:03:29 */ #include<cstdio> #include<iostream> #include<cstdlib> #incl...

[toc] 线性方程组 概述 线性方程组就是形如下方的方程组。 初等行变换与高斯消元 线性方程组有3种初等行变换（将某行乘以某个数，将两行相减，交换两行） 通过三种初等行变换，我们可以进行高斯消元。 高斯消元其实就是平时解方程组的过程。 大体过程就是通过第i行消去每行(除第i行)的第i个未知数的系数。 齐次方程组 齐次方程组是指等号右侧均为0的线性方程组。 当方程组个数小于未知数个数时一定有解。 这个可以直观的理解为每个方程组相当于对未知数的限制，方程组个数越少对于未知数的限制就越小就更可能有解。 有限维向量空间 n维向量 高中学到的二维向量是由一个二元坐标来描述，空间向量由一个三元坐标来...

树的同构 两棵树如果形态相同，就称这两棵树同构。也就是：存在一个排列，将其中一棵树的编号改为，使得这棵树和另外一棵树完全相同。 树hash 判断两棵树是否同构可以使用树hash的方法。用表示i这棵子树的hash值。那么有，表示第个素数。表示以为根的子树的大小。dfs一遍即可求出。 任意点为根的hash值 设表示以为根时整棵树的hash值。然后就有自上而下转移即可。 以重心为根的hash值 因为一棵树的重心只有一个或者两个。所以可以找到两棵树的中心。以重心为根求树的hash值。如果存在两个重心。可以新建一个根节点，分别向两个重心连边。并且断掉两个重心之间的边。 例题 luogu5043 判断无根...

SG函数 作用 对于一个状态i为先手必胜态当且仅当SG(i)!=0。 转移 那怎么得到SG函数尼。 SG(i)=mex(SG(j))（状态i可以通过一步转移到j） 首先说一下mex。一个集合的mex是最小的没有出现在这个集合里的非负整数。 其实想一下这个也是挺明显的。状态i是先手必败态当前仅当i转移到的状态都是先手必胜态。同样，只要当前状态可以转移到一个先手必败态，那么当前就是先手必胜态。 小定理 对于两个独立的游戏A，B，他们的SG函数=SG(A) ^ SG(B) 这个比较难描述，看一下后面的题就明白了。 真模板题 先来娱乐一下 题面 给一个有向无环图，一开始在某个节点有个棋子，Alice和...

杜教筛用来求数论函数前缀和。复杂度为 前提 如果我们要求，那么需要找到一个数论函数，满足的前缀和可以非常快速的求出来，并且的前缀和可以非常快速的求出来。 推导 既然的前缀和可以非常快速的求出来，我们就求的前缀和。 即。 然后我们想得到的是。所以我们让上面的式子减去一个。 对于后面这个式子,我们用来代替，就变成了 因为的前缀和可以快速求出，所以直接数论分块，后面的直接递归就好了。 这样我们得到的是，所以答案除以（一般为1）就好了。 例子 以求的前缀和为例。因为，和的前缀和都非常好求，所以我们令为即可。 再来推一下的前缀和。因为，和的前缀和都非常好求，所以还是令 关于预处理 这样直接搜的复杂度是，...

概述 是用来处理集合卷积的问题。也就是求解类型的问题。其中或运算可以改为。 寻找点值 因为总是看不下去那么长的推导，所以每次都是看到一半。然后就在加上自己的一点理解，简单推导一下吧（背过结论就行） 以或运算为例。为什么说是集合卷积呢。因为或运算等价于求集合并。也就是求 。 那么我们类似于，先将他转化为点值，然后进行乘法运算后，在转换回来。 如何转化为点值呢。或者说他的点值长什么样子呢。 我们求一个。然后我们求一下的乘积。 我们令表示转化后的结果，表示转化或的结果，表示卷积转化后的结果。 也就是 所以就是我们要的点值表达式！ 相互转化 有了点值之后我们还需要在点值与多项式之间相互转化，那么应该怎...

这篇文章主要是整理一些定理，方便后面复习。没有证明(学OI要什么证明)。 数论相关 常见的积性函数 单位函数 欧拉函数 表示小于等于n的数字中与n互质的数字个数。 莫比乌斯函数 正因子数 因子函数 易知一般记作 常值函数 幂函数 特别的，常记作 狄利克雷卷积 对于两个数论函数， 其中*为狄利克雷卷积的运算符号。如果f和g为积性函数，那么也为积性函数。 性质 1.对于任意的数论函数f有$$ 2.$$ 3.$$ 4.$$ 莫比乌斯反演 如果 那么有 莫比乌斯反演常用卷积： 约数个数定理 证明：其实很显然，只要枚举每种质因子的出现在约数中的个数就能得到所有的约数。对于在里出现了次的质因子，在约数...

solution 先对求一遍前缀异或和。 首先肯定要按二进制位处理，假设处理到了第x位，然后枚举一个位置，我们就想要查询所有满足且为偶数的中满足，其中表示第i个位置的第个二进制位上的值。 所以我们只要根据奇偶性分一下类，然后做前缀和就可以求出所有满足条件的的个数了。 code /* * @Author: wxyww * @Date: 2020-05-22 14:14:55 * @Last Modified time: 2020-05-22 15:11:52 */ #include<cstdio> #include<iostream> #include<cstd...

solution 处理出一个数组t，如果那么，否则。 然后我们只要找到一个包含b所在位置的区间满足就可说明这个区间内的中位数为。 所以对求一遍前缀和，记录下所在位置左边的所有前缀和值的数量。然后枚举所在位置的右边，统计答案即可。 code /* * @Author: wxyww * @Date: 2020-05-21 19:50:52 * @Last Modified time: 2020-05-21 19:56:26 */ #include<cstdio> #include<iostream> #include<cstdlib> #include&lt...

solution 我们从1号点开始染色，标记为0的点表示可以从1号点走偶数步到达，标记为1的点表示可以从1号点走奇数步到达。最后就是想要所有点都可以标记为0。如果存在一个奇环，那么这个环上的点既可以标记为1，也可以标记为0，所以所有与这个奇环相连的点都可以标记为0和1。 所以我们只要保证最终连接成一个包含奇环的连通块就可以了，如果存在至少一个连通块里本来就有一个奇环，那么只要让其他连通块向其连边即可，答案就是(S表示连通块个数)。如果不存在一个连通块里有奇环，那么就要自己连出一个奇环，显然连出一个奇环只需要添加1条边，所以答案就是。 判断一个连通块内是不是存在奇环可以用二分图染色。如果无法进行...

solution 用表示前k个区间能(1)不能(0)组成这个数字。然后枚举一下第个区间所选的数字x，就有转移 最后数一下有多少数字可以被组成就行了。 但是这样复杂度爆炸，发现f的值只有和所以可以用进行优化，复杂度 code /* * @Author: wxyww * @Date: 2020-05-19 14:37:41 * @Last Modified time: 2020-05-19 14:46:32 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring...