Posts

21.6.18 考试小记

发布于 8 小时前

刚从NEYC回来,才发现好久没写题解了。 T1 维护一个集合,支持插入一个数、删除一个数、全局加x(<=1e9)、查询二进制第k位为1的数有多少个。 我们只需要对...


特征多项式求解常系数线性递推

发布于 21 天前

给定长为m的数列a,求递推数列\(f(n)=\sum _{i=1}^{m}a_{i}f(n-i)\)的第n项,\(n \leq 10^9,m \leq 3000\)。 如果m小一些的话,我们可以用O(m^3logn)的时间复...


LOJ#6053. 简单的函数 Min_25筛

发布于 25 天前

Min_25筛可以求一些积性函数的前缀和,复杂度\( O(\frac{n^{\frac{3}{4}}}{ln(n)}) \)。 具体来说,如果对于质数p,f(p)是一个低阶多项式,那么我们就可以求...


26.5.18 考试小记

发布于 25 天前

OI赛制,部分分给的档次比较多。 T1 给定一个长为n(<=1e6)的序列,每次可以修改一个元素,求每次修改后,给每个数xor上一个数x,使得整个序列单调不减的最...


24.5.18 考试小记

发布于 27 天前

IOI赛制。 T1 裸的三维偏序,但n<=2e6,且三个权值均不重复。 CDQ+BIT可以获得60分,但是正解必定是一个log的复杂度。 考虑容斥,若只考虑两维限制,加起...


LOJ #2565. 「SDOI2018」旧试题

发布于 2018-05-18

求\(\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c}d(ijk)\),其中\(a,b,c\leq 10^5\),最多10组数据。 曾经考过这道题的弱化版:26.3.18 考试小记,但是这道题...


16.5.18 考试小记

发布于 2018-05-16

T1 BZOJ 4662 题意略。可以发现\(L_i\)、\(R_i\)一定分别单调增,任意时刻每个人剩下的区域是一段连续区间,且区间左右端点分别单调不降。这样,我们可以维护...


JSOI2018 Day2 部分题解

发布于 2018-05-05

T1 LOJ#2549. 「JSOI2018」战争 考试的时候打了个期望70分的半平面交,无奈学校的OJ跑的实在太慢了一直是40(LOJ和本机最慢的点都只要0.7s),非常气愤! 正...