《计算机安全导论——深度实践》中第四章的学习笔记。介绍了缓冲区溢出攻击等知识，持续更新中。
阅读更多设计机器指令，并编写相应的微程序，上机调试，掌握计算机整机概念。掌握微程序的设计方法，学会编写二进制微指令代码表，全面了解并掌握微程序控制方式计算机的设计方法。
阅读更多实现插入排序（Insertion Sort，IS），自顶向下归并排序（Top-down Mergesort，TDM），自底向上归并排序（Bottom-up Mergesort，BUM），随机快速排序（Random Quicksort，RQ），Dijkstra 3-路划分快速排序（Quicksort with Dijkstra 3-way Partition，QD3P）。
阅读更多使用并查集(union-find)数据结构，编写程序通过蒙特卡罗模拟(Monte Carlo simulation)来估计渗透阈值。
阅读更多title: 终于结束的起点——CSP-S 2019 第二轮游记
mathjax: true
toc: true
top: false
tags: []
excerpt: >-
Day -3 在教练和自己的劝说下，终于还是选择最后几天停课，专心复习，全力以赴。 Day -2
上午一直在复习数论知识，中午睡了个午觉，起来后身体就很难受了。 晚上就直接请假回家睡觉。感觉发烧了，一测，39度左右。感觉药丸。 Day -1
早上去医院检查，细菌性感染，开了一些奇奇怪怪的药，整个一天
date: 2019-11-15 08:11:00
categories: 随笔
本校大三课程「离散数学」的同步笔记，已更新「6.1 代数结构」，「6.2 子代数」，「6.3」同态，「6.4」同余，「6.5」商代数，「6.6 半群与独异点」，「6.7 群」，「7.1 格与布尔代数」（更新中）。
阅读更多前言
这个问题在高中生物中，并不会研究的那么深刻。
所以正式做题时还是应该按照老师的教导，避开这个“雷区”。
1.问题发现
在高中生物-遗传与进化-基因的本质学习中，有一个十分经典的问题。
即：给定碱基对数n，不限定每种碱基(A,C,G,T)的个数，求出最多的DNA种数。
在所有的教材，辅导书，以及老师的授课过程中，对于这个问题的答案，一般都是$4^{n}$或者$ \frac {4^n} {2}$。
对于$4^n$的思路，即每个位置有$4$种碱基对可能，一共有$n$组，根据乘法原理，故为$4^{n}$。
对于$\frac {4^n} {2}$的思路，即在上一种思路的基础上，考虑到有重复的情况，便除了个2。
但是，@thorn,@opethrax以及本人的对于这些答案深感怀疑，于是我们便手算了当碱基对数为$2$时的所有情况。
利用计算机程序进行打表，以及查询有关$DNA$的资料后，最终我们确定当n=2时，结果理应为10。
这个答案都不能用上面的公式解答，于是我们继续思考探索。
2.深入探究
通过@opethrax同学辛苦的打表，观察，他发现存在一些情况被忽略。
原先我们认为，一个$DNA$分子拥有$3’$与$5’$段，$3$代表三号碳，$5$代表五号碳。
如下图，从两条链的$3’$端分别扫描，一种序列最多被统计到$2$次。
一个是AGCTA，另一种是TAGCT。
但是，存在一种$DNA$分子，从其两条链的$3’$端分别扫描，结果相同。
如下图：
都为TCGATCGA。
所以这种情况下，具有这种性质的$DNA$会被少统计一次。
且我们不难发现，满足这种性质当且仅当$DNA$链的长度为偶数（如图一，若为奇数，会出现不对称的情况，即不满足这种性质）。
那么我们分类讨论，之前那个$\frac {4^n} {2}$的公式，可以在n为奇数时使用。
对于n为偶数的情况，我们要在原公式的基础上，加上少统计的个数。
现在的问题，即是寻找拥有这种特殊性质的链的个数。
不难发现，一条链的$3’$端的$1$号碱基到该链的第$\frac n 2$号碱基，如果和另一条链的$3’$端的$1$号碱基到该链的第$\frac n 2$号碱基相同，剩下的部分通过碱基互补配对原则，可以保证相同。
下图黑的部分是我们自己确定的一条排列，红色部分是根据碱基互补配对原则形成的。
我们可以把这个理解为一种中心对称。
所以我们只需要构造出一条链中一半的排列，然后按照中心对称放到另一条链的$3’$端，剩下那条按照碱基互补配对原则填充即可满足这种性质。
所以我们不难得出，这种情况下，会有$4^{\frac {n}{2}}$条链会被少统计一次。
至此，我们可以得出公式：
$$
a_n=\begin{cases}\frac{4^n}{2}\ \ \ \ \ \ \ \ n=2k+1\\frac{4^n+4^{\frac{n}{2}}}{2}\ n=2k\ \ (k\in N^*)\end{cases}
$$
这个式子经过打表以及oeis.org的确认，结果正确。
3.声明与感谢
其实$DNA$的结构远比人类脑海中想象的要复杂的多，这里我们只是讨论了理论下的情况。
感谢您的阅读。若您存在任何疑问，或觉得我们有些地方存在纰漏，欢迎您联系我们，我们十分乐意与您探讨。
再次感谢两位同学@thorn,@opethrax深夜的探讨与陪伴，若没有他们的帮助，我们很难单独进行下去。
thorn有关这篇文章的链接：https://www.cnblogs.com/thornblog/p/12381381.html
opethrax有关这篇文章的链接：https://home.cnblogs.com/u/opethrax/
他们两位有关这个内容的博客写的都非常优秀，建议您去访问他们的博客以进行更多的了解。
除非另有说明，本网站上的内容均采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可，请您在转载时注明来源及博客链接。
4.深夜随想
造物主强大的力量是人们无法想象到的。人类很难走到没有任何疑惑的那一天。
每一个个体脑中冒出的新奇想法，或提出的一个问题，都有可能成为筑起人类从无知到有知的桥梁下的一粒石子。
对科学的探索，不是浅尝辄止，而是无穷无尽。
献上一首不错的音乐：
“生于此处却不知此处
日光倾城，万物生长，又是为何
若没有大地的拥抱，我们早已消失于茫茫宇宙之中
若没有原子之稳定，我们亦不复存在
无人问天地变换，斗转星移，是为何故
宇宙又是源于何处
它是否无始无终
时间若愿意倒流，我们的认知是否还会有局限
世间最渺小之物又是什么
滚滚长江，却只留有过去，不知未来
浩淼宇宙，为何我们在此相遇”
——《Moonlight》
形式
$$
\sum_{i=1}^{n}a_i^2 \sum_{i=1}^{n}b_i^2 \geq \sum_{i=1}^{n}a_i^{2}b_i^2
$$
等号成立的条件：
$$
iff:b_i=0 || \exists k \in \mathbb {R},a_i=k \cdot b_i(i \in \mathbb{N^+})
$$
证明
法一：参数配方
思路：巧妙的把常数与方程结合起来，利用性质即可。
证明：
构造函数:
$$
f(t)=\sum_{i=1}^{n}b_i^2\cdot t^2-2\sum_{i=1}^{n}a_ib_it+\sum_{i=1}^{n}a_i^2
$$
化简函数：
$$
f(t)=\sum_{i=1}^{n}b_i^2\cdot t^2-2\sum_{i=1}^{n}a_ib_it+\sum_{i=1}^{n}a_i^2
$$
$$
=\sum_{i=1}^{n}(b_i^2t^2-2a_ib_it+a_i^2)
$$
$$
=\sum_{i=1}^{n}(b_i^2t^2+a_i^2-2a_ib_it)
$$
$$
=\sum_{i=1}^{n}(b_it-a_i)^2
$$
所以：
$$
f(t) \geq 0
$$
$$
\Delta t=b^2-4ac
$$
$$
=4\sum_{i=1}^{n}a_i^2b_i^2-4\times \sum_{i=1}^{n}b_i^2 \times \sum_{i=1}^{n}a_i^2 \leq 0
$$
所以：
$$
4\sum_{i=1}^{n}a_i^2b_i^2 \leq 4\times \sum_{i=1}^{n}b_i^2 \times \sum_{i=1}^{n}a_i^2
$$
$$
\sum_{i=1}^{n}a_i^2 \times \sum_{i=1}^{n}b_i^2 \geq \sum_{i=1}^{n}a_i^2b_i^2
$$
证毕。
因为：
$$
f(t)=\sum_{i=1}^{n}(b_it-a_i)^2
$$
令$f(t)=0$，即
$$
a_i=b_it
$$
此时：
$$
f(t)_{min}=0
$$
即：
$$
\Delta t \leq 0
$$
故等号可取的一个充分条件即为：
$$
\exists k \in \mathbb {R},a_i=k \cdot b_i(i \in \mathbb{N^+}）
$$
法二：均值不等式证明
思路：运用分析法将原式子化简，使用绝对值三角不等式与均值不等式进行证明。
引用到的均值不等式（证明略）：
$$
ab \leq \frac{a^2+b^2}{2}
$$
适用条件：
$$
a,b \in \mathbb {R^+}
$$
等号成立条件：
$$
iff:a=b
$$
证明：
要证：
$$
\sum_{i=1}^{n}a_i^2\sum_{i=1}^{n}b_i^2 \geq \sum_{i=1}^{n}a_i^{2}b_i^2
$$
只需证：
$$
\sqrt {\sum_{i=1}^{n}a_i^2 \sum_{i=1}^{n}b_i^2} \geq |\sum_{i=1}^{n}a_ib_i|
$$
即：
$$
|\sum_{i=1}^{n}a_ib_i| \leq \sqrt {\sum_{i=1}^{n}a_i^2 \sum_{i=1}^{n}b_i^2}
$$
$$
\frac{|\sum_{i=1}^{n}a_ib_i|}{\sqrt {\sum_{i=1}^{n}a_i^2 \sum_{i=1}^{n}b_i^2}}\leq 1
$$
由绝对值三角不等式：
$$
|a_1+a_2+a_3+\cdots+a_n| \leq |a_1|+|a_2|+|a_3|+ \cdots + |a_n|
$$
可得：
$$
|\sum_{i=1}^{n}a_ib_i| \leq \sum_{i=1}^{n}|a_ib_i|
$$
所以：
$$
\frac{|\sum_{i=1}^{n}a_ib_i|}{\sqrt {\sum_{i=1}^{n}a_i^2 \sum_{i=1}^{n}b_i^2}} \leq \frac{\sum_{i=1}^{n}|a_ib_i|}{\sqrt {\sum_{i=1}^{n}a_i^2 \sum_{i=1}^{n}b_i^2}}
$$
又因为：
$$
\frac{\sum_{i=1}^{n}|a_ib_i|}{\sqrt {\sum_{i=1}^{n}a_i^2 \sum_{i=1}^{n}b_i^2}}
$$
$$
=\sum_{i=1}^{n}\frac{|a_i|}{\sqrt{\sum_{i=1}^{n}a_i^2}}\cdot \frac{|b_i|}{\sqrt{\sum_{i=1}^{n}b_i^2}}
$$
由均值不等式：
$$
ab \leq \frac{a^2+b^2}{2}
$$
可得：
$$
\sum_{i=1}^{n}\frac{|a_i|}{\sqrt{\sum_{i=1}^{n}a_i^2}}\cdot \frac{|b_i|}{\sqrt{\sum_{i=1}^{n}b_i^2}}
$$
$$
\leq \frac{1}{2}\cdot \sum_{i=1}^{n}(\frac{a_i^2}{\sum_{i=1}^{n}a_i^2}+ \frac{b_i^2}{\sum_{i=1}^{n}b_i^2})
$$
$$
\leq \frac{1}{2}\cdot (\frac{\sum_{i=1}^{n}a_i^2}{\sum_{i=1}^{n}a_i^2}+ \frac{\sum_{i=1}^{n}b_i^2}{\sum_{i=1}^{n}b_i^2})
$$
$$
\leq \frac{1}{2} \times 2 = 1
$$
即：
$$
\frac{|\sum_{i=1}^{n}a_ib_i|}{\sqrt {\sum_{i=1}^{n}a_i^2 \sum_{i=1}^{n}b_i^2}}\leq 1
$$
上述结论成立，证毕。
法三：n维向量证法
因为：
$$
|\vec a \cdot \vec b| = |\vec a|\cdot |\vec b| \cdot cos \theta
$$
所以：
$$
|\vec a \cdot \vec b| \leq |\vec a|\cdot |\vec b|
$$
$$
|\vec a \cdot \vec b|^2 \leq |\vec a|^2\cdot |\vec b|^2
$$
$\vec a,\vec b$为$n$维向量时，用坐标的形式展开即可证明。
当$\vec a=k\vec b$，即$a$，$b$共线时，等号成立。
申明与感谢
- 内容采用“知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议”进行许可。请您在转载时注明来源及链接。
- 感谢@thorn的审稿。
Day -1
早上学校有两节英语两节语文，就翘掉了。
在家里把$XJOI$的开放试卷做完了，$68.5$，成绩不算很好。
听说这次参赛的水军都没了，复赛可能会很难进，感觉自己心态还可以。
下午围观了有趣的四川选手名单，被四川的操作震惊，看来我们还是太$naive$了…
还做了$51nod$的试题，题挺难的，写完后心态大崩
Day 0
又请了前三节课的假，把初赛篇的基本知识全过了一遍，感觉还不错。
还把$51nod$的题的题解全看了一遍（upd：事实证明这是正确的做法，因为在真正考试中见到了不少原题）
晚上在机房和$lx$一起又把初赛的基础知识全过了一遍，膜拜$lx$的数学能力
还和$misaka$研究了许久的主定理（upd：第二天居然没有考…）
很早就睡了，也没有考前欢乐。
Day 1
好冷啊。
早上8：50就到了，科协的人居然还没有布置考场（太咕了，昨天晚上科协的人忙着印卷子居然让我们自己去准备考场相关事宜，贴条子）。
遇见了许久不见的$spinmry$，还有其他原来认识的人。
9：20进考场，惊奇的发现$zyhh$居然就做我左边，座位还是挨着的，但今年是$AB$卷，所以不担心答案。
但最后我们还是被分开了。。。
再一次吐槽科协的奇妙操作：
1.监考老师说：你们要是没有草稿纸，可以向周围人借。
（啥？去年不是还考过选择题说不能带草稿纸吗？）
2.监考老师说：分赛区填新疆。
（啥？那省份填全国吗？）
3.监考老师说：不能提前交卷。
（啥？这又是什么规定？提前阿克的人不能离场吗？（这里指的不是我））
最后全部打脸。
看到卷子，感觉题量挺大。
看选择题，做起来都不是很难，居然还有原题。
遇见了一些有趣的数学题，便先放下然后去想后面的题去了。
阅读程序，前两道题都是属于看一眼就知道在干嘛的题，但是判断题当时做起来有点懵。
第三题没怎么看懂，自己造了两组数据模拟了一下，成功解决了判断题，最后两道选择题就蒙了起来。
完善程序，第一题比较简单。
第二题耗了我将近$40mins$的时间，一直没看懂，到最后也是。
交完卷子后便去上物理课去了。
中午回到机房，答案出来了，便开始对。
选择错一道，是那道车牌数学题。
阅读程序第一题判断有个错了。
第二题错了一道选择一道判断，是真的坑题。
当我看到算法复杂度时，我就直接选择了$O(nlogn)$，但是完全没有注意到，这并查集居然没有路径压缩（这什么辣鸡啊
还有第四道判断题，当点$x$与$y$所在连通块相同时，那么他们相乘后的结果显然会$\geq n$。
第三题据说$cin$不能读空子串，就很生草。
完善程序最后一道就对了$3$个。。。
最后估分77分，在机房人里面排中等吧。
晚上和yyy还有jmh点了三个小菜，在水房边吃边聊，聊一些往昔与来者。
总结：
自己的$dp$功底还是不行，对于状压这种东西，还是得多钻研啊。不能知难而退。
平时心态方面也要放好一点啊。
复赛应该能进，剩下的时光，就留给月考和复赛的训练了吧。
乾坤未定，谁都是匹黑马。
各位加油鸭！
（ps：%yyy %jmh