1 gigo_64

尚未进行身份认证

请以你的名字呼唤我

等级
TA的排名 10w+

概率与期望复健

当年讲概率和期望的时候我没在啊,,都是自学乱讲的,,不知道今天有多少人被搞晕了qwq概率这个大概都会,期望就是所有概率*贡献的和。反正就是象征性地加起来。主要是做题。然后有个小结论就是一般来说概率正推期望反推。因为你在起点的概率是确定的1,但到终点就不知道了。同样,你从终点到终点期望是已知的0,但从1过去就不知道了。实际上反例也多,比如高斯消元来解什么的,,实际上还是靠做题积累...

2019-10-18 20:14:22

【SCOI2010】传送带【三分法】

传送门咳咳,当年不写博客的后果。三分法用于处理单峰函数的最值问题。对于最大值和最小值的处理是不太一样的,注意一下谁往中间走。这道题固定左端点后,很明显右边是个单峰,所以右边的最短可以视作一个定值,左边移动都对应一个右边的最短值,这个最短值也可以发现是个单峰。所以三分套三分,先固定左边,然后看右边。#include<bits/stdc++.h>usingn...

2019-10-18 18:24:03

多项式求逆

我低头,你踮脚,刚刚好推导过程看楼上的博客就可以了。注意事项在对NTT进行IDFT的时候,本来wn应该要变成自己%len意义下的逆元。但根据zxy说的一位大佬的证明,和zxyoi的感性理解我们发现,只需要把原来的所有含x项翻转就可以了。记得在做limit的时候要做到deg*2,防止溢出。并且开c数组来替代a数组防止出现错误。一个跟博客几乎一样的代码#include<...

2019-08-06 16:07:50

【TJOI2017】DNA【后缀自动机】

传送门稍显窒息的是:这道题只有ATCG四种字符,高中生物知识,,,,,,后缀自动机的优秀之处在于我从跟节点开始走可以走出所有的子串。所以直接dfs记录一下有没有超出3个就好了。#include<bits/stdc++.h>usingnamespacestd;structnode{ intch[6],fail,len,key;}t[200003];int...

2019-10-18 11:25:56

【NOI2011】阿狸的打字机【AC自动机】【离线】【树状数组】

好题啊好题这道题题意很清楚,做起来很毒瘤。首先我们应该可以看出这是一个多模式串多文本串匹配问题,所以我们往自动机上面想。支持加入点,删点,记录打印标记,最后查询答案。删点无非就是几个father,然后回去。打印标记就是记录这次打印在AC自动机的哪个节点发生的。然后给每个自动机节点记录有哪些打印是发生在这个结点的。我开了个vector来记。因为问题很多,一个一个做会出事,所以...

2019-10-18 10:07:38

斜率优化复健

斜率优化。解决一些动态规划的优化问题。可以做到O(n)。当决策点和之前有关,又不知道取哪个的时候,优化方式有很多。单调队列,单调栈,但有时候这些不够用。比如说当方程跟之前的j又和现在的i有关,就会发生变化。因为不同的i会使选择决策不同,所以有时候不能像单调队列一样直接取判断。根据摆渡车,我们发现大概长这样。f(i)=f(j)+i的和j的相乘之类的+i的一坨+j的一坨。我们将已知的j...

2019-10-17 17:15:34

【NOIP2018】保卫王国【矩阵】【倍增】

传送门其实这件事情告诉我们:万物皆可矩阵。同样的,树形dp做一次O(n),一共n次,所以为n^2的复杂度。这样有很多分呢qwq!但是还要更好。一般来说,当我们找到一个复杂度接近正确(个p)的方法时,先考虑怎么优化。我们不应该每次都重新做一遍,而是只管那些被影响了的部分。设被强制的两个点为x,y。我们发现,在树形dp的基础上,它们会影响的答案只包括他们以及他们俩到根节...

2019-10-17 21:19:12

csplus 20191017 【咕】【二维偏序】【最短路构图】

woj4756补票辣鸡前缀和题目。跟去年普及第二题差不多还简单很多。#include<bits/stdc++.h>usingnamespacestd;#defineinread()#defineintlonglongintin{ intcnt=0,f=1;charch=0; while(!isdigit(ch)){ ch=getchar()...

2019-10-17 14:22:03

数位dp复健

对于数位dp,有个挺正常的套路。首先一般拆分数字。将数字的每一位拿出来,作为上界。然后设置状态,一般是填到第几位,然后根据题目设置,比如说windy就要看上一位是谁,不要62就看上一位是不是6之类的。然后注意状态不能跟数字到底是谁有关。就是要确保后面可以乱放的情况下设置状态。拆分完后从高位开始处理。一位一位,用limit来看是否能取到9,反之取到对应数位。然后加起来即可。因为记...

2019-10-16 19:08:28

【NOIP2014】解方程【秦九韶】【高精度处理】

传送门其实秦九韶相信都会,主要是喜欢这道题对于高精度的处理。我们发现这道题的情况比较特殊,a大的很,看起来是要高精度的鸭子。不过我们发现一个事情。我们是在解方程,找到合适的x使多项式为0。那mod一个数好像也没什么问题。所以我们可以对一个数取余,觉得不稳妥多取余几个,都为0的时候就ok了。这启示我们要注意题目本身的性质,尝试转化问题。#include<bits/st...

2019-10-16 15:21:22

【NOIP2012】疫情控制【倍增】【二分答案】【贪心】【思维分析】

传送门倍增只是手段,重点是思维分析的过程。wuvin曾经说过,只要有好的思维,什么神题也打不倒我们。军队可以移动,叶子节点不能被根节点到达,最短时间。发现二分首先发现时间越长,就越可能管辖成功。有这种显然的单调性促使我们二分找临界点。对于一个限定的时间,我们来想想怎么判定是否合法。发现越高越好首先,我们发现,能管辖的越高越好,一次可以管辖更多的子树。所以我们可以尽力往上...

2019-10-16 14:35:50

【TJOI2019】甲苯先生的滚榜【平衡树】

传送门练手题,两个关键字随便弄一下就行。不过我好久没打这东西以至于出了好些bug。顺带来记录一下treap怎么写。1.大根堆最好(我也不知道为啥啊我小根堆就错了)2.insert:在二叉查找的基础上移动,移动到空新建。每次查儿子是否rnd大于自己,如果是挪上来。3.delete:二叉查找移动,如果查到分情况讨论。①:有多个,直接减少。②只有一个,将左或者右儿子按照规则挪上来,将...

2019-10-16 13:32:08

【TJOI2019】甲苯先生的字符串【矩阵快速幂】

传送门咕咕TJOID1T1,难度不大,还能下手。任何相邻不能出现,相当于给了十万个限制。然后计数。当我们一筹莫展的时候,我们发现了数据范围。n好大哦。这么大一般就是矩阵快速幂了呀。然后我们想起来字符串的矩阵状态往往是字符到另一个字符的方案数。矩阵相乘相当于在两个字符中间放东西。那我们的初始矩阵就是两个字符之间不放东西。那合法的就是1,不合法就是0。所以n次矩阵表示长度为n...

2019-10-16 09:57:27

【HAOI2016】找相同字符【后缀自动机】

传送门后缀自动机总结这种需要匹配的问题都是将一个串建成自动机,别的串上去跑。在跑的时候叠加答案,我们发现如果找上了一个结点,那这个结点的所有fail,作为这个子串的后缀,都应该被匹配。所以答案应该从fail链上累加下来。而每个点代表一个串集合。串的个数是maxlen-minlen+1。而minlen=fail的maxlen+1。所以直接减去fail的maxlen就能得到本点代表的字符串...

2019-10-16 09:05:36

【SPOJ8222】Substrings【后缀自动机】

万能VJudge后缀自动机总结求每种长度的子串最大数量。fail树上加起来即可。注意:初始size只能打在字符结点上,不能打在复制结点上。这违背了size的本意。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongcharch[250003];structnode{ in...

2019-10-16 08:15:18

【SDOI2016】生成魔咒【后缀自动机】

传送门后缀自动机总结后方加点,问本质不同子串数量。每新加一个点,当前点的maxlen减去fail的maxlen就是多出来的子串数量。如此便可以维护。不过字符集太大,可以使用map来装儿子。#include<bits/stdc++.h>usingnamespacestd;#defineinread()#defineintlonglongint...

2019-10-16 07:42:08

csp-plus 20191015 【模拟】【结论+排序】【位运算】

数独woj4218咕咕咕分糖果woj4219交换两个找结论,证明贪心。发现min(a,d)<min(b,c)成立。但实际上如果sort的话,这个结论是不完全正确的。因为不满足传递性和非等式性。真正的证明见洛谷题解第一个不过写个最弱的也能过woj。#include<bits/stdc++.h>usingnamespacestd;#def...

2019-10-15 21:33:05

【NOI模拟】Juice【结论】

传送门题目可以qq找我这题也是很nb,,服了气。就是说,如果你看不出结论1,你就GG退赛了。假设答案为m,将每个果汁的数量乘以m,保证总数量为S*m(S是果汁原数量合)现在问题转化为将所有果汁放进m个桶,每个桶容积是S。结论1:对于任何a种果汁数量合为(a-1)*S,均可以用(a-1)个桶装完。归纳证明:a=2显然成立。a>2,令最多果汁数量为Max,最少为M...

2019-10-15 17:15:30

【NOI模拟】Forest【set】

传送门题目可以qq找我要每个点只有一个出点。维护权值c。同样我们从修改对答案的影响这个角度来思考问题。如果我修改了一个点的出边,就会修改度数,修改度数就会修改E。而修改E会修改这个点周围一圈的所有C。这号rilong啊,,复杂度爆炸。抓住出边为1这个条件。再将被影响的点分类。父亲:单点修改,我:单点修改,儿子们:一大群,我们可以找个什么东西来维护。我们发现权值的计算公式...

2019-10-15 16:34:05

【AHOI2013】差异【后缀自动机】

后缀自动机总结传送门求任意两个后缀长度减去其公共前缀长度。如果把串反过来,就是任意两个前缀长度减去其公共后缀长度。公共后缀直接fail树上lca即可。而字符串前缀只有原串长度len个。根据公式,如果将问题转化为两点路径长度和,那边权赋为子节点长减去fail节点长。这样问题就得以转化。而一条边的贡献就是其两端size的乘积。如此可以计算。#include<...

2019-10-15 07:55:53

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周上午根据用户上周周三的博文发布情况由系统自动颁发。