21.6.18 考试小记
发布于 8 小时前
刚从NEYC回来，才发现好久没写题解了。 T1 维护一个集合，支持插入一个数、删除一个数、全局加x(<=1e9)、查询二进制第k位为1的数有多少个。 我们只需要对...
Posts
LOJ 2463 「2018 集训队互测 Day 1」完美的旅行
发布于 13 天前
首先，考虑直接DP，显然我们需要求出两个数组：f[i][j]：走一条路，与出来是i，步数为j的方案数；g[i][j]：走若干条路，与出来是i，步数为j的方案数。 显然f...
特征多项式求解常系数线性递推
发布于 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)的时间复...
OI Bucketlist | AFO之前要巩固的知识点
发布于 24 天前
The Bucklist 数学 多项式相关： 多项式求逆 多项式取模 多项式除法 生成函数 特征方程优化递推 计算几何相关： 半平面交、动态凸包 旋转卡壳 ...
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），非常气愤！ 正...
