高级数据结构 学习笔记
前言 本文主要根据 OIwiki 的数据结构部分展开，也按照常见的考点加入了一些图论、字符串领域的数据结构。本文只包含最基本的理论介绍，相关的实现方式、具体的解题思路和代码都放在站内其他文章中。 后续做到比较好的数据结构题也会添加进这篇文章中来。 块状数据结构 分块初步 经典例题1：参见站内文章 LOJ6280 分块入门 区间和 解题笔记 总体思路：寻找一种合理的分块方式，操作区间中不是整块的部分暴力求解，是整块的部分打标记。 寻找最优分块方式，通常是对最坏时间复杂度求最小值，取得最小值时的约束条件可以得到最优块长。 在分块的基础上，依然可以使用差分、前缀和等方式来优化算法。差分、前缀和不仅可以对原序列使用，也可以对块序列使用。 相关注意事项： 块长不一定等于块数。 区间两端点在同一个块中，必须特判..
更多
复变函数与积分变换 学习笔记
前言 本文由周国全老师的数学物理方法、翔翔的学习频道在B站上传的视频总结而来，借用了华中科技大学的复变函数讲义。 感谢周国全老师、UP主翔翔和华中科技大学！ 第一章 解析函数 第一节 复数及其运算 基本定义 对于复数 z=x+iy∈Cz=x+\mathrm{i}y\in\mathbb{C}z=x+iy∈C ，称 x=Rezx=\mathrm{Re}zx=Rez 为其实部， y=Imzy=\mathrm{Im}zy=Imz 为其虚部。两复数相等，当且仅当他们的实部和虚部分别相等。用 z‾\overline{z}z 或 z∗z^*z∗ 表示与 zzz 实部相等、虚部相反的共轭复数（complex conjugation）。 通过两个共轭复数可以得出实部和虚部，这个方法非常重要。 x=z+z‾2x=\fr..
更多概率论数理统计 学习笔记
前言 感谢B站up主高数叔！每次上课之前打个铃，很有仪式感。 第一章 随机事件与概率 随机事件关系及其运算 名称 符号 理解 集合定义 AAA 包含 BBB A⊃BA\supset BA⊃B 事件 BBB 发生必有事件 AAA 发生 BBB 是 AAA 的子集 AAA 与 BBB 相等 A=BA=BA=B 事件 AAA 发生必有事件 AAA 发生且事件 BBB 发生必有事件 AAA 发生 AAA 与 BBB 包含的样本点相同 AAA 与 BBB 的和 A∪BA\cup BA∪B 事件 A∪BA\cup BA∪B 发生 ⇔\Leftrightarrow⇔ 事件 AAA 发生或事件 BBB 发生 AAA 与 BBB 的并集 AAA 与 BBB 的积 A∩BABA\cap B \\..
更多科目一知识点整理
超员 车型 (0,20%)(0,20\%)(0,20%) [20%,50%)[20\%,50\%)[20%,50%) [50%,100%)[50\%,100\%)[50%,100%) [100%,+∞)[100\%,+\infty)[100%,+∞) 校、公、旅 6 12 12 12 7座以上载客汽车 6 9 12 其他车 3 6 12 超载 车型 (0,30%)(0,30\%)(0,30%) [30%,50%)[30\%,50\%)[30%,50%)或载客 [50%,+∞)[50\%,+\infty)[50%,+∞) 载货汽车 1 3 6 超速 科目一过了😁，此文断更
更多行为经济学导论 学习笔记
行为经济学导论 Edoardo Galllo, Cambridge 两本参考书籍： Thinking fast and slow, by Kahneman Nudge: Improving Decsions About Health, Wealth and Happiness, by Thaler 开卷考试，20个选择题，有多选 第一节 行为经济学导论介绍 凯恩斯选美比赛 规则：每人从1~100中选择一个自己眼中最美的数字，被最多人公认的数字为最美数字，选中最美数字的人胜出。 特点：所有人选择数字的依据不是自己的想法，而是其他大多数人的预期。 类比：选数字相当于选股票。 阿莱悖论 彩票组1： 彩票A：100%概率获得 £500,000\pounds500,000£500,000 ..
更多随笔 那些灵光一闪的瞬间
前言 本文所有信息属于随笔性质，没有经过深刻的审视、反思与论证，以至于很多是情绪化的文字。 但我认为，即使是情绪化的文字也是我灵光一闪的思考结果，并不是完全没有价值的，也应当在我的博客中占有一席之地，故将这些文字保留下来，以便日后审视。 一 人是很矛盾的动物 人是很矛盾的动物。人总是可以找到一方土地来安置自己的身体，却很难找到一种令人满意的方式来安顿自己的心灵。 有的人深居简出，在屋檐下享受着宁静的生活；有的人在格子间里埋头苦干，为了生计或事业潜心奋斗；有的人则永远在路上，寻访名山大川和名胜古迹——虽然许多人事实上并没能生活在最适合自己的物理环境中，但找到这样的环境总是可行的。 我们一边想要让自己的心灵走出囚笼，一边又渴望为自己的心灵找一个归宿；一边在喧闹的人群中渴望独处，一边又在孤身一人时向往他人的关..
更多P5150 生日礼物 题解
虽然题目不难，但背后蕴含的考点还是很有意思的。 本题的核心考点是唯一分解定理。 此考点曾在NOIP中涉及，非常重要！！！ 例如 NOIP2009 Hankson的趣味题 唯一分解定理：设 pip_ipi 表示第 iii 个质数，那么对于任意正整数NNN，都有唯一的一组 a1,a2,a3…ana_1,a_2,a_3\dots a_na1,a2,a3…an ，使得 N=p1a1×p2a2×p3a3×⋯×pnanN=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}\times\dots\times p_n^{a_n} N=p1a1×p2a2×p3a3×⋯×pnan 其中 aia_iai 可以等于000。 用白话文说：任何数都可以表示为他的质因数们的若..
更多
P2272 [ZJOI2007]最大半连通子图 题解
本题解相对于其他题解的特色有二： 一、深入分析了为什么要去重 二、给出了链式前项星的 O(m)O(m)O(m) 线性去重方式 下面进入正文。 不难发现，将原图缩点成一个DAG后，图中的每一条链都是一个半连通子图，而最长的链就是最大半连通子图。 注意：新图中一个点的权值为这个点代表的SCC的点数，一个链的长度为各点权值之和。 统计最长链的权值不难，可以使用拓扑排序或记搜实现。为了避免引入STL影响效率，本文统一使用记搜。 本题的难点在统计方案数。 统计最小生成树方案数、最短路方案数等经典题的解法会给我们启示，紧紧抓住三角不等式这一核心算式，不断更新答案并继承方案数，这种方法依然使用本题。 但有所不同的是，本题需要考虑重边。 认真思考不难发现，传统的 tarjan 缩点得到的DAG中会出现重边（这里的重边是..
更多通信基站覆盖问题 题解
本题来自于某次付费答疑，经本人后续查证，题目出自印度德里理工学院的一次期中考试。 题面 Let us consider a long, quiet country road with houses scattered very sparsely along it. (We can picture the road as a long line segment, with an eastern endpoint and a western endpoint.) Further, let’s suppose the residents of all these houses are avid cell phone users. You want to place cell phone base station..
更多P8458 「REOI-p1」打捞 题解
如果将所有数列都扩展到 kkk 的长度， 1e91e91e9 级别的数组肯定会时间空间双爆炸。 所以这个题要利用周期性。 不难发现，两个数列的最小正周期为 lcm(li,lj){\rm lcm}(l_i,l_j)lcm(li,lj) ， 我们真正需要处理的是在这个最小正周期内的交叉积。 尽管如此，若 li,ljl_i,l_jli,lj 都是质数，他们的最小正周期也可以很长很长。遍历最小正周期求交叉积依然无法AC。 通过分析那 60%60\%60% 的数据我们可以发现，若 li,ljl_i,ljli,lj 互质，那么，在一个最小正周期中， aia_iai 中的每一个元素，都把 aja_jaj 中的每一个元素乘了 111 次，而且只乘了 111 次。那么我们可以利用分配律，得 ∑aiaj=∑(ai..
更多