【笔记】映射方法在几何计数中的应用

Posted on

作者:余不悔,高二,2018 年 CMO 铜牌获得者。 对于两个有限集合 $A$ 和 $B$,如果存在一个一一映射:$f:A \rightarrow B $,那么就有 $|A|=|B|$。 在某些情况下,如果 $A$ 的元素个数不好求,那么我们可以寻找一个集合 $B$,并建立起 $A$ 到 $B$ 的一个一一映射,然后去计算集合 $B$ 的元素个数,从而将问题解决。在这个过程中,寻找到容易计算元素个数的集合 $B$ 是至关重要的一步。 譬如下面这个大家都很熟悉的例子: 在 $6 \times 6$ 的方格表中,从左下角的 $A$ 点到右上角的 $B$ 点沿方格表的最短路径有多少条? 容易发现,从 $A$ 点到 $B$ 点的最短路径中,全部由 “向上” 和 “向右” 的线段组成,且各有六条。因此,我们建立起集合 $B$,定义它包含 “在 12 条线段中,选择 6 条作为向上线段的方法”。这样,对每一个确定的 $B$ 的元素,都可以唯一对应一种 $A$ 的方法,而对于 $A$ 的每一种方法都可以唯一的生成一个 […]

【笔记】动态 DP

Posted on

这个算法的名字好毒瘤的样子。。。Dynamically Dynamical Programming,动态 – 动态规划,简称 DDP。 我们先考虑简单的动态规划。有一个经典问题叫做树上最大权独立集。比如 没有上司的舞会。 那么我们可以设 $f_{u,1}$ 为 $u$ 在独立集内的最大收益,$f_{u,0}$ 为 $u$ 不在独立集内的最大收益。转移方程如下: $$f_{u,1}=\sum_{v\in son}f_{v,0}$$ $$f_{u,1}=\sum_{v\in son}\max (f_{v,0},f_{v,1})$$ 现在我们要支持的操作是动态修改某个点的权值,比如 洛谷模板。 为了快速维护,我们先对整棵树做一个树剖,然后对每一条重链分别进行 dp。 对于重链上的每个点,先根据轻儿子的 $f$ 维护 $g_{u,1/0}$: $$g_{u,0}=\sum_{v\in lightson}\max(f_{v,0},f_{v,1})$$ $$g_{u,1}=\sum_{v\in lightson} f_{v,0}$$ 对于重链上的点,则有: $$f_{u,0}=g_{u,0}+\max(f_{heavyson,0},f_{heavyson,1})$$ $$f_{u,1}=g_{u,1}+f_{heavyson,0}$$ 这样,树上的问题就转化成了序列上的问题。我们可以对于每条重链维护一颗线段树。修改一个点的值就在这个点所在重链的线段树上修改,最后改变了重链顶端的点的 $f$ 值,进而影响了其父亲的 $g$ 值,反复向上修改,时间复杂度就是 $\Theta(log^2n)$ 的。 问题来了,如何用线段树维护 $f$ 呢。我们重新定义矩阵乘法。对于 $C=A\times B$,有 $$C_{i,j}=\max\limits_{k=1}^{n}(A_{i,k}+B_{k,j})$$ 于是,重链上的转移可以写成这样的矩乘 $${\left[ \begin{array}{cc}g_{i,0} &g_{i,0}\\ g_{i,1} […]

【笔记】关于 KMP

Posted on

考前记忆模板。 我们回忆一下 $next$ 数组的含义: $next[i]$ 表示在 $[1,i-1]$ 内,前缀与后缀相同的部分最长是多长。可以理解为,若第 $i$ 位失配了,至少要往前跳多少步,才可能重新匹配得上。 于是对于匹配串,预处理出它的 $next$ 数组,然后对文本串逐位匹配即可。

后记 不知道为什么我内心一直觉得 NOIp 会考这个算法。。。说不定被我奶中了呢。。。

【Tips】NOIp 防翻车指北

Posted on

写代码时请注意: 是否要开 long long?数组边界处理好了么? 实数精度有没有处理? 特殊情况处理好了么? 数组是否足够或者过大? 做一些总比不做好。 当你把你的暴力程序改成正解时,记得扩大数组。 思考提醒: 最大值和最小值问题可不可以用二分答案? 有没有贪心策略?否则能不能 dp? 考场调整: 写下代码前,必须保证有充足的思考时间,有成熟的想法后再动手; 写代码前,尽量用多而强的数据去测试想到的算法,毕竟代码写完后再测试就浪费很多时间了; 不能想一点写一点,就算是输入部分也要在整体思路理清后再写; 永远别去写从未接触过的算法/数据结构; 有多余时间可以尝试进行对拍,即 3 个程序:生成数据、朴素算法(暴力算法)、准备交的算法; 如果你发现你旁边的人写得很快,请你放心,他的算法十有八九是错的,神仙没有你想象中那么多; 交之前 5 分钟千万不要再改动代码,主要留意代码中是否还有测试程序时留下的痕迹; 走出考场后,除非已经是 Day 2,永远别对答案。 其他注意事项 作者:lornd

【杂谈】尝试签约视觉中国

Posted on

(10/12)UPDATE 意料之中… 这是我的 500px 主页 众所周知,我是一个能力低下设备糟糕的摄影爱好者,擅长拍废片和烂片。 我花了一年多的时间凑齐了二十张稍微能看的照片,在 2018年10月7日提交了审核,结果会在 3~4个工作日里出来。现在先把这些照片放出来污染一下读者的眼睛。 (懒得再传一遍了你们直接去 500px 看吧顺便点个赞什么的) 这里只放我个人最喜欢的几张: 摄于 Nikon D7100 摄于 SONY Xperia X 摄于 Nokia 7

【大坑】网络流 24 题集合

Posted on

在看题之前。。。 感谢前辈写出的优秀论文。 部分资源分享(持续更新中) 序号 标题 备注 题解 1 飞行员配对方案问题 最大匹配 裸题 2 太空飞行计划问题 最大权闭合子图 / (最小割) 建模SSL_XXY_BlackCloud 3 最小路径覆盖问题 最小路径覆盖(废话) 参考部落战争 4 魔术球问题 (贪心可做) 代码 5 圆桌问题 多重匹配(奇水无比) 代码 6 最长递增子序列问题 分层图 / 最大流 7 试题库问题 二分图匹配 8 机器人路径规划问题 听说最优解不是网络流 9 方格取数问题 最大点权独立集 10 餐巾计划问题 最小费用最大流 11 航空路线问题 最大费用最大流 12 软件补丁问题 最小转移代价 13 星际转移问题 分层图最大流 […]