几个活蹦乱跳的指针的跳跃次数,决定着莫队算法的优劣…… ·目前的题型概括为三种:普通莫队,树形莫队以及带修莫队。 若谈及入门,那么BZOJ2038的美妙袜子一题堪称顶尖。 【例题一】袜子 ·述大意: 进行区间询问[l,r],输出该区间内随机抽两次抽到相同颜色袜子的概率。 ·分析: 首先考虑对于一个长度为n区间内的答...
摘要: 大米饼正式退役了,OI给我带来很多东西 我会的数学知识基本都在下面了 博客园的评论区问题如果我看到了应该是会尽力回答的... 这也是我作为一个OIer最后一次讲课的讲稿 20190731 多项式乘法 FFT 基本概念 1.多项式的两种表达(拉格朗日插值法) 多项式:$A(x) = \sum_{i=0 阅读全文 ...
【题目描述】 有 n 个正整数 x1~xn,初始时状态均为未选。有 m 个操作,每个操作给定一个编号 i,将 xi 的选取状态取反。每次操作后,你需要求出选取的数中有多少个互质的无序数对。 【输入数据】 第一行两个整数 n,m。第二行 n 个整数 x1~xn。接下来 m 行每行一个整数。 【
后缀数组是处理字符串的有力工具。———罗穗骞 ·前面的言 在后缀树,后缀自动机以及后缀数组三者中似懂非懂地抉择之后,综合代码量和实用性方面的考虑,你选择了学习后缀数组。本文会像往常一样,以更加朴素和便于理解的方式来献出大米饼自己对于后缀数组的理解。 ·LCP——一个问题的引入 LCP(Longest Common Prefix...
回首望去常规那边,只剩大米饼了… 张姐还在调AC自动机,(她说:我很累) LENCE在……… 袁YT在做二分题, 王SY在……… 不要放弃,大不了再给你一个大米饼。 Don’t give up,anyway we can still get a big-riced pancake! WSY:LCA这个题哪门做的?
对人脑来说不如中缀表达式好看,但是对计算机来说很有用。计算时拿一个栈来存放结果,从左往右一次扫描后缀式如果为数字(a,b,c,d,e,f)就直接加入栈中,如果为运算符(-*/-)就取出栈顶的两个元素进行运算,注意这样的运算是有顺序的,即 次栈顶 (运算) 栈顶 ,因为类似减号这样的东西是没有交换律的; ...
最近改换了博客风格,以前可能是不太舍得大米兔的风格,或者说比较倔,感觉换了风格就不太对得起博客,省选过后的半年里感觉十分绝望,停更了一段时间,竞赛学习也有点滞留期,后面想清楚了,开始复习了也觉得自己应该写点,可能很多都以专题呈现,但是我本人变化比较大。。;我现在更希望用简洁但能引导思维的语言去经营博...
随笔分类 -括号序列 【bzoj4337】【Bjoi2015】树的同构 摘要:题解 无标号树的HASH: 找到树的重心,以重心为根求出括号序列; 由于树的重心最多只有两个,取字典序的最小括号序列HASH即可 树的括号序列su="(sv1,sv2,sv3,...,svn)"su="(sv1,sv2,sv3,...,svn)",同时字典序$s_{v_{1}} <= s_{v阅...
博客园 首页 新随笔 联系 订阅 管理 随笔分类 - 生成函数 【JZOJ6239】【20190629】智慧树 摘要:题目 一颗nn个节点的树,每个点有一个权值aiai 询问树上连通块权值之和对 mm 取模为xx 的方案数 答案对950009857950009857 取模,满足m|950009856m|950009856 空间32 M32 M 题解 考虑Fi(x)Fi(x)为i为根...
博客园 首页 新随笔 联系 订阅 管理 快速傅里叶变换(FFT) 如果说出题人给了你一个卷积的话,那么你应该也友好的回赠他一个FFT; ---FFT ·一个问题:FFT的作用是:给定两个多项式,在nlgn内求出其乘积多项式。 ·多项式的两种表达: 多项式∑n−1i=0ai∗xi∑i=0n−1ai∗xi可以用系数(a1,a2...