Content #

def permutations(S):
    if not S:
        return [[]]
    else:
        res, perms = [], permutations(S[1:])
        for i, _ in enumerate(S):
            for perm in perms:
                res.append(perm[:i] + [S[0]] + perm[i:])
        return res

将S[0]插入S[1:]的排列集合元素的每个位置。

From #

Links #

Content #

阅读就是学习：指导型的学习，以及自我发现型的学习之间的差异

读得多并不意味着读得好。必须要区分出各种不同的阅读形态。这种区分对阅读的本身，以及阅读与一般教育的关系都有很重大的影响。

在教育史上，人们总是将经由指导的学习，与自我发现的学习区别出来。一个人用言语或文字教导另一个人时，就是一种被引导的学习。当然，没有人教导，我们也可以学习。否则，如果每一位老师都必须要人教导过，才能去教导别人，就不会有求知的开始了。因此，自我发现的学习是必要的——这是经由研究、调查或在无人指导的状况下，自己深思熟虑的一种学习过程。

◆ 自我发现的学习方式就是没有老师指导的方式，而被引导的学习就是要旁人的帮助。◆ 要区分得更清楚一些的话，我们可以称指导型的学习是“辅助型的自我发现学习”。◆ 医生努力为病人做许多事，但最终的结论是这个病人必须自己好起来——变得健康起来。农夫为他的植物或动物做了许多事，结果是这些动植物必须长大，变得更好。同样地，老师可能用尽了方法来教学生，学生却必须自己能学习才行。当他学习到了，知识就会在他脑中生根发芽。

◆ 自我发现型的学习——严格来说，非辅助型的自我发现学习——是阅读自我或世界的学习。就像指导型的学习（被教导，或辅助型的学习）是阅读一本书，包括倾听，从讲解中学习的一种艺术。

◆ 阅读的艺术包括了所有非辅助型自我发现学习的技巧：敏锐的观察、灵敏可靠的记忆、想象的空间，再者当然就是训练有素的分析、省思能力。这么说的理由在于：阅读也就是一种发现——虽然那是经过帮助，而不是未经帮助的一个过程。

◆ 倾听是从一位出现在你眼前的老师学习——一位活生生的老师——而阅读却是跟一位缺席的老师学习。

From #

《如何阅读一本书》 莫提默·艾德勒 查尔斯·范多伦

Links #

Graph #

• luogu3916 建反向图，深度优先，练习使用 链式前向星。
• uva11175 使用邻接矩阵，题目分析较难想到。
• uva572 深度优先查找连通分量个数。
• uva1599 双重BFS，在最短路径前提下，找最小的序列。较难。
• poj2488 马走遍棋盘的问题，要按字典序做DFS。
• poj3278 同一直线上追逐问题，练习DFS的好例子。

最短路径 #

• luogu4779 单源最短路径模板题，练习Dijkstra算法。
• bailian1797(Heavy Transportation) Dijkstra算法，更新条件稍做变形。dist数组的初始值设置需要留意。
• bailian1860(Currency Exchange) Bellman Ford算法判断正环，需要自定义松驰运算。
• poj3259(Wormholes) SPFA判断负环的存在。
• poj3268 两次SPFA算法，转换视角，构造逆向图。
• P9751([CSP-J 2023] 旅游巴士) 分层图，Djkstra算法。仔细分析题意，这是一个有环图。每个节点会有多个状态。
• P9751([CSP-J 2023] 旅游巴士) 用BFS和二分查找来实现。需要估计最大值搜索的的范围。

最小生成树 #

• luogu3366(【模板】最小生成树) 用链式前向星存图，复用Edge，使用用priority_queue，实现Prim算法。
• bailian1251(Jungle Roads) Prim算法模板题，不需要记录生成树，代码可简化。
• bailian1287(Networking) 并查集优化的Kruskal算法。
• bailian2031(Building a Space Station) Prim算法，建图需要分析。
• bailian2421(Constructing Roads) Prim算法，将已经建好的路的权值设为0。

拓扑排序 #

• bailian2367(Genealogical tree) 拓扑排序模板题，使用邻接矩阵。
• bailian1094(Sorting It All Out) 拓扑排序中判断环，是否唯一，逻辑容易出错。不唯一判断的优先级在环的判断之后。
• poj3687(Labeling Balls) 建反向图，计算节点的入度，与拓扑排序算法的思想一致，但具体做法有区别。
• bailian1270(Following Orders) 用DFS找出所有拓扑序列，节点入度为0，是算法的关键。
• hdu4109(Instrction Arrangement) CPU最短运行时间求的是最长距离。
• poj1949(Chores) 依赖性有次序，无需拓扑排序即可解决。

图的连通性 #

• bailian1144(电话网络) Tarjan算法求割点个数。
• bailian3091(Road Construction) Tarjan算法求解双连通分量，并统计叶子节点个数。需要推导。从题意分析，从任意节点出发，都能访问到其余所有节点，因此，tarjan算法只需执行一次，得到的low数组的值即可视为双连通分量的编号。
• bailian2553(The Bottom of a Graph) Tarjan算法求强连通分量，并输出出度为0的强连通分量的节点。 low值本身并不是用来区分不同强连通分量的。在一个图中，不同强连通分量中的顶点可能会有相同的low值，特别是当不同强连通分量之间存在指向关系时。low值不能作为强连通分量的唯一标识，因为它们只反映了顶点能够回溯到的最早时间戳，而不是顶点属于哪个强连通分量。不能以empty是否为空来判断强连通分量是否结束。
• bailian1236(Network of Schools) Tarjan算法求强连通分量，找到出度为0及入度为0的强连通分量的节点个数。解法与bailian2553相似。

Links #

2023 #

• P9758 小苹果 使用数据结构模拟，最大的测试数据通不过。只要关心苹果数量，不必具体到哪些苹果被移除。数学题。
• P9749 公路 贪心算法。思路很重要，按题意在每个加油站上做选择，会增加解题难度。

2022 #

• P8813 乘方 逐个相乘，判断特殊情况。简单。
• P8814 解密 等式变化，根据韦达定理构造一元二次方程，判断其解是否为正整数。

Links #

Content #

我敢肯定没有任何生物能像我们一样渴望着文学创作。这并不是因为其他物种缺少语言能力而无法做到这一点，而是因为其他物种缺少足够完备的心智理论，无法探索他人的精神世界。

写小说意味着需要想象出虚拟的世界，黑猩猩所拥有的心智理论并不足以完成文学创作。黑猩猩最多能达到三级意向（我相信你想让我认为食物箱子是锁上的），而人类能不太费力地跟上四级意向的思维。

From #

《梳毛、八卦及语言的进化》 [英]罗宾·邓巴

Links #

Content #

事实是，几乎我们所有的对话都有隐喻性质，或需要听话者来解读。通常我们所说的话都是电报式的，只提供了说话要点，听话者能够自动补充完整，以此来理解我们所说的话。

下面这个经典的例子涉及我们日常对话经常需要的深层次解读：

男方：我要离开你。女方：她是谁？

很明显，根据语境以及说话人的过往经历，男方的话可以有多种不同的合理解释。但即使是这么简短的对话，我们也能立刻正确解读出女方回应话语中的隐晦含义，立马就能脑补出所有细节，并检索出可能相关的大量背景信息。

自闭症患者做不到这一点。患有轻度阿斯伯格征的人往往能够设法应对各种社会情境，因而能够通过错误信念测试，但他们却无法像我们一样去解读别人的心思。他们处理问题的方法是心理学家弗朗西斯卡·哈佩(Francesca Happé)所谓的“破解它”(Hacking it)。换言之，他们像正常智力的人一样聪明，能够总结出规律，这样他们十有八九能凭经验在社交场合做出正确的决定。但他们只知道这样做行得通，却不知道为什么。

From #

《梳毛、八卦及语言的进化》 [英]罗宾·邓巴

Links #

Content #

自闭症患者主要有两种缺陷：一是始终无法通过错误信念测试；二是明显缺乏参与假装游戏的能力。

心理学家艾伦·莱斯利(Allan Leslie)曾提出这两个特征彼此紧密相连。因为他们意识不到其他人会持有错误信念（或至少他们认为是错误的信念），也无法想象别人的世界或者是不同于现在的世界。这就导致他们无法参与虚拟游戏。例如，他们不会玩过家家，洋娃娃是没有生命的，它们怎么可能像真人一样。他们不会装睡来捉弄别人。同样，他们也不会故意说谎，因为说谎时你知道别人并不完全知情，而他们意识不到这点。自闭症患者只认为世界是公开明了的，他和自己的观众都知道同样的信息。

From #

《梳毛、八卦及语言的进化》 [英]罗宾·邓巴

Links #

Content #

现在我们很清楚，对于儿童来说，理解社会远比认识物质世界困难得多。

这一发现完全改变了著名心理学家让·皮亚杰(Jean Piaget)的发展理论。近半个世纪以来，皮亚杰的理论一直主导着人们对儿童智力发展的看法。他致力于解释儿童怎样认识世界。与其他同时代的人一样，皮亚杰认为是大脑负责处理有关世界的信息，因此对于儿童来讲最难的是理解世界的奥妙。他认为除此之外的其他问题都好解决。皮亚杰看到儿童在社会领域表现得如此卓越，便误以为这些才能无关紧要。显然儿童在一开始就能毫不费力地掌握这些。皮亚杰的误解也是可以理解的，那个时代很少有人意识到我们的世界到底有多复杂。

对儿童来说，掌握社会技能是十万火急的事情，关乎其生存。在早期只要像视觉和听觉这些次要的功能发育完好，而其他更复杂的任务，例如，理解数量和体积守恒——皮亚杰十分看重这方面——则可以缓一缓，等到儿童弄清楚身处的社会迷宫之后，再解决这些复杂的问题也不迟。

From #

《梳毛、八卦及语言的进化》 [英]罗宾·邓巴

Links #

Content #

研究结果表明，四岁到四岁半对儿童来说是一个关键的分水岭。他们好像突然意识到其他人的想法可以与自己的不同。直到这个时候，儿童才开始去解读世界（以及他人对世界的看法），而不是看到什么就是什么。他们无法想象世界如果不是他们看到的这样会是什么样子，因而也不会意识到你和他们的想法、观念会有不同。他们认为你看到的也是他们自己看到的，你们解读事物的方式是一样的。

这就导致了一个结果：儿童三岁前不会说谎（或者至少说谎也会露出破绽）。也就是说，他们并未意识到你的心理状态和想法是可以被操控的。三岁左右的儿童就知道如果自己极力否认偷吃了很多巧克力，你基本会相信他，但是他还不知道残留在嘴角的巧克力会出卖自己。几个月后，儿童习得了心智理论，他们就能操控你的想法使坏。

From #

《梳毛、八卦及语言的进化》 [英]罗宾·邓巴

Links #

Content #

过去10年的研究结果显示，核心问题在于心理学家所说的心智理论(Theory of Mind,ToM)，这是一个让人疑惑的叫法。

心智理论意味着我们可以理解他人的想法，理解他人的信仰、欲望、恐惧和希望等，并猜想他人确实正在经历这种心理状态。我们可以设想这样一种自然的等级体系：

你有你的心理状态（对某件事的看法），我可以针对你的心理状态形成自己的心理状态（对一种看法的想法），如果你的心理状态正在思考我的心理状态，那我们便可以说“我知道你认为我相信某事是这样的”。

现在这种等级体系通常被称为意向层级(orders of intensionality)。这样一来，便大致上有了下面的层级划分。

1. 零级意向

电脑等机器属于零级意向，它们无法感知自己的心理状态。可能人类在昏迷时也处于零级意向状态，大部分昆虫及其他无脊椎动物也属于这一级别。

1. 一级意向

笛卡尔的名言“我思故我在”问世以来，我们就有了一级意向状态（我认为某事是这样的）。

1. 层级较高的意向

此后，我们开始陷入这种无穷无尽的回问：我认为你认为某事怎样（二级意向）；我认为你认为我认为某事是怎样的（三级意向）；我认为你认为我认为你认为某事是怎样的（四级意向）；以此类推还能继续说下去。显然，层级较高的意向常常被称为“读心”。

From #

《梳毛、八卦及语言的进化》 [英]罗宾·邓巴

Links #