LWLAymh的备忘录

莉娃丽尔终于到了北方。 在来北方的火车上，莉娃丽尔鼓起勇气给那位先生写了一封道歉信。她原本想在下车后把道歉信塞在车轮和轨道的夹缝中，并且不在信封上写那位先生的名字。“这样一来，”她想，“就不会对先生的名誉有任何损失，而且信是被火车碾碎还是被路人捡到、以至于辗转到先生手中，这完全取…

随机化算法 基本分析 Union Bound 即: ,取等当且仅当所有 互斥. Markov 不等式 若 ,则 . Example(Max Cut算法) 一个无向无权图,将点集划分成两个部分,使得跨越这两部分的边尽可能多. 直接随机划分,容易见到每条边有 的概率是割边,因此期望自…

本文除特殊说明,所涉及数均为整数. 整除性及相关 如果 且 是一个整数,我们就说 整除 ,记作 . 能同时整除两个数 和 的数称为 和 的公因子,所有公因子中最大的那个称为最大公因子,记作 .而最小的能同时被 和 整除的非零数被称为他们的最小公倍数,记作 .不难发现 . 欧几里得…

前言 本博客的目的是整理一些选拔题供需要的朋友参考. 由于选拔题具有时效性, 因此可能不会及时更新新的题目. 当新的选拔题出现时, 如果有朋友愿意帮忙整理可以以任意方式联系博主, 十分感谢! 祝看到这篇博客的朋友顺利通过任意选拔考试! 2024寒假学堂(部分) Problem4 …

反演 假设有两个函数 和 满足: ,已知f求g的过程称为反演. 一般情况下,求反演只能高斯消元,但是有一些形式的反演有巧妙解法. 子集反演 一般形式: 证明: 不难发现,这个子集反演也就相当于在做高维前后缀和. Example1(2019zrpzt七连day1D) 根据子集反演,…

KMP Example1(zr23省选第一轮集训day5b) 必须提一下的是,能用KMP的前提是可以比较两个字符串是否相等,不一定是比较两个字母相等.只要能比较两个字符串是否相等,并且已知 能快速判断是否有 ,那么就可以使用KMP.并不要求 并且 才有 . 因此,我们取 的置换 …

反悔贪心 扫描线 第一题 https://www.luogu.com.cn/problem/P6940 首先发现,从上往下扫行,然后对于每个右下角匹配一个列最近的左上角是最优秀的.所以拿set维护上述过程. 第二题 https://www.luogu.com.cn/problem…

一些奇怪的没名字的短篇小故事。 这一面卷子还剩三道题，反面还有两道。上节课是自习，这卷子是课代表发下来让大家练手的。可我没能当堂做完。 “等做完这几道题，拿去给老师看一看吧，”我想着，“这是高考前最后一次了。” 我拿着笔在卷子上勾着答案。 “明天就是高考了。”我忽然想到，“可我并…

本质相同 Example1 对于所有满足以下条件的长度为 的序列 ,我们称它是好的: 对于每一个数 ,求它在每个好的序列中出现的次数的平方和.其中 ,任意模数. 首先注意到可以枚举每个数 出现的次数,这样就转化为对满足某些位置是 的好的序列计数. 对于一个没有限制的好的序列,设 …

OI中的线性代数 线性基 Example1 给定 个非平方因子数 ,求有多少种选取一个子集的方式满足每个质因子都在子集中恰好出现偶数次. . 考虑将每个数的质因子压成一个二进制数,那所求也就是问有多少种选取子集的方式使得子集内二进制数异或和为 .自然想到线性基. 的自由变量的数量…