> 作者：余不悔，高二，2018 年 CMO 铜牌获得者。 对于两个有限集合 $A$ 和 $B$，如果存在一个一一映射：$f:A \rightarrow B $，那么就有 $|A|=|B|$。 在某些情况下，如果 $A$ 的元素个数不好求，那么我们可以寻找一个集合 $B$，并建立起 $A$ 到 $B$ 的一个一一映射，然后去计算集合 $B$ 的元素个数，从而将问题解决。在这个过程中，寻找到容易计算元素个数的集合 $B$ 是至关重要的一步。 譬如下面这个大家都很熟悉的例子： 在 $6 \times 6$ 的方格表中，从左下角的 $A$ 点到右上角的 $B$ 点沿方格表的最短路径有多少条？ 容易发现，…
这个算法的名字好毒瘤的样子。。。Dynamically Dynamical Programming，动态 – 动态规划，简称 DDP。 我们先考虑简单的动态规划。有一个经典问题叫做树上最大权独立集。比如 没有上司的舞会 [https://www.luogu.org/problemnew/show/P1352]。 那么我们可以设 $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}…
2014年3月1号，崔永元先生公布了自费 100 万元拍摄的赴美考察转基因纪录片，片长 68 分钟 28 秒。我们先可以回顾一下它。 现在是 2018年11月。时隔四年多，这部纪录片里提出的观点还有多少可挖掘的价值？我将从头开始分析一下视频的主要内容，希望给读者带来更多的思考。 为了方便部分读者阅读，先把结论复制到前面， > 和崔永元的结语一样，我要强调，这只是一部调查纪实。这次调查从一个反对转基因者的角度出发，未免有一些不够公正，或者完全客观的地方。总是发生在有机超市的采访，疑似被剪辑的讲座，以及有时出错的翻译都不够公正客观。 所以，它不是一部科普宣传片。它反映的是美国不同身份、不同级别、不同知识水平的人对转基因的理解。我们可以看到，美国民众和中国民众一样，对 GMO 不甚了解，或者保持二元论的观点；美国农民对转基因的理解也停留在表面，仍有相当多的人不顾成本地坚守自己有机种植的情怀；政府官员以及科学工作者，在一些基本事实上仍存在分歧，但是在访谈的最后，他们依旧对转基因的未来提出了相对积极和正面的期许。 这个视频中大部分的，可能的事实错误，我都拿出了相对权威的资料进行了一…
> 首先，这篇文章的写作时间开始于 1:59 PM，11/10/2018，NOIP 2018 提高组比赛结束的两小时之后。 Day 1 -------------------------------------------------------------------------------- 考试前感冒了，考试的时候整个考场的人一直在听我打喷嚏，抱歉。如果和我同考场的同学考炸了，我的错。 题目好像是 8:29 就下发了，我迅速用 Chrome 打开题面 PDF，三道题完整地扫了一遍，都有一种彷佛从前遇见过的，莫名的熟悉感，但当时想不到究竟有没有看过原题。 于是就从第一道题开始吧。 首先想到的方法是每个高度分别处理出有多少联通块，最后的答案就是每个高度联通块个数之和。我用了一个 $pos$ 数组记录每个高度上一次出现的位置，然后每加入一个高度都要 $\Theta (d_i)$ 地更新一遍 $pos$ 数组，总的时间复杂度 $\Theta(\sum{d_i})$。写完以后测了大样例，…
考前记忆模板。 我们回忆一下 $next$ 数组的含义： $next[i]$ 表示在 $[1,i-1]$ 内，前缀与后缀相同的部分最长是多长。可以理解为，若第 $i$ 位失配了，至少要往前跳多少步，才可能重新匹配得上。 于是对于匹配串，预处理出它的 $next$ 数组，然后对文本串逐位匹配即可。 #include #define maxn 1000001 char p[maxn],t[maxn]; int next[maxn],n,m; int main(){ scanf("%s%s",p+1,t+1); n=strlen(p+1),m=…
写代码时请注意： 1. 是否要开 long long？数组边界处理好了么？ 2. 实数精度有没有处理？ 3. 特殊情况处理好了么？ 4. 数组是否足够或者过大？ 5. 做一些总比不做好。 6. 当你把你的暴力程序改成正解时，记得扩大数组。 思考提醒： 1. 最大值和最小值问题可不可以用二分答案？ 2. 有没有贪心策略？否则能不能 dp？ 考场调整： 1. 写下代码前，必须保证有充足的思考时间，有成熟的想法后再动手； 2. 写代码前，尽量用多而强的数据去测试想到的算法，毕竟代码写完后再测试就浪费很多时间了； 3. 不能想一点写一点，就算是输入部分也要在整体思路理清后再写； 4. 永远别去写从未接触过的算法/数据结构； 5. 有多余时间可以尝试进行对拍，即 3 个程序：生成数据、朴素算法（暴力算法）、准备交的算法； 6. 如果你发现你旁边的人写得很快，…
（10/12）UPDATE 意料之中… 这是我的 500px 主页 [https://500px.me/xgzepto] 众所周知，我是一个能力低下设备糟糕的摄影爱好者，擅长拍废片和烂片。 我花了一年多的时间凑齐了二十张稍微能看的照片，在 2018年10月7日提交了审核，结果会在 3~4个工作日里出来。现在先把这些照片放出来污染一下读者的眼睛。 （懒得再传一遍了你们直接去 500px 看吧顺便点个赞什么的） 这里只放我个人最喜欢的几张： > 摄于 Nikon D7100 > 摄于 SONY Xperia X > 摄于 Nokia 7…
在看题之前。。。 感谢前辈写出的优秀论文。 部分资源分享（持续更新中） [https://cloud.xgzepto.cn/index.php/s/5tzCDqxspzLak9m] 序号标题备注题解1飞行员配对方案问题 [https://www.luogu.org/problemnew/show/P2756]最大匹配裸题2太空飞行计划问题 [https://www.luogu.org/problemnew/show/P2762]最大权闭合子图 / （最小割）建模 SSL_XXY_BlackCloud [https://cdn.luogu.org/upload/pic/21712.png]3最小路径覆盖问题 [https://www.luogu.org/problemnew/show/P2764]…