• 等级
  • 5391 访问
  • 55 原创
  • 0 转发
  • 114089 排名
  • 5 评论
  • 4 获赞

博客搬迁啦

博主的博客已搬迁至https://lnrbhaw.github.io

2018-11-25 09:59:11

NOIP2018游记

NOIP2018游记前言今天说要写游记,机房的大佬们问我为什么现在才写,估计是因为以前也没写过不知道怎么写,而且今天正式才成绩出来,算是尘埃落定了吧。day-1以前所有的openday都不幸的被关在家里,这次这么好的机会当然要好好利用啦,结果不知是喝了咖啡还是自己过于兴奋,实在是睡不着,凌晨四点才好不容易落入了梦乡,没想到六点钟准时被生物钟叫起,只睡了两个小时,好困啊。。。。day0...

2018-11-21 22:15:43

bzoj 3696 化合物 树形dp (附复杂度证明!!!)

题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=2318题目大意介于这是一道权限题,先讲一下题意有一棵根节点编号为1的数,给出每一个节点的父亲。对于点对(x,y),令他们的LCA为k,定义这对点对的A值为dis[x][k])^dis[y][k],dis即为两点间的最短距离(边数),最后求出对于x=(1…n),A值为x的点对的数量...

2018-11-04 21:23:10

威尔逊定理

前言好久没更博客了,今天讲一个比较冷门的定理,但在某些题中还是有一定用处的,叫威尔逊定理。主要是比较简单,笔者的垃圾水平能讲的清楚威尔逊定理(p−1)!≡−1(p-1)!\equiv-1(p−1)!≡−1(modp)当p是质数时。下面讲一下证明。以下的-1都是在模p意义下的,实际上就是p-1。我们知道1∗1≡11*1\equiv11∗1≡1(modp),(−1)∗(−1)≡1(...

2018-10-15 09:57:00

Miller_Rabin&Pollared_Rho

Miller_Rabin质数判断我们朴素的质数判断算法是枚举小于等于n−−√n\sqrt{n}的数,判断是否都不能整除n,这样的复杂度是n−−√n\sqrt{n},那么当n的数量级达到1018101810^{18}的时候就不够优越了。这时候我们的Miller_Rubin算法就闪亮登场了。我们的故事从费马小定理讲起,ap−1ap−1a^{p-1}≡1(modp),当p为质数的时候。在费...

2018-09-09 11:00:35

莫比乌斯反演学习笔记

前言停更好久了,刚好我们老师讲了莫比乌斯反演,那我就来开数论这个天坑吧。莫比乌斯反演比如说我们现在有一个函数f(n)=∑d|ng(d)f(n)=∑d|ng(d)f(n)=\sum_{d|n}g(d)假设f非常容易求得,但是g很难求,那么我们是不是可以通过f来求g呢g(n)=∑d|nf(nd)∗μ(d)g(n)=∑d|nf(nd)∗μ(d)g(n)=\sum_{d|n}f(\...

2018-08-29 21:37:33

bzoj3261 最大异或和 可持久化trie

链接https://www.lydsy.com/JudgeOnline/problem.php?id=3261做法我们先考虑没有修改操作,只有询问的话怎么做,我们记sum[i]表示i的后缀异或和,那么我们每个询问相当于查询区间对一个数x异或后的最大值,那么贪心很明显,位数从高到低,如果有数这个位置上可以和x异或起来是1,那么我肯定不会去选和x异或起来这位上是0的。根据这个性质,我们考虑...

2018-07-22 12:41:53

浅谈矩阵乘法的应用

前言矩阵乘法,常常被用作递推式的优化,如果把一个递推式一步的递推转换成乘上一个矩阵,那么由于矩阵乘法有结合律,所以我们就可以快速幂啦,起到优化的效果。而递推式出现最多的地方当然就是dp了,所以今天想简单的总结一下矩阵乘法优化dp。正文博主做的题比较少,见到的这类题也比较少,但有一道题感觉还是比较经典的。给出一张有向图,问从1号点出发,走过路径长度为T,到达n号点的方案数,其中T...

2018-07-19 12:42:50

三角函数

特殊角的三角函数sin(16π)=12sin(16π)=12sin(\frac{1}{6}\pi)=\frac{1}{2}sin(13π)=3√2sin(13π)=32sin(\frac{1}{3}\pi)=\frac{\sqrt{3}}{2}cos(16π)=3√2cos(16π)=32cos(\frac{1}{6}\pi)=\frac{\sqrt{3}}{2}cos(13π)=...

2018-07-15 15:21:56

只是想谈谈学习kmp中的一点体会

我觉得写出一篇能够看一遍就能理解KMP的博客是很难的,理解这个算法是需要时间和能力的,所以我就不不自量力的去尝试了,所以我就谈一谈我认为kmp学习中比较难理解的点和比较重要的点。建议学习过kmp但还是有疑惑的同学看。我们看next数组上一张图片吧,我现在箭头指向的是我现在要求第i为的next值,而0..i-1的next值都求过了。先看next[i-1]假设两段红色的相等,然...

2018-07-11 13:44:11

bzoj 1483 [HNOI2009]梦幻布丁 线段树合并

题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=1483做法网上好多的做法都是链表合并,我感觉有点难写,这里提供一种不一样的思路,线段树合并,复杂度是一样的,都是一个log,但是代码复杂度应该会比较简单。我们对每个颜色建一棵线段树,线段树每个节点记录三个信息,size,ll,rr,分别表示这个颜色这段区间中的段数,左边是...

2018-06-25 14:10:35

bzoj 1212 [HNOI2004]L语言 AC自动机

题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=1212做法首先看到多个单词匹配就直接想到AC自动机了啊,然后把AC自动机建出来,做匹配的时候有点不同,以f[i]表示以i结尾的前缀能否匹配,然后我是在每个单词的结尾挂了个vector,表示这个节点结尾的单词长度,用fin[i][j]表示。那么我们每走到一个节点,把fail...

2018-06-23 18:17:26

bzoj 3252 攻略 长链剖分

题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=3252做法贪心应该还是比较好像的,每一次走最长的链,然后这条链上点的权值就都为0了,那么我们发现题意转化成为一棵数分成若干条链,然后去前k大的链求加和。那么这个链是怎么划分的呢,根据这个贪心可以发现,长链剖分一下就好了。因为长链剖分会找到到叶子的最长的链,然后长链剖分...

2018-06-22 10:37:28

bzoj 2561 最小生成树 网络流

题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=2561做法做这道题的时候,我想起了以前同学给我讲最小生成树的一个性质,基于kruskal的做法。当你要加入一条边时,边权小于它的边一定都over了,而且哪些点构成一个联通块是确定了的,注意是小于,不是小于等于。那么有了这个性质之后,这道题就非常easy了,考虑这条边能...

2018-06-03 21:17:17

bzoj 1901: Zju2112 Dynamic Rankings 树状数组套权值线段树

题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=1901前言首先不得不说某些博客名称写的是树状数组套主席树的人,实际上写的是树状数组套权值线段树,这种把权值线段树和主席树划等号的人,简直是误人子弟。主席树实际上是可持久化的权值线段树,他的核心思想是现在这个时刻的权值线段树要继承上个时刻的权值线段树,而这道题目中没有用到这种方法,...

2018-05-26 15:16:26

BSGS算法

前言这个算法的全名是baby-step-giant-step,用来求解一个数的离散对数,说白了就是求Ax=BAx=BA^{x}=B(modmodmodppp),方程中x解的个数。算法根据费马小定理,我们知道这个x的范围是在1..p-1中的,所以我们暴力枚举的复杂度是O(p)的。这不够优,令q=sqrt(p)q=sqrt(p)q=sqrt(p),那么x可以表示为x=q∗k...

2018-05-23 15:41:46

CF 895C-Square Subsets

题意简述给你一个有n个元素的可重集(n<=1e5,元素大小<=70),从这个集合中选出若干元素使得这些元素的积为完全平方数,求方案数mod1e9+7做法注意到元素非常的小,70以内的质数只有19个,那么我们想到状压dp,f[i][j]表示到第i个数,前面有质因子的集合是j的方案数,转移是O(2182182^{18}),状态是219∗n219∗n2^{19}*n的,会挂掉。...

2018-05-15 18:49:01

CF 876E-National Property

题意简述给你n个数字串,刚开始每个数字的优先级为2,你要把某些数字的优先级设为1,然后使得得这些串不降,就是后面一个串要大于等于前面一个串,这个判断大小就是按位比较,先比较优先级,然后比较大小。做法为了方便叙述,我们把优先级为1的叫做大写,优先级为2的叫做小写。我们把每个串i和他前面一个串i-1比较,找到第一个不相同的位置j,分类讨论一波1.如果a[i][j]>a[i...

2018-05-14 15:51:44

CF 939E-Maximize! (三分法)

题目链接http://codeforces.com/problemset/problem/939/E题意简述现在有一个数列,一开始为空,有两种操作。1.加入一个数,保证这个数比之前的数都要大2.在这个数列中选择一个子集S,是的S中的最大元素减掉S的平均值最大,输出这个最大值做法首先,每次加入一个数,有两种可能,一种是最大值不变,第二种是以当前加入的这个数为最大值...

2018-05-14 09:54:21

CF 980E-The Number Games

题目链接http://codeforces.com/problemset/problem/980/E题意简述给你n个点,n<=100w,每个点有点权,点权为2i2i2^i,再给你一个整数k,k<=100w,表示你要删除k个点后使得这棵树仍联通且剩余点的权值和最大,输出所有删除的点。乍一看以为树形dp,突然发现k也小于等于100w,好像不行啊。我们把题意转换为选择...

2018-05-09 14:12:00

Michael-Li

关注
  • 其他/学生
  • 中国 浙江省 杭州市
奖章
  • 专栏达人
  • 持之以恒
  • 1024勋章