LWLAymh的备忘录

前言 本博客的目的是整理一些选拔题供需要的朋友参考. 由于选拔题具有时效性, 因此可能不会及时更新新的题目. 当新的选拔题出现时, 如果有朋友愿意帮忙整理可以以任意方式联系博主, 十分感谢! 祝看到这篇博客的朋友顺利通过任意选拔考试! 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 给定 个非平方因子数 ,求有多少种选取一个子集的方式满足每个质因子都在子集中恰好出现偶数次. . 考虑将每个数的质因子压成一个二进制数,那所求也就是问有多少种选取子集的方式使得子集内二进制数异或和为 .自然想到线性基. 的自由变量的数量…

动态规划的设计 分析状态 Example1 给定一个序列,初始为空,进行多次操作,每次在序列末尾等概率加入一个 中的数字,然后进行以下判断: 1. 如果当前序列末尾两个数字相同且小于 ,假设都是 ,那就将它们都删去,加入一个 . 2. 如果当前序列没有可以删的数字,并且序列长度为…

Bash游戏 和 ,有 颗石子,每次可以取 颗,其中 ,求 是否能赢. 考虑直接令石子数量为状态,有 ,注意到 当且仅当 . 我们使用数学归纳证明: 当 时,显然成立. 而对于 ,如果 ,那么集合 中一定 满足 . 也就是 满足 ,那么 .反之,一定存在. Nim游戏 和 ,有 …

数据结构理论 维度 B维正交范围 对于一个 维的点 ,满足 ,称所有这样的点组成的集合为一个 维正交范围. 一维正交范围就是区间,二维正交范围是矩形,三维正交范围是立方体. 另外,如果 有若干个是自动满足的(所有点都满足),那么我们称它为无用限制,如果一个 维正交范围有 个有用限…