加载中...
2024.8.7-A
欧几里得 algorithm:math 设棋子总共向左移动了 \(a\) 次,最终的落地为: \[ s-ax+y(n-a) = s+ny-a(x+y) \] 容易发现落点对 \(x+y\) 的取模结果不变,而 \([t-x.t+y)\) 区间内对 \(x+y\) 取模结果两两不同,二分答案即可。 容斥原理 algorithm:dp 一道思维难度大,码量奇小的题目。 由于答案是对 \(2\) 取模,容易发现
好文收集
介绍 这里放了很多不错的文章。 字符串 A tool for hacking rolling hashes with fixed modulos and bases On the mathematics behind rolling hashes and anti-hash tests 图论 2-SAT 超入门讲解
2024.8.5-A
T1 一切大师 algorithm:math 考虑将原式转换: \[ \begin{aligned} ans &=\sum_{a=1}^{L}\sum_{b=1}^{L}[lcm(a,b)]*|ax-by|\\ &= \sum_{d=1}^{L}\sum_{a=1}^{\left \lfloor \frac{l}{d}\right \rfloor}\sum_{b=1}^{\left \lfloor \frac{l}{ad}\right \rfloor}[\gcd(a,b)=1]*d*|ax-by|\\ \end{aligned} \] 直接爆算,发现 TLE。 预处理 \(\sqrt{L}\) 以内的 \(\gcd\),再卡一下常,即可过掉。 T2 你考它干嘛 暂缺 T3 digital 喜闻乐见的模拟题 algorithm:divide-and-conquer 一个区间众数为 \(1\),当且仅当 \(1\) 的个数大于等于 \(\left \lfloor \frac{n+1}{2}\right \rfloor\)。 考虑分治,设 \(solve(l,r,x)\) ...
2024.8.1-A
考虑构造一道毒瘤题,它拥有 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- ...
2024.7.31-A
T1 United Cows of Farmer John algorithm: segtree 一道非常神奇的数据结构题。 考虑枚举每个区间的右端点,设当前点为 \(i\),值为 \(v_i\),上一个 \(v_i\) 的位置为 \(pre_i\)。 显然,左端点只能在 \((pre_i,i-1]\) 这个范围内。 当我们加入点 \(i\),那么 \((pre_i,i-1]\) 中左端点的方案数均可以加 \(1\),线段树维护即可。 但有一个问题,左端点不一定是连续的,所以我们再维护一个 \(0/1\) 的系数,表示这个点能否作为左端点。 T2 Permutation algorithm: dp 考虑答案的图应该长什么样子: 首先有一个三角形,每次选择一个点,分类讨论: 在三角形内,图还是一个三角形。 在三角形外,它会与原三角形的两个顶点构成一个新的三角形。 就两种情况,我们可以用动态规划来解决。 设 \(dp_{p,i,j,k}\) 为当前已经计算了 \(i\) 个点,答案为 \(i,j,k\) 三个顶点构成的三角形。 内部转移,相当于把 \(l\) 取出后,在 \(i,j, ...
2024.7.30-A
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}\) ...
字符串 Hash 的攻击
强烈建议尝试 Luogu U461211 字符串 Hash(数据加强) 前言 某天看到同学打 字符串hash,发现还在用 腐朽 的 单模数hash。 为了帮助他改进码风,我决定 卡炸hash。 一、大模数哈希 1.前言 我们知道,要想卡掉 hash,本质上就是让两个字符串有相同的 hash 值,我们称为哈希碰撞。 假设 hash 中每个值生成概率相同,则碰撞概率取决于两个因素: - 取值空间大小 - hash 的计算次数 这个问题在数学中有一个经典的问题,叫 生日问题。 简单来说,就是在一个有 d 人的班中,有人生日相同的概率为多少。 实际上,这个问题的答案并没有想象中的小,下面是部分概率: | 人数 | 概率 | | :---: | :------: | | 23 | \(50\%\) | | 50 | \(97\%\) | | 70 | \(99.9\%\) | 2.计算冲突概率 我们设 hash 的取值空间为 d,计算次数为 n。 则 hash 不冲突的概率为: \[ \overline{p}(n,d) = 1 \cdot \left (1 - \frac{1}{d} \rig ...
Windows 10 美化
AC 自动机
AC 自动机 很多人在第一次看到这个东西的时侯是非常兴奋的。不过这个自动机叫作 Automaton,不是 Automation,这里的 AC 也不是 Accepted,而是 Aho–Corasick(Alfred V. Aho, Margaret J. Corasick. 1975)。 前置 Trie (字典树) KMP (只要失配指针的思想即可) 定义 AC 自动机是 以 Trie (字典树) 的结构为基础,结合 KMP (字符串匹配) 的思想 建立的自动机,用于解决多模式匹配等任务。 构建 先简单解释一下: AC 自动机由两部分组成: 将模式串构造成一棵普通的 Trie。 利用 KMP 思想构造失配指针。 失配指针 同 KMP 一样,AC 自动机同样构造一个 fail 用于失配时的跳转指针。 但 AC 自动机的 fail 指向当前状态的最长后缀。 定义如下变量: 当前节点 u,u 的父亲节点 p,p 和 u 间用一条字符 c 连接。 字典树的边集 tr。(\(tr[u][c]\) 表示节点 u 的 c 出边的点) 假设所有深度小于 u 的 fail 指针均已求得。 若 \ ...
字典树
字典树 定义 字典树 ( trie ),将多个字符串进行 树 一样的处理,从而快速查找的一种算法。 实现 如图,我们依次加入 1234567abababacaaacabcbacc 我们以边代表字母,结点之间的路径就为字符串 就得到了这棵树 1
How to prove Girl=Evil
\(\because To\ chase\ a\ girl\ needs\ time\ and\ money.\) \(\therefore Girl\ =\ Time\times Money\) \(\because time\ is\ money\) \(\therefore Girl\ =\ Money^2\) \(\because money\ is\ the\ \textbf{root}\ of\ evil.\) \(\therefore Girl\ =\ (\sqrt{Evil})^2\) \(\therefore Girl\ =\ Evil\) 重点词解释: chase n. 追求 root n. 根;根源 evil adj. 邪恶的
oi梗
关于一些oi的梗 模拟只会猜题意,贪心只能过样例。数学上来先打表,DP一般看规律。 组合数学靠运气,计算几何瞎暴力。图论一顿套模板,数论只会GCD。 骗分过样例,暴力出奇迹。暴搜挂着机,打表出省一。N方过百万,暴力踩标算。肥修赛大象,只是代码短。 想要骗到分,一定有方法。图论背模板,数论背公式。动规背方程,高精背代码,要是都不会,干脆输样例。 10年OI一场空,没开long long见祖宗 高级算法:可持久化非确定状态AC自动分块维护线段平衡仙人掌优化最小费用最大流预处理混合图上莫比乌斯反演莫队带花舞蹈链并查集树状数组套主席树预处理动态DP分治FFT求多项式逆元对数函数的指数函数用可持久化并查集合并最小费用循环流上插头DP 模拟只会猜题意,贪心只能过样例。 数学上来先打表,动规一般看规律。 组合数学靠运气,计算几何瞎暴力。 图论一顿套模板, 数论只会GCD。 递归递推伤不起,搜索茫然TLE。 分治做得像枚举,暴力枚举数第一 数据结构干瞪眼,怒刷水题找信心。 涨姿势也不容易,考试一来全懵逼。 怎么进队拿国一?看懂洛谷A+B。 刷题是一种出路, 枚举是一种思想。 打表是一种勇气, ...
avatar
星光light
星光照耀,灿烂前行
Follow Me
最新文章
网站资讯
文章数目 :
34
已运行时间 :
本站总字数 :
31.4k
本站访客数 :
本站总访问量 :
最后更新时间 :