周弈帆的博客
0%

Posted on In ,

第一章 概率论基本概念

1.随机试验

世界上，没有两片相同的叶子。在没有时间倒流的情况下，严格上来讲，我们无法在完全一样的条件下做同一件事情。

然而，由于生活中许多事情的性质相同，我们在不同时间重复做这一件事，可以看成是在一个时间多次做这件事产生了多个结果。

而随机试验则是可以在相同条件下重复进行、结果不定、不可预知的试验。

这一小节很水，我们赶快把它跳过。

2.样本空间、随机事件

这一小节的讨论全部是基于集合的。

我们把一个试验的结果用集合表示，这个集合被赋予了高贵的名字：样本空间，记为$S$。$S$中的子集也有了别名，叫事件。空集叫不可能事件，全集叫必然事件，单个元素的集合叫做基本事件。事件就是集合，你可以做 $\bigcup \bigcap \subset - =$等基本运算。由于有全集，你还可以做补运算，结果等价于用全集减该集合。

集合有一堆运算律，比如德摩根律。这些东西应该是集合论讲的，这里就不复习了，考试也不会考。事实上，集合定律不用特别去记，集合定律和逻辑运算定律基本一样，而后者广泛存在于我们在生活中的一些思维方式里。

特别的，两个交为空的事件互为互不相容事件，并集是全集的互不相容事件叫做对立事件。

这一小节我们取了很多名字。但是这些名字记不住也没关系，因为这些名字非常容易从字面上理解它们的定义。快进入下一节吧。

3.频率与概率

为什么要学概率呢？明明结果不可预知啊！

恰恰相反，正是因为结果不可预知，我们才需要学习概率，掌握事情发生背后的规律，从而更好地掌控随机事件。

概率有用的证据就是，无数次重复同一随机试验后，试验结果会十分接近其概率。

那概率是什么呢？概率就是个0~1的数。你硬要把它规定成0~10000里的数也可以，但没什么意义，因为概率是一个相对的概念——相对于样本空间这个全集而言。我们强行做了一个集合到数的映射，这个数越靠近1，表示它越接近必然事件，越可能发生。

要定义概率，就要对「集合到数」这个函数做一些规定。对于集合函数$P$，任意事件$A$，$P(A)\geq0$；$p(S)=1$,其中$S$为样本空间；任意个彼此互不相容事件之并的函数值是每个事件函数值之和。满足了这三个条件，概率的一切东西都可以推出来了。

考试与生活的应用中肯定不会取管定义。我们这里只注意概率的一个有用的性质：$P(A\bigcup B)=P(A) + P(B) - P(AB)$。这个性质由容斥原理而来，不仅概率函数P满足这个式子。第一章出的题目应该都会围绕这个式子出。两个事件各自的概率、两个事件并与交的概率，知道其中3个就可以推出剩下的。

例题：设$A，B，C$是三个事件,$P(A) = P(B) = P(C) = 1/4， P(AB) = P(BC) = 0, P(AC) = 1/8$， 求$A,B,C$至少有一个发生的概率。

解：
最后一句中文太不和谐了，把它转换成数学语言：求$P(A+B+C)$

由容斥原理,$P(A+B+C) = P(A) + P(B) + P(C) - P(AB) - P(AC) + P(ABC)$

$\because ABC\subset AB$

$\therefore P(ABC) \leq P(AB)$

$\because P(AB) = 0$

$\therefore P(ABC) = 0$

$\therefore P(A+B+C) = 1/4 + 1/4 + 1/4 - 1/8 = 5/8$

这题太水了，下一节。

4.古典概型

生活中最常见的概率模型是：事件由有限个基本事件组成，基本事件概率相同。比如一百个人抽签，每个人抽中的概率就是1%。如果其中有二十个人是我派过去的抽签小队，那么这个签被二十个人中某个人抽中的概率就是20%。这个概率模型非常容易理解。

换个角度来看，求概率问题就变成了计数问题。计算出所有基本事件的个数，这个数就是所有概率的分母。再计算出你要求的事件包含的基本事件数，把这个数作为分子。最终就可以计算出概率。

这一小节理论上属于组合数学的范畴了，不太像概率论。但考试还是会考，我们还得复习。只要有高中的排列组合基础，这一小节就基本不用学了。看几道水题：

例4.1：
从1~10中随机挑3个数，求：
（1）最小数为5的概率
（2）最大数为5的概率

解：

$(1) C(5, 2) / C(10, 3) = 10 / 120 = 1 / 12$
$(2) C(4, 2) / C(10, 3) = 6 / 120 = 1 / 20$

例4.2：
五双鞋子，随机取4只，求至少配成一双的概率

解：

不妨求出配不成一双的概率，再求其对立事件。

$P(至少配成一双) = 1-P(配不出一双) = 1 - C(5, 4)\times2^4 / C(10, 4) = 1 - 80 / 210 = 13/21$

5.条件概率

条件概率又是一个生活中常出现的概念。当一个事件极其复杂时，我们只能下一个大致的判断；但当你掌握的信息越来越多时，你之前下的判断的概率会越来越大。比如你掷两次骰子，你说你可以丢2次6出来，这个概率仅仅是1/36。当你第一次丢完，已经丢出了一个6后，你成功的概率就变成了1/6。

从整体的角度来看，条件概率就是知道了某些条件后，原来的样本空间缩小了。满足这个条件的事件，它自己包含的基本事件不变，而整个样本空间又缩小，它发生的概率也会随之变大。

设A，B为两个事件，$P(A) > 0,P(B|A) = \frac{P(AB)}{P(B)}$称为A发生的条件下B发生的条件概率。

这个定义不是特别直观，因为我们在生活中用的一般是条件概率的性质——乘法原理，即$P(AB) = P(A | B) \times P(B)$。

比如，对面有3个怪和一个英雄，其中一个怪的效果是，你的英雄获得免疫。现在你可以造成两次无穷大的伤害，但是目标随机选定。求对面英雄死亡概率。我们通过直觉去考虑，我们要杀死对面英雄，必须要先杀死对面的特殊怪。杀死特殊怪的概率是1/4,在杀死特殊怪的条件下，杀死英雄的概率是1/3。所以杀死对面英雄的概率是$1/4\times1/3=1/12$.

条件概率还有一些重要应用，比如全概率公式。设$B_1,B_2…B_n$互不相容，且并集为全集，则$P(A) = \sum_{i = 1}^nP(A|B_i)P(B_i)$。

换句话说，某件事的概率不好求，我们只能在知道一些条件后才能确定该事件的概率。这个时候，我们要算无遗策，把所有下一步的情况考虑了，再算出每一个下一情况下，我们要求的事件的概率。最后乘一下，求个和。不过比较常见的是，我们下一步情况只有两种，因此我们只要算出下一个事件和其对立事件下，我们最后要求的事件的概率。我描述得比较抽象，不妨看一道例题：

例5.1：

甲袋中n白球m红球，乙袋中N白球M红球。从甲袋中取一个放到乙袋中，再从乙袋中取一个球。问取到的这个球是白球的概率。

解：

我们必须讨论一下从甲袋中取出的是什么，才好确定从乙袋中取白球的概率。

从这里也可以看出，条件概率和全概率公式是十分符合我们生活中的思维方式的。

全概率公式加上条件概率定义可以组合出一个很厉害的公式——贝叶斯公式：

这个公式乍一眼看很复杂，但仔细观察后发现，等式右边分子就是$P(AB_i)$,分母就是$P(A)$。这个式子给我们的直观感受是：我不知道B在A情况下发生的概率，但我知道A在B情况下发生的概率，那我再知道一些关于事件A发生的信息就可以求出B在A情况下发生的概率了。

这个公式在生活也是非常实用的，通过它或许可以得到一些反直觉的结论。这也是数学的奇妙之处：源于生活中的直觉，又超过了直觉。(暂时没有找到说明这个的例子)

看一个例题：

例5.2
假设男性色盲率5%，女性色盲率0.25%，从男女相等的人群中随机挑一人，其为色盲。问该人是男性的概率。

解：
设事件A：人是色盲，B：这人是男人，C：这人是女人。
则题目表述变为:$P(A|B) = 5\%, P(A|C)=0.25\%,P(B)=P(\overline B)=P(C)= 1/2,求P(B|A)$
由贝叶斯公式：$P(B|A) = \frac{P(A|B)P(B)}{P(A|B)P(B)+P(A|C)P(C))} =0.05\times 0.5 \div(0.05\times0.5+0.0025\times0.5) = 500/525 = 20/21$

6.独立性

在生活中，我们喜欢把没什么关系的时候瞎关联起来。比如，有人说，喝水会让人死亡，因为所有人活着的时候都喝了水。

为了驳斥这个观点，我们提出了独立性的概念，用以了解两件事事件是否会有关联。具体来说，也就是一件事发生或不发生，另一件事发生的概率是否发生改变。

若$P(AB) = P(A)P(B)$，则称A，B独立。

由$P(AB) = P(A | B) \times P(B)$可知，A，B独立，意味着$P(A) = P(A|B)$，也就是B发生对A发生的概率毫无影响，符合我们直观上的感觉。

回到之前提出的例子，我们可以用独立性的概念来不严格地解释这个问题。$P(喝水的人死亡) = P(喝水)P(人死亡)$，因为所有人喝水，这个式子显然成立。因此我们可以说明，喝水和死亡没有半毛钱关系，它们是独立的。

独立性的运用也很广。我们生活中经常把两件事都发生的概率直接用两件事单独发生的概率乘起来，就是因为我们不自觉地假设两事情是独立的。

定义独立性也没有什么的意义，就是为了方便说明。比如题目提到，这两件事是独立的，就是在说明你在算这两件事的概率时分开来算就行，不用考虑它们的影响。

例6.1：

一个盒子有3个A，2个B，2个C，另一个盒子有2个A，3个B，4个C，独立地分别地在两只盒子中各取一个东西，求
(1)至少一个A的概率
(2)1A1C的概率
(3)已知至少有一个A，求1A1C的概率

解：
$(1) P = 1 - P(无A) = 1 - 4/7\times7/9 = 1 - 28/63 = 35/63 = 5/9$
$(2) P = 3/7\times4/9+2/7\times2/9 =16/63$
$(3) P = P(2) / P(1) = 16/35$

可以看出，独立性什么新的概念也没有提出，就是方便以后的说明而已。

学习总结

概率论第一章主要介绍了概率的基本定义，并且介绍了古典概型这一贴近生活的概率模型。

这一章前半部分涉及集合运算、排列组合计数，这个东西比较看基本功，不需要特别地复习。后半部分一些条件概率的公式比较重要，需要理解记忆。最简单的条件概率公式倒也好理解，但贝叶斯公式和全概率公式如果忘记了推导的原理，还是挺麻烦的。题型应该也就按内容分成这两种。古典概型求概率，用排列组合靠大脑做；碰到需要用到概率公式的题目，用符号表示题目给的量，最后放进公式一算就行了。

参考资料

浙江大学 盛骤 谢式千 潘承毅，《概率论与数理统计》 第四版，高等教育出版社
例题来自于我们老师给我们布置的书后习题

Posted on In ,

《群体性孤独》这本书讲述了在科技的不断发展下，计算机相关技术对人们情感上的影响，给人们生活带来的改变。书的前半部分讲述了“人造生物”从电子宠物蛋发展到外表酷似人类的机器人这个过程中，人们对于这些“人造生物”的看法及背后的问题；后半部分描述了在网络化生活下，人们沉浸于虚拟世界、只以短信交流、只对陌生人告白、在熟悉与陌生的人面前表现自己的行为，以及部分人对网络化生活的焦虑、反思。本书大部分时候都是在中立、客观的角度记录人们的谈话、感受，但这些看似不带感情的文字却背后透露出一丝忧虑、一种自省与反思，引发了我对于技术和人类本身的思考。后半部分描述的情况在我们生活中已经十分常见了，而前半部分在我们周围不太常见的一些人与机器人交流的现象令我更加震撼。我主要就机器人与人的问题谈谈我的感想。

为何把更多的情感给机器人？

稍微有一点编程基础的人都能理解，在现在科技条件下，所谓的机器人的内在原理：现在的机器人能听、能看，只不过是简单地对图象、语音做一些处理，对某些东西多加一些权重；能说、能做动作，只不过是按照事先写入的一些规则，对输入产生某些反应。机器人外表上看似逼真，但那只能说是艺术制作的功劳。机器人的“大脑”，只是一些没有广泛学习功能的简单程序，和我们在电脑上使用的程序一模一样。

我自己没有接触书中提到的人造生物的经历。看到书中很多人对于机器人、机器狗甚至是屏幕上的电子宠物蛋产都能产生那么深厚的感情时，我还是有些震惊与难以理解的。但随着阅读进度的不断推进，我也大概理解了人们对于机器人产生情感的原因：人们的情感都有所缺失，所以得把情感寄托在事物上。

人们把情感寄托在事物上，其实是一件很常见的事情。在有机器人之前，人们就有养猫养狗的习惯。除了那些因为好玩而养宠物的小孩外，很多养宠物的人都是没有配偶、子女不在身边的独居的人。他们没有亲人的陪伴，只能把宠物当成那些亲人的替代品。他们对宠物好，对宠物付出感情，是因为他们也想从中得到同样的感情。不仅是活的生物，一些具有意义的物品，也能成为情感的寄托对象。比如书中就提到过，有人在独处时，经常对着一张全家福来吐诉情感。对保留了珍贵记忆的日记、他人送自己的纪念品、陪伴自己多年的工具产生一些简单的感情，确实是很正常的事。

而人的情感有所缺失，则是一件普遍却不怎么容易察觉的事。情感缺失，小到日常生活的小小挫折，大到童年留下的终身阴影，其实是普遍存在的。有了情感上的缺失，我们会下意识地寻找他人的援助，希望在情感上得到弥补。比如书中提到过，有一个渴望超过自己姐姐的女孩见到了机器人后，就会不自觉地认为机器人喜欢她甚于她姐姐；一个身体有疾病的男孩见到了机器人的一些故障，就开始担心机器人的健康。机器人只是一面无暇的镜子，映照出了人渴求的内心。

人会把情感寄托在机器人上，这看上去很容易理解。可令所有人诧异的是，这种情感似乎和其他的情感不一样，与我们对没有生命的物体的感情不同，与我们对小猫小狗的感情也不同。书中也提到，接触机器人的人中，从小孩到老人，甚至是制造机器人的科学家本身，都体会到了与接触其他任何事物所不同的感觉。这种感觉，是这本书前半部分所要反映、讨论的重点。

其实准确来说，这种对机器人的情感并不是有什么本质上的不同，而是一个量的区别。人在对物体，对动物会有情感，但我们有一个对于情感回报的期望。我们知道物体不会给我们任何回报，而动物则会以它们的方式感激一下我们。但无论如何，人们都不会把过多的情感给他们——与把情感给予自己重要的人相比。而机器人不一样，人们知道机器人的原理就是那么回事，知道了不会得到很多回报，但还是不知不觉投入了过多的感情——甚至就像对待一个不存在的亲人一样。人们下意识地投入了过多的情感，也下意识感到了异样，却没有及时理解异样意味着什么。所以，他们产生了想要掩饰这一切的行动。书中就有这样的案例：一个老太太得到了一个婴儿机器人，她短时间里竟然选择了陪机器人玩而不是和她的孙女待在一起。实验结束后她十分镇定地把机器人换了回去，继续和孙女谈笑风声，仿佛什么都没有发生过。一个老人得到了减肥机器人后，最开始是把它当成物品摆在客厅。当研究人员要拿回机器人时，他故意指责了一些把机器人当成人类的称呼。但是，此时他却把机器人从客厅带到卧室，还给机器人取了一个名字。人们见到机器人的时候，投入了与期望不匹配的，溢出的情感，所有人也暗暗察觉了这些异样。

为什么人会把更多的情感放在机器人身上呢？上过多年理科的我，用排除法得出的猜测是：机器人的交互性，让人们对机器人的情感期望有所改变。

所有这些“人造生物”被称为“人工智能“，就是因为它们有一些与人类似的交互功能。拓麻歌子只是一个屏幕中的宠物，但是你定时去照顾它，它就会给你回报，成长得更好；当你有所疏忽，宠物就可能会生病，甚至死亡。后来的猫头鹰”爱宝“，它会像人一样说话。好像你教它越多，和它说话越多，它就能真的学会说话。它在”感到难受“时，会用一些信号来表示自己的情绪。再先进一点的机器人，会自己用眼睛盯着人，会用手抓东西，会说出一些简单的话。你和它交流时，它在眼神上或者语言上会做出一些回应。

人类感性的一面，会把这些回应作为自己情感投射的奖励。仿佛你给予机器人更多情感，机器人就会肯定它们，并用这些交互式的反应来回报你。同时，机器人回应人们的方式大多是说话、表示伤心等一些人类特有的情感，在与机器人交流的过程中，你会下意识地把它们与人类关联起来，认为机器人拥有和人类一样多的情感。这些原因使人们在与机器人交互的过程中，拥有了更多的情感期望。

人们也知道，机器人并没有真正的情感与思维，这却恰恰又给了一个人们蒙蔽自我的理由。人理解他人的回应时，常常是一厢情愿地从自己的方式来理解。比如青春期的少男少女在和异性交流时，异性的某个不经意的动作，都会被认为是在表达对自己的喜欢。但随着人们生活经验越来越丰富，大家知道别人的想法是很难琢磨的。而机器人不一样，它们没有真的思维，你可以随意地、按照你喜欢的方式去解读机器人的回应。书中提到过，一个充满爱心，喜欢机器人的孩子和机器人交流后，她认为机器人也喜欢它；一个自卑而充满控制欲的孩子，认为机器人忽视了它，而对它大发雷霆。

人们在与机器人交互时表现的担忧、异样，并不是技术上的问题，而是一个涉及人们心理的问题。人们普遍在情感上缺乏安慰，会极力在事物上寻找安慰。机器人，是一个极为特殊的情感投射对象。机器人的交互性，让人们觉得机器人会在情感上给予我们回报；机器人的拟人性，让人们觉得机器人和人一样可以提供较多的情感；机器人的物体性，又让人们可以随意地解读机器人与自己的关系。人们对机器人有了更多的情感期望，把更多的情感放在了机器人上。

机器人能代替人类的工作吗？

许许多多的人都会关心，机器人，或者说人工智能，能否完全取代人类的工作。生产力的提升，能给社会带来极大的变革，工业革命就是一个很好的例子。机器在很多体力劳动的地方胜过了人类；而人工智能，则在很多需要脑力劳动的地方胜过了人类。倘若机器人完全代替了人类，那么社会必将发生翻天覆地的变化。

恐怕包括我在内的大部分人都会同意，让机器人代替一些繁琐、无聊的工作是十分可行的，比如银行柜员；但是在涉及沟通、情感方面的工作上，机器人是无法代替人类的。那些制造“真宝”，“帕罗”的人们，本意或许也是希望这些机器人能起到陪孩子玩、照顾老人的日常生活等一些繁琐的工作。他们看到孩子和老人和这些机器人相处得很好，便认为机器人确实起到了某些帮助。

然而，这些看似重复无聊的陪伴，才是最需要情感的地方。正如开始分析的那样，人类把过多的情感放在了机器人上，是因为他们本身情感有了缺失。孩子喜欢和机器人玩，不完全因为机器人和其它玩具一样有趣味性；老人喜欢机器人，也不是因为它们真正方便了自己的生活。这些人群都缺乏了应有的陪伴、感情。机器人只是作为一种代替品出现的。

我认为，我们常说的情感，其实特指人的情感。有人存在，情感才有了意义。只有从其他人身上，人才能获得最多的情感。机器人被制作的目标就是拟人，无论它们再怎么高级，人们从它们身上得到的情感，也比不过从人身上得到的情感。把情感寄托于机器人，只能缓解内心空虚的表象，却改变不了人与人之间关系愈发淡薄的现实。书中也提到过，老人们被问到是希望是人还是机器人来照顾他们时，有人毫不犹豫地选择了人；有人虽然提到了人的种种缺点，最终也选择人来照顾。

书中提到，五年级的孩子被问到是否该让机器人做祖父母的伴侣时，孩子问道：“难道没有人来做这项工作了吗？”这段话在整本书中出现了多次，也确实能够引起人们的反思：陪伴亲人，进行亲密的交流，这本来就是人该做的事情啊！在涉及情感的工作上，机器人永远无法代替人。哪怕一个机器人在照顾老人时，能够面面俱到，为他们及时测量身体状况，及时拿药，我们也不能就此把一切事情都交给机器人——我们不能忽略他们在情感上的需求。

科技时代的问题

从书中，能够看到很多社会中的心理问题。和机器人交流中的情感问题，网络化时代中的人渴望被关注的问题。仿佛在科技时代，这些问题就如雨后春笋一样冒了出来。

但我认为，这些问题一直都存在，只不过科技把它们放大、固定了而已。即使在现在，你和两三个好友久别重逢，谈笑风生，也不会拿出手机来；做在十几个熟悉的陌生人前，没有手机只会让场面更加尴尬。人与人的联系本来就比想象得要淡，与科技无关。

科技，只是把这些本来隐藏的问题暴露出来，让人们习以为常，给了自己一个忽视问题的借口。书中提到，一天和家人联系15次，过去会认为心理上不够健康，现在却是一种正常情况；原来在会议上写信会被认为是不礼貌，而现在在会议上用手机发消息也成为了常态。科技也确实有一些负面作用：它让人们不再去试图纠正这些问题。但我还是认为，科技不是问题的根源。

科技在发展，人们可以做到的事情越来越多。但是，一些错误的文化、思维方式没有得到改善，一些人与人之间的问题一直普遍存在。这些问题具体是什么？该如何去改变？这两个问题太大，以至于书的作者也无法给出明确的答案。但无论如何，人们需要进行一些反思，寻求一些解决方法。这些问题靠单纯发展科技是无法解决的。

Posted on In ,

Description

给一个由左右括号组成的正确括号序列（保证一个左括号一定对应右边的一个右括号）。

通过这个括号序列，我们可以构建一棵树：左括号表示进入子树，右括号表示从当前子树返回。括号相当于描述了一棵树先序遍历的出入栈过程。

现在，我们有q次操作。每次操作会交换括号序列中的两个的括号位置，该操作保证括号序列的正确性。每次操作后，都能得到一颗新的树。要求输出最开始和每次操作后树的直径（树上某两点距离的最大值）。

序列代表的树有$n$个节点，操作共$q$次。$3 \leq n \leq 100 000, q \leq100 000$
输出$n+1$棵树的直径

Sample Input & Output

5 5
(((())))
4 5
3 4
5 6
3 6
2 5

4
3
3
2
4
4

Sample

Solution

首先考虑到树的子树具有子结构性质。每一步操作都没有完全改变整棵树，有很多子结构的信息是相同的。

那么可以这样思考，在括号序列的任意一个位置开始往后走，我都可以得到一颗与这个位置前面的节点独立的一颗树。这棵树不一定是子树，因为从任意一个位置开始的括号序列可能会多出几个右括号，这种情况下这棵树会往回生长。

再从题目的问题入手，题目要我们求出每颗树的直径来。路径长可以看成两个树的深度减去两倍他们lca的深度。即：设点$u$的深度为$d(u)$,那么$u$到$v$的路径长$l(u, v)=d(u)+d(v)-2\times d(lca(u,v))$。而直径就是所有路径长的最大值。也就是说，如果能得知每个点的深度，并设法维护最大的路径长，就能得到答案。通过括号序列得到每个点每个时刻的深度是很容易的，现在我们就要设法维护路径长，得知路径长又必须知道点对的lca是谁。

恰好，题目给的是树的一个dfs序。任意两点的lca，都是在左边节点之后，右边节点之前访问。那我们也不用管lca是谁了，随便拿$u,v$点中间的一个点$w$，使得$d(u)+d(v)-2\times d(w)$最大的$w$就是它们的lca。即：$l(u, v)=max \{ d(u)+d(v)-2\times d(w) | t_u \leq t_w \leq t_v \}$ ，其中 $t$ 为括号序列中访问节点的时间(也可以说是序列中的下标）。

那问题就变得更简单了。只要是满足 $t_a \leq t_b \leq t_c$ 的三元组 $a,b,c$ ，$d(a) + d(c) - 2 * d(b)$ 就可能是一条路径长。维护最大的这个值，就可以得到直径。

如果只是算一次的话，一边维护当前深度，一边记录下最大的$d(a)$，最小的$d(b)$等值很容易就可以地$O(n)$维护当前直径。但问题是，题目有q次操作。这就得回到开始的分析了——每次操作过后，还有很多子结构的信息保留了下来。

我们需要的是子结构的哪些信息呢？注意到我们计算答案只用到了深度，在每一个子结构代表的树中，我们也必须得维护一些用于计算最大的 $d(a)+d(c)-2\times d(b)$ 的一些深度信息。我们可以把某个子结构开始位置当作相对深度，并记录在这个相对深度下，深度的最大最小值，路径左半边（左边的点到lca距离）的最大值和路径右半边的最大值。同时，还要记录这个子结构的总深度，以得到它和后面一个子结构的相对深度。通过以上信息，就可以维护子结构中最大的 $d(a)+d(c)-2\times d(b)$了。

这种用子结构来解决问题的思想和分治是类似的。分治的每一个结果都可以存在线段树中。虽然第一次求解的复杂度是$O(nlogn)$，但对于每次修改，都能在$O(logn)$的时间里得到新的答案。

总的时间复杂度$O((n + q)logn)$

Review

这道题实际上算法并没有很难，写起来也很容易，但比较考验思维，需要把问题进行巧妙地转换。我一直没有想出解法，是看完官方题解才写出这道题的。虽然我没有自己想出来，但在回味题目巧妙的解法时，还是学到了很多东西的。

在每次操作中，一定是有一些子结构没有改变的。这一点我一直都很清楚，一直都想找出这个子结构。但我一直都拘泥于树的结构，希望先把括号序列转变成树，再找出交换括号是对应树上的把哪一个子树移到哪个地方的操作。这样想下去的话，是怎么也找不出正解的。

想出这道题的关键，应该是想出lca可以用深度表示，而括号序列保证了lca在两点之间。这样的话，求直径就变成了维护几个最大最小值再做计算的问题。这里可以反映出我对树上的一些计算的表达形式还不够熟悉，没有第一时间把求直径的方法转换。而且，我对dfs序的性质不够敏感，没有利用好这个性质。

这样想出了用最大最小值维护答案，怎么建线段树，要维护哪些变量稍微想一想就能想出来。而其中能用线段树维护答案是这道题可以在时限内被解出来的关键。能够用线段树维护子结构，是因为每个路径包含的$a,b,c$三个值的时间是在一个连续区间里的，即$t_a \leq t_b \leq t_c$。这一个序列上的连续性使得问题能够通过线段树来维护。

这也给了我一些启示：线段树不是只能做那些给一个$[l,r]$区间，做一些修改操作的题目的。线段树维护的是连续区间上的性质。如果一个题目中看到了子结构性质，且这些结构构成了连续区间，就可以考虑用线段树来维护。或者换一种想法，如果一个问题可以用连续区间的分治来解决，那么分治的每一步结果就可以用线段树来保存。

Posted on In ,

自信地点击提交按钮后，得到依旧是一行刺眼的Wrong Answer。

数个小时的付出，丝毫没有得到回报。提交记录上，代码行数越变越多，判题结果却永远见不到绿色的那8个字母。

绝望笼罩了心头，焦躁充斥了大脑，整个世界变得黑暗了起来。

万般无奈下，颤颤巍巍地用鼠标复制一段文字，放到搜索引擎里面，点开第一个链接。

片刻之后，你恍然大悟。一切都好起来了，世界再次变得光明。

题解，正是照亮世界的那束光。

只要你参加过算法竞赛的训练，就一定接触过题解，上面的提到的经历，也都能感同身受。

我看过很多题解，也一直有考虑过自己写题解。但我一直因为一些问题而犹豫不前：我为什么要写题解呢？怎么样的解题记录才算好呢？

思考了很久后，我今天写出我的第一篇解题记录。我也顺便写一下我的思考结果，稍微谈一谈我对解题记录的认识。

别人的“题解”

大多数的题解都是这样的：标题是题目来源及题目名称，后面用括号写下题目算法。正文内容先把题目完完全全复制过来，之后贴上自己代码，谈一下解题的思路。大家写题解都默认使用了这套“模板”。

这样写题解是为了什么呢？是用来给那些想不出题的人来看吗？仔细一想这是不太合理的。没写过这道题的人，认真阅读这篇题解的概率极低；看过而不会写这道题的人，肯定已经理解了题意，试过了输入输出。再把多余的信息写上来是没有意义的。此外，「别人的代码」是比医生的病例还要难看懂的东西。如果要把方法讲清楚来，很多时候用文字或者伪代码来表达算法，比直接贴代码效果好很多。最后还有一小点，很多题目偏向思维题，知道了做法就可以立刻写出题来。如果把题目的算法直接写在标题里，会让那些还摇摆不定不知道要不要认真看完题解的人立刻知道题目的做法。综上，只要稍微想想就能发现，“题解”并不是写给别人看的。虽然网上的题解被大家当成了写不出题的救命稻草。

比较合理的想法是，“题解”的称呼有失偏颇，正确说法应该是解题记录。解题记录就是给以后的自己复习看的。标题里的算法方便自己找到对应类型的题目；复制的题面能避免翻原网站的麻烦；自己的代码让自己能快速理解思路；解题思路里的三言两语能快速唤起写这道题时的记忆。这样一看，解题记录纯粹是为了方便自己而写，这种说法有道理多了。

但我依旧对这种写解题记录的方式抱有一丝的厌恶。

以我狭隘的心理来揣测，许多人写题解，只是为了写题解而已。他们看到了别人的博客，看到了几百篇、上千篇解题的记录，他们感到了敬畏与心虚。于是，他们开通了自己的博客，用同样的格式来写解题记录。自己的博客越写越多，那颗空虚的内心也会越来越踏实。

也不能说这样完全不好。起码每写完一道题，贴完一道题目的题解，你能够收获一份成就感，能够让自己坚持下去。

但除此之外，这样写解题记录就是浪费自己时间。

写完一道题目，这题水不水，你学到了多少东西，你有没有学到东西，大家心里自己都有数。单纯地让解题记录数目++，只是让自己心里好受一点：不管参加比赛打得怎么样，不管我菜不菜，起码我还写了这么多题目。

那些写了几百题上千题的人，不是因为他们写了解题记录而厉害，是因为他们真的认认真真想要去提升自己，认认真真地写了那么多题目才厉害啊！

这是我一直没去写解题记录的原因。

我对自己解题记录的要求

做事首先要目标明确。思考与尝试了一段时间后，我总结出了我自己写解题记录想要达到的目的。

  1. 对于解题时思路不清楚，甚至看了题解的题目，要借写解题记录的机会，彻底地把题目再思考一遍，把题目吃透来。
  2. 记录反思写题时碰到的一些轻微的思考错误、代码错误，争取以后不犯错。
  3. 对于略带套路的题目，写解题记录能让自己加深印象，记住这种比较特殊的题型。
  4. 如果有人在写这题时碰到了困难，碰巧看到我的解题记录，我能保证他能通过我的解题记录彻底理解这道题。
  5. 给未来的自己当回忆录看。

上述目的是按重要性降序排序的。与学新东西同理，写解题记录时，你会为了把事情说清楚，而不得不自己先把事情全部理解透。通过写解题记录这种手段来达到完全理解题目，这大概是写解题记录最大的目的。可以说第一条是最最重要的，相比之下后面几条都没那么重要。

可以看出，最应该写解题记录的题目，应该是在补题或学新专题时，那些略微超出自己当前能力，要稍微看看题解才能想出的题目。这些题是真正能提升自己的题。而在比赛中，你能过的题目，你一定都已经完全掌握了，这些题目就没有写记录的必要了。

顺带提一下我当前的记录格式。我会先把题意用较为清晰的话表达出来，再附上题目的样例。之后我会按照思维顺序把题目的解法娓娓道来。最后以反思收尾，回顾整道题的收获。整篇记录，起承转合，抑扬顿挫，虽无音韵、色彩之美，却有逻辑、通顺之妙。能想出这种格式的人，不可谓不是一个奇才。

今天是我第一次在博客里写解题记录。老实说，花的时间很多，我也能理解为什么很多人只是贴个代码稍微提两句题目——有认真写一篇解题记录的时间，下一题都写完了。但是我还是不愿意潦草地只把解题记录当成普通的记录。要做就把事情做好。哪怕以后我因为怕苦怕累，再也不写解题记录了。哪怕整个互联网中，只流传了我一篇质量奇高的解题记录，这篇解题记录成了我的绝唱，那也没有什么遗憾的。毕竟我的优秀作品还会有很多，这篇解题记录只是钻石里的一块金子。

Posted on In ,

Description

给m个由A,C,G,T组成的DNA片段。现在你需要构造一些长度为n的字符串，使这些字符串完全被这些DNA片段覆盖。求构造方案数 $mod$ $1e9+9$ 。（DNA片段之间可以互相重叠）

长度 $n\leq1000$，片段个数 $m\leq10$，片段长度不大于10.

Sample Input & Output

6 2
CAT
TACT

2

（CATCAT和CATACT是可行的方案）

Solution

DNA间可以相互重叠，也就是匹配完某个DNA后，匹配下一个DNA时不一定会从头开始，而是从下一个DNA的某个前缀开始（这个前缀也是当前DNA的后缀）。为了表示这种关系，肯定会想到使用AC自动机来表示匹配的状态。

有了AC自动机，我们就可以把所有 $4^n$个字符串全部输入自动机，保证状态转移“合法”，统计出最终所有满足条件的状态就行了。现在我们要做的事情有三件：统计状态，判断状态转移是否合法，判断结果是否满足条件。我们一件一件来解决。

每个状态对应AC自动机上的一个节点，因此用一个dp[MAX_NODE]数组就可以存处于当前状态的方案数。每多放入一个字符，状态就会发生转移。理论上，当前字符数的状态只与上一字符数的状态有关，拿两个dp数组循环用就行了。但为了书写方便还是先定义成dp[MAXN][MAX_NODE]，每次dp[i]由dp[i - 1]转移而来。

接下来来判断合法的状态。所有字符串都要被DNA覆盖，也就是在AC自动机上转移的时候，不能还没走到终点（DNA的结束点），就跑到另一个DNA字符串的前缀去了。只有当走到了终点的时候，才可以随意地走下一步（但是不能走回根）。

统计答案也很简单，只有那些DNA字符串结束点对应的状态才能被统计进最终答案。

根据以上分析可以写出以下式子：

$当j 为终点:$
$dp[i][j.next[k]] += dp[i - 1][j] (j.next[k] \neq root, k \in {A, C, G, T})$
$否则:$
$dp[i][j.next[k]] += dp[i - 1][j] (j.next[k] 不通过fail转移, k \in {A, C, G, T})$

提交上述代码会得到WA的结果。

考虑下面的例子: 3 3 ACCC A C。ACC显然是一个满足条件的字符串，但在自动机上，ACC却不是一个字符串的结尾，最终不会被统计答案。

那我是不是应该把字符串结尾通过fail传递下去呢？也就是说，只要一个字符串的后缀是某个更短的字符串的结尾，那这个字符串也被认为是满足条件的字符串。这样更不对了。考虑例子：2 2 ACC C，AC不满足条件，却因为有后缀C被错误地统计进了答案。

这个时候我们发现，怎么样都无法合理地表示答案。换句话说，现在这种定义状态的方式，会混淆一些本质不同的状态。在定义一个状态时，只是记录这个状态处于AC自动机的哪个节点是不够的，还得记录一些其它的东西。

从本质上思考，一个满足条件的字符串可以分成两部分，后一部分是最后一个被覆盖的DNA，前一部分是之前匹配好的一堆DNA。前一部分和后一部分可以重复。对于AC自动机上的一个状态，它的最长的DNA后缀是确定的，但是它之前已经被匹配好的长度是不确定的。而一旦我们确定了这两个值，我们只要判断之前匹配好的长度加上最长的DNA的后缀长度是否大于等于整个当前字符串的长度即可（等价于前一部分和后一部分正好拼接或覆盖）。我们在dp中还要加一维，记录某个状态被匹配的长度。顺便，为了之后的判断，AC自动机上每个节点的长度和最长DNA后缀的长度也要提前统计好来，后者可以通过fail边来转移。

和开始一样，继续解决三个问题：状态定义、答案判断、合法转移判断。

现在，$dp[i][j][k]$被定义为放第$i$个字符时，处于AC自动机上$j$号节点，在自动机前面已经匹配好了长度为$k$（而不是总长度已经匹配好了$k$）的方案数。$j.len,j.low$分别表示某个节点的长度，最长DNA后缀长度。

对于某个$j,k$，若$j.low + k \geq j.len$，则说明这个状态满足条件。最终$dp[n][j][k]$中满足条件的状态的dp值之和就是题目的答案。

转移时，我们不再死板通过判断一条边是否是通过fail转移的来判断这个转移合不合法。在当前一个非答案状态$i,j,k$上，对于下一状态$j.next$，只要$j.next.len + k > j.len$，就能保证在状态转移时中间没有“断掉”。下一个状态的最长匹配长度为$j.next.len + k - j.len - 1$。也就是说:
$dp[i + 1][j.next][j.next.len + k - j.len - 1] += dp[i][j][k]$

对于某个状态，如果它已经满足了被覆盖的条件，则下一状态的最长匹配长度一定是下一状态的长度减1（因为多出了一个新的未匹配字符），写成式子的话：
$dp[i + 1][j.next][j.next.len - 1] += dp[i][j][k]$

至此，题目顺利解完。dp数组是1000 100 10的，时间复杂度$O(n|str|\sum|str|)$

Review

题解部分应该是正常的思考过程，发现二维不够后用三维dp，这也是我写这题从WA改到AC的过程。

之前我一直以为，AC自动机中dp都很容易，只和处于哪个节点有关。看完题面后，我立马敲了一个二维dp出来，很快WA了。

在cf上对着样例调试多次后，我才发现怎么定义dp都不行。看了一眼题解，发现状态要多定义一维后，我重新地把题目考虑了一遍，定义出了新的状态。

后来状态转移我差不多写完了，交上去WA了一个大的样例。仔细思考过后我发现，非答案状态在转移时，它的最长匹配长度可能会变的，这一步转移需要认真考虑。改完这一处后总算AC了。

这题对我最大的启示和警示是，AC自动机的dp不一定都那么简单，很多时候但靠节点来定义状态是不够的。

在用dp时，一定要把状态的每一个变量的转移都考虑好。尤其是在重新定义了dp状态后，最好能完全从头推一遍递推关系。

Posted on In ,

2019年的3月17日，对于人类来说，可能只是普通的一天。但是，这一天却发生了一件影响极其深远的事：天才游戏设计师、世界著名大局观选手、改变中国的十四亿人中重要的一员——周弈帆开始写博客了。

第一篇博客就不谈什么大的东西了，我就谈一谈我为什么要写博客。

为什么要写？

人活得久了，见过的悲欢离合越多，对这个世界的理解也就越加深刻。现在的我虽年未弱冠，但已经隐隐参透出了这个世界的一些奥妙。如果把这些宝贵的知识财富一直藏在我的心里，那对于世界思想界来说将是一件极为可惜的事。所以，我想把我自己对于一些我熟悉的事情的看法、经验整理一下，创造出一些有趣的 「理论」，供世人品鉴。

现在的我没什么大的成就，唯一的可以提一提的就是在高考这个战场上杀出了一条血路。在学校学了这么多年，我深深感受到了学习的方法性。差的老师、烂的教材，都会为你的学习带来极大的阻碍。我想写一些简明易懂的 「技术文章」，来减少那些恰好和我专业方向相同的人的时间。

人嘛，总是希望得到别人的认同——你吹我，你就是我的好朋友；你黑我，我就恨不得把你喷到改口为止。虽然我的反应不会这么激烈，但那份渴望认同的心还是和常人无异的。我有时也会发一些带有主观色彩的 「评论」 文章。我的文字功底不是很好，写不出什么辞藻华丽，又有内涵的抒情文，但我可以用结构严谨的议论文，一字一句地说清楚我的看法。

为什么是博客？

自互联网在中国开始兴盛以来，主流社交方式换了一波又一波。我虽目睹了整个互联网的发展过程，却因为年纪尚小，没有亲身投入到这股浪潮中。当我想好好得在社交媒体上展示自己时，却发现我已经不太适应主流的社交媒体了。

对于大部分像我这样的平民百姓来说，社交媒体就是满足自己虚荣心的小小舞台。分享出生活中亮眼的几个片段，极力吸引住熟人的注意。每一次被浏览，那渴望被关注的心就会得到一丝的满足。

对于某些媒体来说，社交媒体不过是一个敛财的工具。被关注得越多，得到的收益越多。只是四处张罗吆喝也还好，但用一些有成本的手段去创造关注，这就让社交媒体本身的性质改变了。

越快越短的东西，只会让价值不断地消失。

我仔细想想，还是博客好。在一个人的天地里，能够随心所欲地发言。我会在这里，慢慢地、静静地，书写我自己的价值。博客是也算是一个社交媒体，虽然不会有太多的人去关注，但也不会有多余的东西。

我的目标

今天勉强算是完成了第一篇博客，但距离我准备写博客已经过去一个多月了，我本身拖延症似乎有点重。再加上博客本来就是带有娱乐性质的东西，强求自己做一些事也没必要。在博客经营上大而具体的目标就不订了。

然而，如果我享受到了写博客的乐趣，我就会竭尽所能，去写出一些有价值的东西。之后，我会让更多的人去看的文章。我不求别的，只希望某些人在看过我的文章后，能发自内心地说出：

从字里行间就能看出来，这个小伙子天赋异禀，才高八斗。遣词不可谓不精妙；造句不可谓不用心；道理不可谓不深刻。可谓是江山代有人才出。看着他的文字，我的脑海中就浮现出一幅英俊、帅气、潇洒、精致的脸庞。此人前途无量啊。