星光light

介绍 这里放了很多不错的文章。 字符串 A tool for hacking rolling hashes with fixed modulos and bases On the mathematics behind rolling hashes and anti-hash tests 图论 2-SAT 超入门讲解

考虑构造一道毒瘤题，它拥有 T1 的时间复杂度分析，T2 的数学推导，T3 的代码难度，T4 的卡常。 T1 往事成风 algorithm:segtree 结论题，下面给出三个结论： 在最优划分中，每个区间的众数都是不同的，否则显然可以合并到一起减小答案。 若不考虑编号的限制，我们将某些数字选为最后的众数。若这个方案合法，没有被选为众数的数的个数的最大值一定小于等于选出的众数的个数之和。 这样我们可以得到一个朴素算法，对于每次询问，从高位向地位枚举，如果将当前数字删去后仍满足条件，则删去。最后保留的数字即为众数。 设 \(V\) 为值域,所有删去的数字形成的连续段数量级为 \(O(\sqrt{V})\)。（我不会证） 考虑优化朴素算法，我们在线段树上删除连续段： 1. 若删去当前节点最小值仍不满足，直接返回。 2. 若将右子树删除满足条件，删去它并遍历左节点。 3. 否则先遍历右子树，再遍历左子树。 T2 数数乐（eval） algorithm:math \[ f(n)=\sum_{k=0}^n 2^{n-k}\sum_{m=0}^k \binom{k}{m}\binom{k- ...

T1 Promotion Counting algorithm: segtree, BIT 水题，树状数组差分即可。 T2 rabbit algorithm: network-flow, greedy 乱搞。 将数据用桶装起来，枚举胡萝卜或干草，与另一个分别相减。 网络流？不会（好像是最小割）。 T3 【2024年SD省队集训 day2】反转了 (flip) algorithm: PST, divide-and-conquer 先考虑朴素算法，若当前前缀和右端点为 \(i\)，则反转的肯定为 \([1,i]\) 间最小的 \(k\) 个数，用主席树计算，时间复杂度 \(O(n^2log \ n)\)。 发现有决策单调性，第 \(k+1\) 次反转的最优右端点 一定大于 等于第 \(k\) 次反转的右端点。 证明：https://lnw143.github.io/blog/gmoj/p8081/#%E5%8D%95%E8%B0%83%E6%80%A7%E8%AF%81%E6%98%8E 考虑分治，设函数 solve(l,r,L,R)。 每次把求 \(k = \frac{l+r}{2}\) ...

字典树 定义 字典树 ( trie )，将多个字符串进行 树 一样的处理，从而快速查找的一种算法。 实现 如图，我们依次加入 1234567abababacaaacabcbacc 我们以边代表字母，结点之间的路径就为字符串 就得到了这棵树 1

关于一些oi的梗 模拟只会猜题意，贪心只能过样例。数学上来先打表，DP一般看规律。 组合数学靠运气，计算几何瞎暴力。图论一顿套模板，数论只会GCD。 骗分过样例，暴力出奇迹。暴搜挂着机，打表出省一。N方过百万，暴力踩标算。肥修赛大象，只是代码短。 想要骗到分，一定有方法。图论背模板，数论背公式。动规背方程，高精背代码，要是都不会，干脆输样例。 10年OI一场空，没开long long见祖宗 高级算法：可持久化非确定状态AC自动分块维护线段平衡仙人掌优化最小费用最大流预处理混合图上莫比乌斯反演莫队带花舞蹈链并查集树状数组套主席树预处理动态DP分治FFT求多项式逆元对数函数的指数函数用可持久化并查集合并最小费用循环流上插头DP 模拟只会猜题意，贪心只能过样例。 数学上来先打表，动规一般看规律。 组合数学靠运气，计算几何瞎暴力。 图论一顿套模板， 数论只会GCD。 递归递推伤不起，搜索茫然TLE。 分治做得像枚举，暴力枚举数第一 数据结构干瞪眼，怒刷水题找信心。 涨姿势也不容易，考试一来全懵逼。 怎么进队拿国一?看懂洛谷A+B。 刷题是一种出路， 枚举是一种思想。 打表是一种勇气， ...