- 博客(39)
- 收藏
- 关注
RSS订阅原创 【BZOJ4241】历史研究（回滚莫队）
题目：BZOJ4241分析：本校某些julao乱膜的时候发明了个“回滚邹队”，大概意思就是某个姓邹的太菜了进不了省队回滚去文化课回滚莫队裸题qwq（话说这个名字是不是莫队本人起的啊这么萌zui首先看到题询问区间信息+没强制在线，妥妥的莫队。然而朴素的莫队（开个桶记每种事件当前的重要度，用set或者堆之类维护一下答案）要O(nnlogn)O(n\sqrt n \log n)O(nnlo...
2018-12-21 22:26:10
224
原创 【知识总结】后缀自动机的构建
参考资料：(APIO2018)从DFA到后缀自动机_张云帆又一个学了很多遍都不会的算法/数据结构……（话说我怎么每篇知识总结一开始都是这句话qwq）先orz后缀自动机之神兔崽子TzzDzz（顺便喂它最喜欢吃的叶子）OrzTzzDzz前排提示：由于作者很菜，且本文的目标是快速理解并写出 （背过） 后缀自动机的构建过程，所以将会省略很多结论的证明，语言也有不严谨之处，敬请谅解。如感兴趣可以参考...
2018-12-21 22:25:47
248
原创 【洛谷1117_BZOJ4650】[NOI2016] 优秀的拆分（哈希_后缀数组_RMQ）
题目：洛谷1117分析：定义把我校某兔姓神犇Tzz和他的妹子拆分，为“优秀的拆分”随便写个哈希就能有959595分的好成绩……我的959595分做法比fei较chang奇葩，不想浪费时间的可以忽略解法一qwq解法一：用nnn个vector记录对于每个点iii，哪些长度lenlenlen满足i+2len≤ni+2len\leq ni+2len≤n且str[i,i+len)=str[i+...
2018-12-21 22:25:27
390
原创 【BZOJ3527】[ZJOI2014] 力（FFT）
题目：BZOJ3527分析：FFT应用第一题……首先很明显能把FjF_jFj约掉，变成：Ej=∑i&lt;jqi(i−j)2−∑i&gt;jqi(i−j)2E_j=\sum _{i&lt;j} \frac{q_i}{(i-j)^2}-\sum_{i&gt;j}\frac{q_i}{(i-j)^2}Ej=i<j∑(i−j)2qi−i>j...
2018-12-21 22:24:39
134
原创 【洛谷4215】踩气球（线段树）
题目：洛谷4215分析：感觉思路有点像线段树分治？把所有区间插到线段树上。我一开始的想法是修改时给树上一条链上包含的所有熊孩子的值都减111，然后发现这个单次最坏是O(m)O(m)O(m)的，gg。可以记录每个熊孩子被分成了多少个非零的区间。修改时如果某个区间变成000了，那么就给包含该区间的熊孩子的区间数减111，这样均摊最多有mlogmm\log mmlogm个区间，总复杂度O(q...
2018-12-14 07:30:58
155
原创 【BZOJ3294/洛谷3158】[CQOI2011]放棋子（组合数+DP）
题目：洛谷3158分析：某OIer兔崽子的此题代码中的三个函数名：dfs、ddfs、dddfs（充满毒瘤的气息显然，行与行之间、列与列之间是互相独立的。考虑背包，用f[k][i][j]f[k][i][j]f[k][i][j]表示用前kkk种颜色占了iii行jjj列的方案数，g[i][j]g[i][j]g[i][j]表示用颜色kkk占据iii行jjj列的方案数，c[i]c[i]c[i]表示颜...
2018-12-14 07:19:19
138
原创 【知识总结】后缀数组（Suffix_Array）
又是一个学了n遍还没学会的算法……后缀数组是一种常用的处理字符串问题的数据结构，主要由sasasa和rankrankrank两个数组组成。以下给出一些定义：strstrstr表示处理的字符串，长度为lenlenlen。（下标从000开始）[i,j)[i,j)[i,j)表示strstrstr从iii到j−1j - 1j−1的字串。后缀iii表示子串[i,len)[i,len)[i,len)，...
2018-12-14 07:18:55
320
原创 【Codeforces576E_CF576E】Painting Edges（可撤销并查集+线段树分治）
题目CF576E分析：从前天早上肝到明天早上qwq其实颓了一上午MC ，自己瞎yy然后1A，写篇博客庆祝一下。首先做这题之前推荐一道很相似的题：【BZOJ4025】二分图（可撤销并查集+线段树分治）大力每个颜色维护一个并查集，就很像上面那道题了。但是存在一个问题：在处理线段树区间[l,r][l,r][l,r]时，可能并不知道lll处的修改是否成功，所以不知道lll处修改的边具体是什么颜色...
2018-12-14 07:18:25
593
原创 【BZOJ1483】[HNOI2009]梦幻布丁（平衡树启发式合并+并查集）
题目：BZOJ1483分析：（这题码了一下午，码了近250行，但是意外跑的比本校各位神仙稍快，特写博客纪念）首先能看出一个显然的结论：颜色段数只会变少不会变多。我们考虑用并查集维护区间，对于每个区间维护它的起点和终点。建nnn棵平衡树，第iii棵存颜色为iii的区间。把xxx变成yyy时进行启发式合并，同时对于xxx上的每个结点[a,b][a,b][a,b]，在yyy中找a−1a-1a−...
2018-12-03 13:26:33
174
原创 【BZOJ4025】二分图（可撤销并查集+线段树分治）
题目：BZOJ4025分析：定理：一个图是二分图的充要条件是不存在奇环。先考虑一个弱化的问题：保证所有边出现的时间段不会交叉，只会包含或相离。还是不会？再考虑一个更弱化的问题：边只会出现不会消失。当加边的时候，若(u,v)(u,v)(u,v)不连通：一定不会构成奇环，将它加入。若(u,v)(u,v)(u,v)已经联通，则不加入这条边，而是查询uuu和vvv两点间的距离。若为偶数则...
2018-11-25 11:26:39
391
原创 【BZOJ3110】[ZJOI2013]K大数查询（整体二分）
题目：BZOJ3110分析：整体二分模板题……先明确一下题意：每个位置可以存放多个数，第一种操作是“加入 (insert) ”一个数而不是“加上 (add) ”一个数。首先考虑只有一次询问的情况。设询问的名次为kkk，我们二分出一个答案midmidmid，然后遍历所有修改。建立一棵区间线段树（下标是位置的线段树），对于一个给[a,b][a,b][a,b]区间加入一个数ccc的修改，如果c...
2018-11-24 17:27:28
189
1
原创 【BZOJ2149】拆迁队（斜率优化DP+CDQ分治）
题目：BZOJ2149分析：先吐槽一下题意：保留房子反而要给赔偿金是什么鬼哦……第一问是一个经典问题。直接求原序列的最长上升子序列是错误的。比如{1,2,2,3}\{1,2,2,3\}{1,2,2,3}，选择{1,2,3}\{1,2,3\}{1,2,3}不改变后会发现无论如何修改都无法变成一个严格上升序列。只能选择{1,2}\{1,2\}{1,2}，把原序列改成{1,2,3,4}\{1,2...
2018-11-15 23:20:58
226
原创 【知识总结】快速傅里叶变换（FFT）
这可能是我第五次学FFT了……菜哭qwq先给出一些个人认为非常优秀的参考资料：一小时学会快速傅里叶变换（Fast Fourier Transform） - 知乎小学生都能看懂的FFT！！！ - 胡小兔 - 博客园快速傅里叶变换（FFT）用于计算两个nnn次多项式相乘，能把复杂度从朴素的O(n2)O(n^2)O(n2)优化到O(nlog2n)O(nlog_2n)O(nlog2n)。一个常见...
2018-11-14 23:52:55
1029
原创 【洛谷4396/BZOJ3236】[AHOI2013]作业（莫队+分块/树状数组/线段树）
题目：洛谷4396BZOJ3236（权限）这题似乎BZOJ上数据强一些？分析：这题真的是……一言难尽发现题面里没说权值的范围，怕出锅就写了离散化。后来经过面向数据编程（以及膜神犇代码）知道最大权值1e51e51e5（下文用MMM表示最大权值。注意如果没有这个限制，把所有数的权值和询问中提到的权值一起离散化后MMM也可以达到n+2m=2.1e6n+2m=2.1e6n+2m=2.1e6），...
2018-11-13 23:34:24
131
原创 【洛谷3648/BZOJ3675】[APIO2014]序列分割（斜率优化DP）
题目：洛谷3648注：这道题洛谷3648有SPJ，要求输出方案。BZOJ3675数据组数较多但不要求输出方案。分析：这可能是我第三次重学斜率优化了……好菜啊这道题首先一看就是个DP。稍微推一推类似下面这种式子就会发现事实上结果和切的顺序无关a(b+c)+bc=ab+c(a+b)=ab+ac+bca(b+c)+bc=ab+c(a+b)=ab+ac+bca(b+c)+bc=ab+c(a+b...
2018-11-07 08:39:16
159
原创 【洛谷4933】大师（DP）
题目：洛谷4933分析：（自己瞎yy的DP方程竟然1A了，写篇博客庆祝一下）（以及特斯拉电塔是向Red Alert致敬吗233）这里只讨论公差不小于000的情况，小于000的情况进行复读机即可（注意不要重复计算公差为000的情况）。用dp[i][j]dp[i][j]dp[i][j]表示结尾为第iii个数，公差为jjj的长度不小于222的非降等差数列的方案数（单独111个数的情况公差不确...
2018-10-27 19:49:29
193
原创 【Codeforces827D/CF827D】Best Edge Weight（最小生成树性质+倍增/树链剖分+线段树）
题目Codeforces827D分析倍增神题……（感谢T*C神犇给我讲qwq）这道题需要考虑最小生成树的性质。首先随便求出一棵最小生成树，把树边和非树边分开处理。首先，对于非树边(u,v)(u,v)(u,v)（表示一条两端点为uuu和vvv的边，下同）。考虑Kruskal算法的过程，它必定成为树边的充要条件是它的权值小于树上uuu到vvv之间的路径上的某条边eee，这样就会选中这条边来连...
2018-10-25 20:04:32
322
原创 【知识总结】扩展卢卡斯定理（exLucas）
扩展卢卡斯定理用于求如下式子（其中ppp不一定是质数）：Cnm&amp;amp;amp;amp;nbsp;mod&amp;amp;amp;amp;nbsp;pC_n^m\ mod\ pCnm&amp;amp;amp;amp;nbsp;mod&amp;amp;amp;amp;nbsp;p我们将这个问题由总体到局部地分为三个层次解决。一首先对ppp进行质因数分解：p=∏ipikip=\prod_i p_i^{k_i} p=i∏piki
2018-09-29 16:56:17
6047
原创 【洛谷1654/BZOJ4318】OSU！（期望DP）
题目：洛谷1654分析：本人数学菜得要命，这题看了一晚上才看明白……先说说什么是“期望”。不太严谨地说，若离散型随机变量（可以看作“事件”）XXX取值为xix_ixi的概率为pip_ipi，则它的期望E(X)E(X)E(X)为：E(X)=∑ixipiE(X)=\sum_i x_ip_iE(X)=i∑xipi（下面大段胡扯可以跳过）举个例子：Monster of the Mo...
2018-09-24 00:23:02
241
原创 【BZOJ1939】[Croatian2010] Zuma（动态规划）
题目：BZOJ1939（权限题）分析：这题很容易看出是DP，但是状态和转移都不是很好想……用dp[l][r][c]dp[l][r][c]dp[l][r][c]表示在lll前面已经新加了ccc个和lll一样的弹子时，使区间[l,r][l,r][l,r]消完所需插入的弹子数量显然，当c≥k−1c\geq k-1c≥k−1时，这ccc个弹子和lll组成了连续的至少kkk个弹子，这些情况是类似的...
2018-09-20 23:46:33
310
原创 【BZOJ2762】[JLOI2011]不等式组（树状数组）
题目：BZOJ2762分析：加入的不等式分三种情况 当a&gt;0a&gt;0a>0，可以变成x&gt;⌊c−ba⌋x&gt;⌊c−ba⌋x>\lfloor \frac{c-b}{a}\rfloor 当a=0a=0a=0，若b&gt;cb&gt;cb>c则恒成立，否则恒不成立 当a&lt;0a&lt;0ax&a
2018-09-15 12:06:38
302
原创 【洛谷2469/BZOJ1927】[SDOI2010]星际竞速（费用流/最小路径覆盖）
题目：洛谷2469分析：（挖坑待填） 戳我进入兔崽子的博客代码：#include &lt;cstdio&gt;#include &lt;algorithm&gt;#include &lt;cstring&gt;#include &lt;iostream&gt;#include &lt;queue&gt;us
2018-09-08 20:11:29
178
原创 【洛谷2257/BZOJ2820】YY的GCD（数论/莫比乌斯函数）
题目：洛谷2257预备知识：莫比乌斯定理（懵逼乌斯定理）μ∗1=ϵμ∗1=ϵ\mu*1=\epsilon（证bu明hui略zheng） 其中（我校学长把ϵ(x)ϵ(x)\epsilon(x)叫单位函数但是为什么我没百度到qwq） ϵ(x)={10x=1x≠1ϵ(x)={1x=10x≠1\epsilon(x)=\begin{cases}1 & x=1\\0 & x\neq1\\\...
2018-09-08 19:36:16
199
原创 【知识总结】约数个数定理和约数和定理及其证明
据说这俩是小学奥数内容？完了我菜成一团没上过小学本文只研究正整数AAA的约数个数和约数和。首先对AAA分解质因数A=∏inpaii (pi是质数)A=∏inpiai (pi是质数)A=\prod_i^n p_i^{a_i} \ (p_i是质数) 约数个数定理先看结论 num=∑in(ai+1)num=∑in(ai+1)num=\sum_i^n (a_i+1)...
2018-07-14 18:26:18
3560
原创 【POJ1845】Sumdiv（数论/约数和定理/等比数列二分求和）
题目：POJ1845分析：首先用线性筛把AAA分解质因数，得到： A=pa11∗pa22...∗pann(pi是质数且ai&amp;gt;0)A=p1a1∗p2a2...∗pnan(pi是质数且ai&amp;gt;0)A=p_1^{a_1}*p_2^{a_2}...*p_n^{a_n} (p_i是质数且a_i&gt;0) 则显然ABABA^B分解质因数后为 A=pa1B1∗pa2B2...∗...
2018-07-13 17:13:05
233
原创 【CodeForces727E/CF727E】Games on a CD (字符串哈希)
题目：CodeForces727E分析：看到字符串比较，肯定想到哈希啊……现学的哈希，先丢两个重要的公式 (seedseedseed是大于字符集大小的质数，ppp是大质数) hash[i]=(hash[i−1]∗seed+s[i])mod&nbsp;phash[i]=(hash[i−1]∗seed+s[i])mod&nbsp;phash[i]=(hash[i-1]*seed...
2018-07-11 21:50:41
235
原创 【洛谷3224/BZOJ2733】[HNOI2012]永无乡 (Splay启发式合并)
题目：洛谷3224分析：这题一看n≤100000n≤100000n\leq100000的范围就知道可以暴力地用O(nlogn)O(nlogn)O(nlogn)数据结构乱搞啊……每个联通块建一棵Splay树，查询就是Splay查询第k大的模板，建桥的时候就把两个联通块的Splay进行“启发式合并”本来以为启发式合并是什么高端的东西，tzh神犇给我说就是把小的推倒然后暴力插...
2018-07-10 18:54:35
170
原创 【BZOJ2565】最长双回文串 (Manacher算法)
题目：BZOJ2565分析：首先看到回文串，肯定能想到Manacher算法。下文中字符串sss是输入的字符串strstrstr在Manacher算法中添加了字符‘#’后的字符串 (构造方式如下) string s = "#";for (int i = 0; i < str.size(); i++){ s += str[i]; s += '#';}...
2018-04-17 14:43:24
182
原创 【洛谷2926/BZOJ1607】[USACO08DEC]Patting Heads拍头（筛法）
题目：洛谷2926(截止至本博客发表时，BZOJ1607题面有误，正确题面请到洛谷2926查看）分析：一句话题意：给定nnn个数{ai}{ai}\{a_i\}，求对于每个aiaia_i有多少个数ajaja_j满足ai|ajai|aja_i|a_j (1≤i,j≤n(1≤i,j≤n(1\leq i,j\leq n且i≠j)i≠j)i \neq j) 按题意模拟的话O(n2)...
2018-04-15 13:32:07
223
原创 【知识总结】卡特兰数 (Catalan Number) 公式的推导
卡特兰数的英文维基讲得非常全面，强烈建议阅读！Catalan number - Wikipedia(本文中图片也来源于这个页面) 由于本人太菜，这里只选取其中两个公式进行总结。 （似乎就是这两个比较常用？） 首先先扔卡特兰数的定义式Catalann=∏i=1n−1Catalani∗Catalann−iCatalann=∏i=1n−1Catalani∗Catalann−i...
2018-04-12 18:03:35
7828
2
原创 【BZOJ2944】[Poi2000]代码(卡特兰数)
这题在网上找不到题解，硬写一下午终于写出来了…… （编辑本文时博主为了输入表格和公式转了Markdown编辑器。。。Markdown就是好用) 题目：BZOJ2944分析：首先明确：比较两棵节点数相同的二叉树时，根节点是第一关键字，左子树是第二关键字，右子树是第三关键字；然后我们分析一下题目中那个4个节点，14种代码的例子 左子树大小slslsl ...
2018-04-09 18:39:57
436
2
原创 【POJ3280/洛谷2890】[Usaco2007 Open Gold]Cheapest Palindrome（动态规划）
题目：POJ3280洛谷2890分析：首先，考虑只可以加字的情况设s[i]表示第i个字符，add[i]表示加上一个字母i的花费，dp[i][j]表示把区间i~j变成回文串的花费，那么1.如果s[i]==s[j]，那么只需要把(i+1)~(j-1)变成回文串就可以了，即dp[i][j]=dp[i+1][j-1]2.如果s[i]!=s[j]，那么可以先把i~(j-1)变成回文串，然后在前面加一个s[j...
2018-01-20 15:04:53
298
原创 【洛谷3467/BZOJ1113】[POI2008]海报PLA-Postering（单调栈）
题目：洛谷3467分析：（ti jie shuo）这题是个单调栈经典题。单调栈就是栈元素递增或递减的栈，这里只考虑递增。新元素入递增栈时，先将所有比它大的元素弹出，然后让新元素入栈，这样保证栈顶永远是最大的元素，代码如下：（a是新元素）while(top>0&&stack[top]>a)top--;stack[++top]=a;然后来分析这道题。我这种蒟蒻乍一看一脸懵...
2017-12-20 13:51:04
254
原创 【Vijos1083/BZOJ1756】小白逛公园（线段树）
【写在前面】TYC (Little White) 真是太巨啦！题目：Vijos1083分析：一眼看上去就是线段树啊……然而当我这种蒟蒻兴高采烈地把线段树模板敲了一半，却发现一个问题：这子区间最大值的查询咋整啊……于是经过仔cha细zhao思ti考jie，设计了这样一个线段树结点类型：struct node{ int val; int lm; int rm; int mm;}tree[2...
2017-12-19 21:09:48
332
原创 【POJ3255/洛谷2865】[Usaco2006 Nov]路障Roadblocks（次短路）
本文Markdown版见http://www.cnblogs.com/zyt1253679098/p/8867678.html题目：POJ3255洛谷2865 分析：这道题第一眼看上去有点懵……不过既然要求次短路，那估计跟最短路有点关系，所以就拿着优先队列优化的Dijkstra乱搞，搞着搞着就通了。开两个数组：dis存最短路，dis2存次短路在松弛的时候同时更新...
2017-12-18 09:27:26
208
原创 【洛谷2982】[Usaco2010 Feb]慢下来Slowdown（dfs序+线段树）
题目：洛谷2982分析：这道题最重要的是想明白一点：牛i走到以后只对P_i的子树产生影响知道这个以后，就可以想到在线维护每个牧场已经被“影响”了多少次（也就是在此之前有多少个牛是到达自己的祖先结点的），这就是从谷仓到这个牧场需要减速多少次。怎么维护子树信息呢？dfs序+线段树啊……于是变成模板题代码：（虽然题目只要求支持单点查询，但是线段树模板打顺手了就不知不觉地写了区间查询……）in[i]代表i...
2017-12-16 13:58:34
233
原创 【洛谷2904/BZOJ1617】[USACO08MAR]跨河River Crossing（动态规划）
本文Markdown版见http://www.cnblogs.com/zyt1253679098/p/8795767.html题目：洛谷2904分析：裸dp……dp方程也不难想：dp[i]表示运i头牛需要的最短时间，sum[i]表示一次运i头牛（往返）所需的时间则dp[i]=min(dp[i],dp[j]+sum[i-j])(0<=j<i)注意sum[0]是m*2而不是0（船上只有FJ...
2017-12-10 23:05:52
220
原创 【洛谷4158/BZOJ1296】[SCOI2009]粉刷匠（动态规划）
本文Markdown版见http://www.cnblogs.com/zyt1253679098/p/8779732.html题目：BZOJ1296分析：这题一看就是动态规划。可以看出，如果每个木条粉刷的次数是固定的，那么这些木条是互不干扰的，因此对于每个木条可以通过dp来求出把T次中的j次分配给这个木条时可以获得的最大正确数，然后再dp出如何分配这T个粉刷次数可以获得最优解（类似于背包）。针对这...
2017-12-10 21:18:34
302
2
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人