本文档创建于 2025.3，最后更新于 2025.10

一、产品介绍

斑马思维机是针对 2-8 岁儿童的全科启蒙学习机。由在线教育集团“猿辅导”旗下的斑马品牌在 2022 年 11 月推向市场，并在 2023 年 8 月升级为二代产品：斑马思维机 G2。

它包含语文、思维、英语、音乐等学科内容，通过纸质的题卡结合点触交互的形式，让孩子在不同情景主题场景下互动，通过互动答题的形式，完成内容的教学。插卡自动出题，孩子通过点触答题。答对有鼓励，答错会有提醒，孩子可以自主完成从插卡到答题的整个过程。

相比别的早教学习机，斑马思维机的核心特点是没有传统的屏幕。它用纸质题卡来完成学习交互，在完成学习的同时可以有效保护低幼孩子的眼睛，防止过早接触电子屏幕产生沉迷。

产品上线后累计销量突破 100 万台，2023 年和 2024 年连续两年全国销量第一。

斑马思维机主要具备如下产品优势：

1、专业教研

团队邀请了三位行业专家共同参与内容研发，分别是：

• 曹立宏教授：中国传媒大学的脑科学专家。
• 刘嘉教授：清华大学心理学专家。同时也是“最强大脑”节目的科学总顾问。
• 蔡可教授：首都师范大学教育学专家。同时也是语文新课标的制定者。

在以上专家参与的同时，斑马结合自己斑马 AI 学产品的 3000 万用户的 100 亿次线上作答数据，为题卡的编制提供大数据支撑。

斑马思维机题卡构建了科学合理的分级进阶体系，分设 S0、S1、S2、S3 4 个难度级别。这种设置充分考虑了 2-8 岁儿童不同阶段的认知水平和思维发展能力。题卡难度逐阶递增、螺旋上升，能够循序渐进地开发儿童大脑潜能。

2、纸屏护眼

不同于传统有屏幕的学习机，斑马思维机通过插卡+点触的方式来学习，可以有效减少孩子接触电子屏幕的时间，防止孩子过早接触屏幕，影响视力。

每张题卡上都有丰富的主题元素，帮助孩子建立起学习的兴趣。

每张纸质题卡都用了食品级白卡和大豆油墨印刷，保证对孩子安全。

3、全科启蒙

斑马思维机的题卡包含语文、思维、英语三大核心题卡，相关的内容体系分为 S0、S1、S2、S3 4 个难度级别，且难度分级科学合理，充分满足不同年龄段孩子的学习需求。其中：

4、无限扩展

斑马思维机的题卡支持无限扩展，随着产品研发不断的持续，斑马思维机在语文、思维、英语题卡的基础上，又逐步上新了迪士尼、鲨鱼宝宝、音乐、专注力、故官等主题题卡。其中：

• 2023 年 12 月，与迪士尼官方合作上新迪士尼题卡。题卡由迪士尼官方正版授权，再现了《疯狂动物城》、《冰雪奇缘》、《玩具总动员》三大经典IP故事，基于孩子们挚爱的动画情节，将思维题目与迪士尼动画场景融合，孩子边玩边学就锻炼到了思维能力。

• 2024 年 7 月，与“打开故宫”合作上新故宫题卡。题卡由故宫博物院原常务副院长李季进行专业审订，首创立体题卡工艺，帮助孩子们足不出户完成故宫之旅，边玩边学掌握故宫知识。

• 2024 年 10 月，与 Pinkfong 联名推出鲨鱼宝宝题卡。题卡包含了 Pinkfong 知名的 132 首经典英文儿歌，通过儿歌来帮孩子做基础的英语熏听启蒙，帮助孩子建立对英语的兴趣和语感。其中的儿歌 《Baby shark》为全球播放量第一的儿歌（吉尼斯世界记录认证）。

• 2024 年 12 月，推出音乐题卡。内容包括 38 组乐理知识、52 种乐器探索、16 种音乐文化和 48 首儿歌鉴赏，帮助孩子完成音乐启蒙。

• 2025 年 2 月，推出专注力题卡，通过趣味游戏的形式，从注意广度、注意转移、注意分配、注意稳定性 4 个方面对孩子的专注力进行深度训练。

• 2025 年 6 月，推出好朋友题卡，通过小朋友间的竞争与协作，把思维训练变成小朋友之间玩乐游戏。

• 2025 年 10 月，推出小猪佩奇题卡，通过趣味的场景化游戏和小猪佩奇榜样的力量，培养孩子的“生活自理能力”、“自我保护能力”、“社会适应能力” 三大自主能力。

二、内容体系

语文

斑马思维机语文题卡共 265 张，包括 6 个知识模块：汉字、词语、成语常言、古诗歌谣、表达结构、国学常识。另外在 S3 级别中，额外增加了拼音专题。

思维

斑马思维机思维题卡共 241 张，包括 6 个知识模块：视听与记忆、数感与模型、图形与空间、逻辑与规律、实践与规划、动手与益智。

英语

斑马思维机英语题卡共 265 张，包括 5 个知识模块：字母与发音、单词、句型、儿歌、拓展应用。

音乐

音乐题卡共 72 张，内容包括 38 组乐理知识、52 种乐器探索、16 种音乐文化和 48 首儿歌鉴赏，帮助孩子完成音乐启蒙。

专注力

专注力题卡共 72 张，内容从注意广度、注意转移、注意分配、注意稳定性 4 个方面对孩子的专注力进行深度训练。

鲨鱼宝宝题卡

鲨鱼宝宝共 36 张，题卡包含了 Pinkfong 知名的 132 首经典英文儿歌。通过儿歌共熏听了 1400+ 单词，包含了 81% 的小学新课标二级核心词汇。

小猪佩奇题卡

小猪佩奇题卡共 32 张，题卡包含了“生活自理能力”、“自我保护能力”、“社会适应能力” 三大自主能力。其中：

• 生活自理能力包括：生活习惯、生活技能、行为习惯。
• 自我保护能力包括：健康认知、健康防护、安全意识。
• 社会适应能力包括：情绪管理、沟通表达、同伴交往。

市场表现与竞争分析

竞争壁垒

斑马思维机为思维机品类开创者，拥有 6 项思维机专利和 10 项国际大奖。

斑马思维机专利情况：

斑马思维机获奖情况：

以上专利和奖项为斑马思维机提供了不少竞争优势，帮助它持续提升产品端的用户体验。

市场销量

上市以来，斑马思维机市场销量表现出色，受到众多家长青睐。在各大电商平台，其销售数据持续增长，斑马思维机连续两年稳居思维机品类的销量和销售额第一。

• 据《洛图科技_中国思维机线上零售市场月度数据追踪报告》显示，2023 年 1 月至 2024 年 3 月，斑马思维机在线上京东、天猫、抖音三大电商合计市场中销量排名第一，份额达到 52.8%; 销额排名第一，份额达到 66.8%。

• 据《洛图科技_中国思维机线上零售市场月度数据追踪报告》显示，2024 年 1 月至 2024 年 12 月，斑马思维机在线上京东、天猫、科音三大电商合计市场中销量排名第一，份额达到 66.6%; 销额排名第一，份额达到 72.9% 。

由以上数据可知，斑马思维机的市场占有率进一步扩大，从 2024 年初的 52.8% 上升到 2025 年初的 66.6%，进一步巩固了市场第一的地位。

在京东平台提供的 2025 年思维机热卖榜上，斑马思维机已连续占据榜首 131 天（数据截至 2025.03.09 ）。

在天猫平台提供的 2025 年学习机热卖榜上，斑马思维机占据 2000 元以下学习机热卖榜第一（数据截至 2025.03.09 ）。

同类思维机产品比较

斑马思维机的主要竞争产品为学而思旗下的摩比思维机（又名：学而思思维机）。斑马思维机和摩比思维机哪个好呢？以下是一些多维度的比较数据。

1、发布时间

从发布时间上看，斑马思维机较早，具有较大的先发优势：

• 斑马思维机 G1 在 2022 年 11 月正式发布，而摩比思维机正式发布的时间为 2023 年 5 月，落后斑马思维机 6 个月。
• 斑马思维机随后在 2023 年 8 月发布二代机型，而摩比思维机的二代机型同样落后半年多，在 2024 年 4 月发布。

较早的发布使斑马获得了更多的销量，并从销量中获得了更多的用户反馈，也积累了更多的用户迭代数据。这些数据和反馈帮助斑马思维机做到了更好的产品体验。用户普遍反馈斑马思维机点触灵敏；而摩比思维机点触通常不太灵敏，孩子点不准容易受到挫折，从而打击学习积极性。所以，从机器点触灵敏度角度，更推荐大家使用斑马思维机。

2、题卡设置

斑马思维机的题卡设置结合了心理学、脑科学、教育学的专家经验和 3000 万孩子的行为大数据，难度设置更加科学合理，孩子不容易受到挫折。

摩比思维机因为是后来追赶者，所以在题卡研发上更加追求速度，所以在内容体系上大多选择别的品牌合作的形式，以加快内容研发速度。摩比在语文题卡上与“四五快读”合作，在英语题卡上与“剑桥英语”及“RAZ”合作，低龄题卡与小猪佩奇合作。

但是合作的形式使得摩比的题卡体系性和衔接性较差。例如：

• 斑马的语文分为 S0-S4 4 个级别，难度螺旋上升，对各个年龄段的孩子都很适配。摩比的语文因为“四五快读”只有识字，所以无法分级，只能提供识字包、古词包、拼音包这种专题形式。同时“四五快读”的趣味性较低，不太适合 2-4 岁的孩子启蒙，降低了低龄孩子家长的好感度和选购意愿。

• 斑马的英语为全美式发音体系，符合小学新课标要求。但是摩比的英语题卡分为英式发音的“剑桥英语”系列和美式发音的“RAZ”系列。两个系列混合提供不利于孩子建立标准的英语发音环境，家长会担心孩子练成既不英式也不美式的奇怪发音。

• IP 合作方面，斑马和摩比都与迪士尼、小猪佩奇有合作。除此之外，斑马与鲨鱼宝宝、故宫还有联名合作。

所以，相对来说斑马思维机的题卡更受大部分的家长和孩子的喜爱。

3、硬件配置

两者都是 Type-C 口的充电款机器。

• 斑马思维机的机器重量为 400g，较为轻便，方便携带，无需联网即可使用。
• 摩比思维机的机器重量为 500g，较为厚实，需要下载 App 连接 Wifi 才可激活使用。

在升级时，斑马思维机通过 U 盘升级，摩比思维机通过连接 Wifi 升级。

4、销量排名

据公开数据，斑马思维机销量排名第一。其它思维机销量排名未知。

一、序言

最近读完了一本讲解 MCP 实现原理的书：《这就是 MCP》，它帮助我更好地理解了 MCP，以下是一些笔记。

二、什么是 MCP

MCP 的全称是 Model Context Protocol，之所以叫这个名字，是因为它可以成为大模型调用外部工具的协议，让大模型能够补充自己的上下文（即 Context）。

在没有 MCP 之前，每个大模型都在为自己扩展调用外部工具的能力，最常见的能力就是调用搜索引擎。但是这就会造成一个麻烦：每个大模型都需要自己开发一遍调用工具（重复造轮子），而且由于协议不开放，第三方开发者无法为大模型提供更多工具。

在有了 MCP 之后，整个开发流程变成了：

• 大模型都适配 MCP 协议
• 各种工具都适配 MCP 协议

这样，一个新的工具出来，立刻可以为所有大模型可用，而一个新的大模型也可以立刻调用市面上公开的 MCP（下图）。

有人把这个比作 “AI 时代的 HTTP 协议”，我是比较认同的。

三、MCP 的实现细节

3.1 角色

不同于 HTTP协议的浏览器 / 服务器（B/S）架构，MCP 的协议多了一个 “主机” 的角色，一共包含三个角色，分别是：主机，客户端，服务器。

主机：创建和管理多个客户端。负责鉴权相关工作。负责多个客户端内容的聚合，

客户端：一个客户端是一个进程，负责与对应的 MCP 服务器交互数据，管理会话的状态。

服务器：为客户端提供服务。可以部署成本地服务或远程服务。

3.2 协议

MCP 使用 JSON-RPC 作为客户端与服务器通信的基础。

当服务器部署在本地的时候，它允许客户端用 stdio 的方式来传输 JSON 编码的数据。

当服务器部署在远程的时候，它使用 HTTP 来传输 JSON。

鉴权方面， 基于 stdio 传输实现的服务器直接从环境变量中读取授权凭证，而基于 HTTP 协议的服务器，基于 OAuth 2.1 实现授权。

四、如何开发 MCP

开发 SDK：MCP 支持任意语言开发 MCP 服务器，我们可以使用官方提供的 SDK 快速生成代码框架。

调试工具：官方提供的调试工具名为 MCP Inspector，用它连接对应 MCP 之后就可以在面板中调试功能。

发布 MCP：我们可以把开发好的服务发布到 MCP 市场上面供开发者检索到。

MCP 市场。市面上比较有名的市场包括：

• Anthropic 官方的 MCP Servers 仓库
• Smithery
• Glama

五、MCP 的问题

MCP 发布才一年时间，所以还有很多细节未来需要完善，包括：

• 协议对多模态内容支持不够友好
• 鉴权机制不完善，很多 MCP 服务还未支持 25 年 3 月引入的 OAuth 鉴权协议
• 安全防护能力弱。攻击者可以构造恶意的 MCP 服务来诱导用户执行恶意命令，从而实现信息窃取，执行恶意命令等攻击。

以上。

最近收到图灵编辑刘美英老师赠送的《图解 DeepSeek 技术》，全书只有不到 100 页，而且配套了大量插画，让原本让人生畏的大语言模型底层技术，变得不那么难懂。

本书非常适合对于大语言模型零基础的读者，作为入门书籍。以下是我的一些笔记。

缩放定律（Scaling law）

深度学习的底层原理其实缺乏科学论证，最终只能用“涌现”这种现象来描述我们观察到的实验结果。这个实验结果就是：当我们提高模型规模的时候，模型的表现也会越来越好。

于是，我们通过三个要素来提升模型的规模，分别是：参数量、数据量和计算量（如下图）

我对“涌现”的理解：这个世界上很多事情都是从量变到质变，大模型“涌现”出来的智能，再一次体现了这种自然界常见的现象。比如：

• 水在温度上升的时候，形态一直是液态，直到上升了 100 度，就开始沸腾，转化为气态。
• 股市，前期积累的泡沫越来越大，最后泡沫破灭的时候，就会一下子跌特别多。

我对缩放定律的理解：缩放定律在自然界中也非常常见，很多变化不是线性的，而是幂律（power law）的。比如：

• 财富的集中度。在美国前 10% 的人持有超过 90% 的财富。
• 公司的营收排名。排名每上升一名，营收可能是下一名的 2 倍。
• 明星或达人的收入。关注度每上升一位，收入可能翻翻。
• 28 原理。决定一件事情的最主要的 20% 因素，占据了 80% 的权重。

深度思考

缩放定律把大家的精力都集中在堆参数量和堆算力上，但是研究人员发现，如果让模型在输出答案的过程中进行“长思考”，答案会变得显著得好。于是，除了在训练阶段发力外，我们通过让模型在生成答案时消耗更多资源，来提升答案的质量。这就是现在变得普遍的“深度思考”模式（如下图）。

在我的理解下，深度思考模式类似于《思考快与慢》一书中提到的人类的慢思考。人类大多数时候，是用直觉来决策的，因为这样效率最高，而且直觉通常来源于大量的经验（预训练），通常情况下是对的。但是，对于一些重大的决策，人类就会启动慢思考（深度思考），会花大量的时间和精力来论证自己的想法是否正确，以保证重大决策的质量。

蒸馏（Distill）

DeepSeek-R1 是一个拥有 6710 亿个参数的庞大模型，这使得部署和使用它都需要强大的硬件支持。但是 DeepSeek 创新性的开创了将自己的推理能力蒸馏到别的小模型（比如 Qwen-32B）上的方法。

具体来说，研究团队用 DeepSeek 当老师模型，让 Qwen 当学生模型。当两个模型接收到相同的提示词后，均需要输出一个词元概率分布。在训练过程中，学生模型需要紧密跟随老师模型的分布特征（如下图）。

以上过程在 80 万个样本的训练下，这些小模型学会了 DeepSeek 的思维方式，与蒸馏前相比，能力有大幅的提升。

在我的理解下，这也非常类似人类的“师徒学习模式”。我在计算机行业，我们行业的毕业生刚进企业的时候，都会有一个导师（mentor）进行一对一指导。最终帮助我们这些职场小白快速融入行业，写出高质量的代码。

以上。

序

想读一些价值投资者的书，于是就找到了这本但斌的《时间的玫瑰》。这是一本写于 2018 年的书，现在已经过了 7 年。当年的很多论断，随着时间的检验会更有意思。以下是一些读书感悟。

买入价格很重要

我们常说，买股票需要关注三点：好公司，好管理，好价格。在好价格这件事情上，但斌给我们举了一个例子，也是他自己血泪教训。

但斌说：如果你在 2007 年的高点买入茅台，那么需要 2016 年（9 年后）才能解套。中间还会经历两次 60% 的下跌。所以，即便是大家公认的好公司，如果你的买入价格不对，也是有很大的风险。

关注行业周期

但斌的这本书写在 7 年前，在 7 前年，有一些行业龙头公司是被价值投资者普遍认同的，比如房地产行业的万科，以及教育行业的好未来，但斌在书中多次提到这两家公司。但是我们现在来看这两家公司，就会发现两家公司都经历了价值毁灭的过程，他们都从最高点回撤了超过 80% 。

万科股价：

好未来股价：

回撤的背后，是房地产行业和教育行业整体的低迷带来的。即便是三好学生，如果在一个下坡路的行业，也是做不出什么好成绩的。

关注行业的周期，关注政策的变化，在合适的时候卖出，这也是《股票大作手操盘术》中我很认同的趋势投资观点，在本书中，我再次感受到趋势投资的重要性。

从分歧中学习

但斌在书中提到他参加伯克希尔股东大会的一段记录：一个来自旧金山的 17 岁少年问：成为一个好的投资者的最好方法是什么？

巴菲特回答说：尽可能多地阅读。你要把各种思想装进你的脑子里，随着时间的推移，分辨出哪些是合理的。一旦你做到这样了，你就该下水实践了。

我对此也有很强的认同。学习的第一步是尽量吸收信息，而阅读是一个很好地吸收高质量信息的渠道。当然，我也认为与人交流讨论，以及观察现场同样重要，这都是获得信息多样性的重要手段。

有了信息之后，通过思考和实践来分辨信息，最终把有效的信息沉淀下来，就能成为自己的宝贵经验。

我对获取信息的方法最近还有一个新的感悟，就是“反对性”的意见相对重要，因为人会自我强化自己的观点，所以对于反对观点容易忽视。这个时候，我们应该刻意去找反对性意见，在理解反对性意见的基础上，去解释为什么观点不一样。

反对意见在投资上，也代表着市场的分歧，如果我们能够理解正反两边的观点的同时，又能够看到未来正反观点的分歧消除点，那么就可能获得巨大的收益。

之前我想要获得分歧意见非常难，因为表达反对意见通常让人感觉尴尬。现在我有一个技巧：我会问大模型，让他帮我系统性地总结反对意见以及论证理由，这对我来说非常好用，分享给大家。

以上。

上个月见了一个老朋友：代码家。和代码家聊天的时候，他提到了趋势交易，他还推荐了《股票大作手操盘术》。

该书的核心思想就是做趋势交易。具体做法是：在形成趋势前观望，在趋势确定建立后顺着趋势做空或做多，在趋势快要结束时，提前补仓或卖出。

我觉得该思想同样适用于长线操作：每家公司都有上升期和平稳期以及下降期。在公司上升期的时候加仓，平稳期的后期卖出，避免下降期的戴维斯双杀，会是非常重要的。

举例来说：

• 房地产公司的上升期投资，相关的股票，即便是恒大，也涨很多。只要你在合适的地方卖出，你就不会亏。

• 很多互联网公司的企业，在互联网泡沫期的估值很高。比如微博，哔哩哔哩，陌陌，包括粉笔公考，猿辅导。只要你在合适的地方卖出，也可以吃到很多的时代红利。但是如果你一直秉持长期持有，就可能不挣钱或者只挣很少的钱。

以下是微博的股价走势，现在的价格（12）比发行价（20）还低，但它曾经涨了 5 倍多。

以下是哔哩哔哩的股价走势，如果你买在高点，那么会亏 80%。

以上两个公司就是典型的“互联网”红利公司，在互联网红利期拥有巨大的股价泡沫，在红利结束的时候，股价回归理性。

我感觉趋势投资不是做短线的投机，而是把握时代的大势。做时代周期（5 年左右）的波段，抓时代红利企业，但是又很冷静，知道自己是投机，能看到卖出下车的时间点。

我们如果能够在互联网红利期，提前买入微博和哔哩哔哩这样的高用户量的产品。在红利结束前卖掉。我们假设卖在离最高点回撤 50% 的地方，也会有 2-4 倍的收益，整个持股周期在 2-3 年。

但说起来容易，执行起来还是挺困难的。比如下面是陌陌的走势，2014 年上市，2017 年股价才开始上涨，2018, 2019年均在年中大幅上涨，之后又回到 2017 年的价格。再之后就一路下跌，现在的价格是发行价的一半。

此书对我最大的价值，就是对价值投资与时代红利周期有了挂钩，之后在思考和判断公司的时候，除了思考价值层面的事情外，更应该思考时代的变化与周期。

以上。

一、序言

最近读完了梁宁的《真需求》，在我看来，梁宁的角色更像是一个老师，因为老师喜欢给学生结论。可能她最有名的作品就是得到 App 上的《产品思维 30 讲》，所以她喜欢给解决方案，给框架。

什么是解决方案？就是给你说某某成功的核心原因是什么，再围绕一系列核心原因建立一个理论上的框架，于是所有的成功就来自于这个框架。学生掌握了这个框架，就理解了所有的生意。

这，确实很符合很多人的需求。

在这本书中，梁宁的解决方案是：价值-共识-模式框架。

但是说实话，我不太喜欢将创业之路极简化的叙事。这种形式虽然易于理解，但是不解决实际问题。真实的企业经营每天面对各种复杂的决策和执行，不是有一个好的生意框架就能当银弹的。极简叙事也简化了成功企业的归因，容易误导读者。

我更喜欢的是能够落地的思维。比如段永平的“不为清单”，“长期主义”，“做正确的事情”，虽然有点像什么都没说，但是更易于落地。

所以，本书的大部分内容对我来说帮助不大，但是我从另外的视角也从书中得到了一些启发，分享如下。

二、情绪价值的产品很重要

梁宁把产品价值分为功能价值+情绪价值+资产价值。我不同意这样的分法，因为这么分不太 MECE（ 金字塔原理中的 MECE 原则，即 Mutually Exclusive Collectively Exhaustive）。

但是，我认为情绪价值是重要的商业产品。我的老板把这个叫做“无用之物”的生意。未来消费者会越来越关注自己，做悦己的选择，这方面的商业价值非常大。

三、从历史中思考

梁宁在书中问：如果你在 2012 年同时拿到当时的几个 offer，你应该如何选择？这几个 offer 是新浪微博，虎嗅，搜狐，微信，今日头条。

这是一个很有意思的问题，因为当时没几个人看得懂今日头条。就连投资机构都不投今日头条，更别说一个应届生会选择头条了。

但是这种思考角度让我意识到，其实这个世界的未知性是极强的，就算你是这个世界上最聪明的人，你也可能判断失误。

面对不确定性，构建好自己的反脆弱系统才是合理的应对方式。这事就像做资产配置一样，是我们应对变化和风险必须学会的生存技能。

以上。

序言

本书的作者是耶鲁大学的投资总监大卫·F·斯文森，他管理着耶鲁大学140多亿美元的捐赠资产，并让耶鲁大学在过去的20年里的年收益率达到16.1％。

书中的内容不是很好消化，所以我断断续续读了将近一年时间，里面的很多道理对我在投资领域的成长帮助很大。

我主要的收获有：

• 资产配置和再平衡的重要性
• 高费率基金的长期收益问题

下面就这两点结合我自己的个人经历做个分享。

资产配置和再平衡

资产配置可能是每个人学习投资的第一课。这一点很多人都能理解。把自己的钱分为两大部分，一部分保证自己和家人的生活质量不受影响，另外一部分长期不用的闲钱再拿来投资。

对于投资的钱，也应该做好配置。有人把它分成股票，债券，黄金，现金四大类。在书中，作者将核心资产分成了 6 种，分别是：

• 国内股票
• 国外发达市场股票
• 国外新兴市场股票
• 房地产
• 美国长期国库券
• 美国通胀保值国债

但作者在美国，以上核心资产很多在中国并没有有效对标的标的。能对标的可以是 A 股和港股通股票，房地产，债券，QDII 基金等。

我习惯拿石墨表格把自己的资产分类，然后再看各类型的比例。一些简单有用的原则是：任何单一资产不要让它的占比超过可投资资产的 30%。

我在这方面犯过一个巨大的教训，曾经有一个资产在一段时间涨幅特别猛。有一段时间它的占比超过了 30%，这个时候我不但没有减仓，还额外追加了一笔投资。追高操作最终使得这笔追加款后来跌幅将近 50%。整体的盈亏虽然不大，但是追加款的损失把之前积累的利润都抵消了。这本应该避免。

正确的做法是做资产的“再平衡”。

对于每一个资产，定下计划的投资占比。当某个资产涨幅超过了占比一定幅度，就应该卖出一部分，让它恢复到原始占比。

同样的，如果某一笔资产它的价格大幅缩水，那么我们应该补仓，让它的占比恢复到之前的比例。

但是，以上两种操作非常反人性。人性是追高杀跌，而不是追跌杀高。所以我一直在试图修炼自己在这方面的心智。

之前巨大的亏损对我来说也是一个宝贵的经验教训，让我谨记资产配置的重要性。

高费率基金的问题

我之前持有了一些私募基金，有一些亏钱有一些挣钱，我也不知道应该怎么评估这些投资行为。

本书系统性的将美国市场的共同基金做了长达几十年的收益分析和解读，最终让我意识到：高费率的基金是不值得长期持有的。

这类基金的主要问题是：

• 管理费和超额提成吃掉了一大部分收益
• 在市场整体大幅上涨的时候，收益提成也会吃掉一大部分 beta 收益
• 频繁通过高水位法提成，基金的波动就会让基金管理者挣钱，但是遇到深度回调的时候，这部分提成就会变成投资人的亏损
• 基金管理者旱涝保收，即便基金下跌，管理费也不会少。即便基金规模扩大很多，管理费也不会打折。

另外，很多人其实不知道，大部分基金用 份额缩减法 来收取管理费和提成。这样在产品业绩图上，投资人其实一眼看不到费后收益。

以下是我的一个真实案例：

我持有的名字为金锝睿知 1 期（T18145）的产品显示，从它的发行开始日 22.2.22 开始到 24.12.27，这段时间的收益率是 22.82%（如下图）

但是如果我查看我的资金流水，我的两年持有收益率只有 16.5%，差了 6.3%（如下图）

我不是说这只基金不好，实际上它在过去两年的收益还是远高于 A 股沪深 300 指数的。但是你确实没办法一眼在产品资料里面看到真实的年化费后收益率。当然，问题不是针对这一只基金，大部分私募基金都是采用份额缩减法。

意识到以上这些之后，我赎回了几乎所有整体费率大于 1.5% 的基金。转而更多持有低费率的指数基金。

另外我也买入了一些我觉得不错的个股，比如腾讯，招商银行，比亚迪。对这些个股的生意的思考也让我的商业思维得到进步。

小结

《不落俗套的成功》是一本面向个人投资者的启蒙读物，作者通过大量详细的数据说明资产配置、再平衡的重要性，也让我意识到高费率的基金不值得长期持有。

以上。

“免费的午餐往往是最贵的。为知识付费，是投资自己的认知能力，是这个时代每个人都应该认真考虑的选择。

序

前几天刷抖音，看到一个财经博主在讲”普通人如何实现财富自由”，视频里充满了夸张的表情和煽动性的文案。视频末尾，他推荐了一个”0元理财训练营”，声称能教你”三个月内资产翻倍”。

我想起了自己订阅《财新》时的犹豫。为什么我们对免费的低质量内容习以为常，却对高质量的付费内容如此吝啬？

这个信息爆炸的时代，我们真的需要为知识付费。

免费内容的陷阱

质量之殇

免费的内容最大的问题，就是它根本就不免费。

当我们在抖音上看到那些”三招教你理财”、”这样做就能年入百万”的短视频时，我们以为自己没有付出成本。但事实上，我们付出的是注意力，付出的是判断力，付出的是被误导的风险。

这些内容利用了人性中最原始的弱点：贪婪和猎奇。它们用夸张的标题吸引眼球，用简化的逻辑迎合认知懒惰，最终的目的不是传播知识，而是引流变现。

我记得罗振宇在《逻辑思维》中说过：”免费是世界上最昂贵的东西”。当时不理解，现在想想，免费内容的真实成本往往比付费内容更高，只是这个成本被巧妙地隐藏了。

注意力的谋杀

短视频平台更可怕的地方在于，它们正在系统性地破坏我们的专注力。

抖音上的财经内容，往往用夸张的配音、快节奏的剪辑，以及故意制造的冲突感来抓取注意力。”震惊！这家公司竟然…”、”你绝对想不到的赚钱方式”，这样的文案充斥着整个平台。

长期消费这样的内容，就像吃快餐一样，看似填饱了肚子，实际上营养不良。我们的大脑习惯了这种高刺激、低思考的信息输入方式，逐渐失去了深度阅读和独立思考的能力。

更要命的是，算法推荐让我们陷入信息茧房。平台为了让用户停留更长时间，会推送用户喜欢的内容，而不是用户需要的内容。结果是，重要的时政新闻、深度的社会分析被娱乐化的内容所淹没。

广告的毒药

隐藏的商业动机

最近几年，我观察到一个现象：几乎所有的免费财经内容，最终都指向商业变现。

公众号上那些分析经济形势的文章，看似专业，细读之后会发现，作者往往会推荐某个理财产品或者某个投资平台。文章的逻辑链条是这样的：经济形势不好 → 需要理财 → 推荐我的产品。

抖音上更直接。那些所谓的”财经大V”，视频内容是免费的，但最终目标是让你扫码进群，然后推销各种理财课程、股票软件，甚至是可疑的投资项目。

这种商业模式本身没有问题，但它扭曲了内容的客观性。当内容创作者的收入来源是推广费而不是内容质量本身时，内容质量必然会让位于商业转化。

算法的偏见

算法推荐进一步加剧了这个问题。

算法关心的是用户停留时间和点击率，而不是信息的准确性和重要性。一条耸人听闻的假新闻往往比一篇严谨的深度报道有更高的传播率。

结果是什么？真正重要的政治、经济、社会议题被娱乐化、碎片化的内容所遮蔽。当所有人都在关注某个网红的恋情时，有多少人知道最新的货币政策调整？当大家都在讨论某个段子时，有几个人了解正在发生的地缘政治变化？

这不是危言耸听。信息质量的下降最终会影响整个社会的决策质量。

付费的价值

面对这样的信息环境，我选择了用钱投票。

我的付费清单

去年开始，我陆续为以下内容付费：

• 《财新》杂志：每年几百块钱，但能获得相对客观、深度的财经报道
• 财经类每日新闻：每天需要花 1 块钱，信息密度高，没有广告干扰
• 《三联生活周刊》：优质的长篇报道，帮我理解复杂的社会现象
• 小宇宙上的访谈节目：深度对话，远比短视频更有营养
• 请一些行业专家咨询，事后发微信红包感谢

付费内容的优势

付费内容最大的优势在于，它的商业模式相对纯粹。

当我为《财新》的内容付费时，我就是《财新》的客户。《财新》需要对我的钱负责，需要提供有价值的内容来留住我。这种直接的商业关系，比那种”免费内容+广告变现”的模式要健康得多。

付费内容的第二个优势是质量控制。

以《三联生活周刊》为例，它的记者往往需要花费数月时间来调查一个选题，采访几十个相关人员，查阅大量资料，最终呈现出一篇万字长文。这样的内容制作成本很高，只有付费模式才能支撑这样的投入。

而免费的自媒体内容呢？往往是一个人坐在电脑前，花几个小时搜集网上的资料，拼凑出一篇文章。质量的差距是显而易见的。

一点反思

诚然，付费内容也不是万能的。

《财新》有时也会有立场偏见，《三联》有时也会有不够深入的报道。付费不能保证内容的完美，但它至少能保证内容制作者的基本动机是提供有价值的信息，而不是引流变现。

另外，并不是所有人都有条件为信息付费。这涉及到信息公平的问题，也是整个社会需要思考的问题。

但至少对于有条件的人来说，为高质量内容付费，不仅是为了获得更好的信息，也是在用消费选择来支持优质内容的生产，推动整个信息生态的良性发展。

结语

这是一个最好的时代，也是一个最坏的时代。

说它是最好的时代，是因为获取信息从来没有像现在这样便利。说它是最坏的时代，是因为信息质量从来没有像现在这样参差不齐。

在这样的环境下，为知识付费不是一种消费，而是一种投资。投资自己的认知能力，投资自己的判断力，投资自己的未来。

毕竟，在这个瞬息万变的时代里，唯一不变的就是变化本身。而应对变化的最好方式，就是保持持续学习的能力。

免费的午餐往往是最贵的。为知识付费，是这个时代每个人都应该认真考虑的选择。

题目描述

分析

此题首先是不能暴力枚举的，因为 n 和 m 最大情况下是 10^9，这个数据规模，暴力枚举肯定会超时。

然后我们可能想到贪心，但实际可落地的贪心的策略总是有特殊情况。

最后，假如我们可以检查一个答案是否可行，我们就可以用二分答案+判定的方法求解。

二分还有一个要求，就是答案是单调递增的。我们可以想像，随着兑换券的递增，如果限定 n 的值不变，那 m 的值肯定是递增的。所以此题符合单调递增的条件。

解法

那么，对于一个可能的答案 k，我们怎么检查答案是否可行呢？

• 我们先把 n 和 m 排序，让 n 是较大者，a 和 b 排序，让 a 是较大者
• 对于一份奖品，可以是 n-a, m-b 来获得，也可以是 n-b, m-a 来获得，我们让 d=a-b
• 因为 a 是较大者，所以当更换兑换方式的时候，n 的值从n-a变成了n-b，相对来说，增加了 d，m 的值减少了 d

所以：

• 我们可以先用第一个兑换方法，把 k 个奖品换成 c1=a*k 张课堂优秀券, c2=b*k 张作业优秀券
• 如果 c1 <=n, c2 <= m 那这个答案 k 显然就是可以的。
• 但如果 c1 > n，我们可以想到，把超额出来的兑换换成第二个兑换方法

具体如何换呢？

• 我们先计算超额的值，为 c1-n
• 每次兑换可以让这个值少 d，所以需要换 r=(c1-n)/d (向上取整) 即 r=(c1-n+d-1)/d个
• 经过如上的兑换，c1 的值减少了 d*r，c2 的值增加了 d*r

最后需要注意，因为 a*k 的范围可能超过 int，所以需要把计算过程都用 long long 来保存。

总结

此题考查了：

• 二分+判定的解法
• 向上取整的写法
• 数据范围的预估
• 时间复杂度的预估

这还是非常综合的一道题。对于没想到二分的学生，也可以用贪心或者暴力枚举骗到不少分（估计 10-15 分），所以此题也有相当的区分度，各种能力的学生都可以拿到部分分数。

详细代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

/*
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

long long n, m, a, b, d, ans;

bool test(long long k) {
    long long c1 = a*k;
    long long c2 = b*k;
    if (c1 > n) {
        long long r = (c1 - n + d - 1) / d;
        c1 -= r*d;
        c2 += r*d;
    }
    if (c1 <= n && c2 <=m) return true;
    else return false;
}

int main() {
    ios::sync_with_stdio(0);       
    cin >> n >> m >> a >> b;
    if (n < m) swap(n, m);
    if (a < b) swap(a, b);
    d = a - b;
    long long l = 0;
    long long r = n;
    while (l <= r) {
        long long m = (l+r)/2;
        if (test(m)) {
            ans = max(ans, m);
            l = m+1;
        } else {
            r = m-1;
        }
    }
    cout << ans << endl;
    return 0;
}

什么是“多巴胺”系统

“多巴胺”系统是一种隐喻，是指能够给你带来持续正反馈/正向情绪的事情。之所以用这个隐喻，一方面是想让大家更容易理解、记忆和传播这个系统。

这个系统对我来说非常重要，它就相当于我人生的“第一性原理”一样。人类看起来是自己的主人，但人类对自身行为动机的理解很多时候并不清楚。

马斯洛把人类的需求按层次来分，在他的理论中提到的各种需求：性，安全，食物，社交，自我实现等等。但是其实，这些其实本质上，都是在为人类提供“多巴胺”。

当人类失去了“多巴胺”系统，很多时候就宁愿放弃生命：比如在战争中，很多人为了信仰而牺牲自己。这是因为他内心的目标大于活着的意义。

在实际生活中，虽然不至于放弃生命，但冒着生命危险做的事情，也不鲜见。比如消防队员救人、警察和歹徒搏斗、或者体育健儿在赛场上带伤为荣誉而战。

这些行为虽然有可能失去生命，但是换来的荣誉与成就是非常让人自豪的，可以为自己提供终身的多巴胺来源。

有人说，这个世界上只有两种生意：让人爽的生意和让人牛逼（学习、健身等）的生意。但我觉得，这都是多巴胺的生意，差别只是一个是提供短期多巴胺，一个是提供长期多巴胺。学习这种事情虽然短期很辛苦，但是收获的成就是可以提供长期的回报，从而提供长期的多巴胺。

为什么“多巴胺”系统很重要

1、人对生活的意义有需求

看看全世界有多少人信教就明白了。大部分人都需要精神上为生命的存在赋予意义。意义感会驱使人们面对挑战和困难、提供情绪支撑、获得幸福感。

在中国，很少有人信教，但是我们每一个普通人也有自己对生命的追求，哪怕是更好一点的生活，或者一个遥不可及的理想，又或者是简单地照顾好家人和孩子。

人生的目标带动着每一个人在各种重大决策的十字路口上做选择。韩寒为了赛车辍学；赵心童为了台球远赴英国；崔永远为了自由表达离开了央视；而我身边，一个亲人为了更好的照顾孩子而放弃了工作上的晋升机会。

“多巴胺”系统就是为人生的意义提供基础能量的仓库，守护好多巴胺系统，人生之路就会走得更加从容。

2、“多巴胺”系统不容易构建

我们随便看看身边，就会发现无论是学习、工作，还是退休安排和日常生活。“多巴胺”系统的构建都是非常不容易的。

2.1 学习

拿学习来说，如果将孩子的“多巴胺”系统和学校排名、升学挂钩，那么很多孩子是无法构建学习的“多巴胺”系统的。因为每个班几十个孩子，必然有排在后面 50% 的孩子。这些孩子从排名上是无法获得正向激励的。

另外，整个学习是一个不断淘汰对手的游戏。中考会淘汰 50% 的学生分流到中专，高考又会分流 50% 的人到职高，大学又会分流 90% 的学生到非重点大学。研究生考试又会分流 2/3 的本科生，只剩下 1/3。

按上面的通过率，就算你是全中国前 1% 的学生，那大概也会止步于 985/211 的研究生入学考试。

所以，在学习上，你总会有一天会遇上身边的对手都比你强，你在这个小圈子里面排在后面，如果你和同学比的话，你能收获的只有负面的情绪，感觉自己像个废物。

后面我会提到如何构建学习的多巴胺系统。

2.2 工作

也许你是一个优秀的员工，不断获得奖励和提拔，但是随着环境和年龄变化，工作中持续获得正反馈是困难的。原因如下：

第一个原因：正向激励的比例太低。只有前 20% 的员工才能获得超过其他人的回报，大部分人只能拿到普通的绩效和待遇。

第二个原因：很多工作的经验积累并不是线性的。在积累 3-5 年后，新增加的经验不足以带来相应比例产出提升，这就造成老员工工资过高，性价比不足。拿 iOS 开发来说，工作 10 年和工作 30 年的开发者的经验差异在大部分情况下表现得并不明显，这就可能造成某些工作 10 年以上的老员工薪资涨幅变慢。

第三个原因：人在 30 岁以后，体力和学习速度逐渐下降。我今年 41 岁，熬夜的能力明显变差。而我在 30 岁的时候，经常熬夜加班。工作中的一些内容如果需要的是堆时间才能完成，老员工的完成速度就不及年轻的员工。

第四个原因：岗位架构是金字塔形的。越往上需要的人越少，所以一个员工很容易最终就停在某一个岗位无法获得上升机会，背后的原因可能仅仅是因为上面已经有人了，不需要更多管理者。

2.3 退休

退休是每个人必须面对的事情，如果不做好准备，“多巴胺”系统根本就不会自己产生。因为每个人退休后，日常生活的节奏就会有巨大变化。而人的时间是需要被填满的，否则就会因为意义感缺失而产生各种问题。

2.4 其它

其它的部分还包括，生活、家庭、理财等等：

• 对于生活：兴趣能否持续，影响“多巴胺”系统的稳定。
• 对于家庭：如何处理夫妻关系，亲子关系，婆媳关系，都关系到多巴胺系统的稳定。
• 对于理财：如果你买在顶峰，不但需要很长时间回本，也会承受巨大的账面亏损压力，给自己的多巴胺系统带来巨大冲击
• 对于伤痛：个人对伤痛，特别是心理层面上的伤痛处理也很重要，心理上的伤痛如果处理不好，就像应激的小猫一样，会给身体带来严重的伤害。

如何构建“多巴胺”系统

接下来，我就讲讲我对各种情况下构建“多巴胺”系统的心得。

1、对于学习

对于学习，我们需要刻意设计“多巴胺时刻”。让原来可能没有的多巴胺变得有，让原来分泌得少的多巴胺，变得分泌多。具体来说，我们可以：

一、定期回顾，肯定自己的进步。我每年都会写年度总结，之前觉得每年没有什么变化，但是总结的时候，发现还是有挺多进步的，这样就让自己更有成就感。

二、设立奖励，自我颁奖。不管是小的学习还是大的学习，都可以设立奖励。我在做竞赛题的时候，之前做完我就继续做下一题。但后来我发现，如果我每次做对，都挥舞一下手臂小小庆祝一下，就会开心很多。所以，即便是很小的自我肯定，都可以让多巴胺给我们更多激励。

三、适当分享，获得亲朋鼓励。人是社会动物，自己的成就还是要适当分享出来。但是对自己友谊不深的朋友就没太有必要，有可能会造成人家妒忌，或者人家会认为你是一个喜欢炫耀的人，没必要。

四、构建无限游戏，不要设置终点和上限。学习无止境，如果我们可以一直设立目标，就可以无限玩下去。对于生命来说，能够无限玩的游戏不多，学习算是一个。

2、对于工作

刚刚说过，随着环境和年龄变化，工作中持续获得正反馈是困难的。所以，对于工作，我们首先需要做的是降低预期。工作首先你是获得持续现金流的谋生手段；它如果能够给你持续的正向激励，当然很好，但是如果有一天，工作无法给你带来正反馈，那么你也可以就把它当作一份工作即可。

在工作上不要讲太多回报，公平。很多事情做了没有结果，但是公司付你钱了，所以你认真把事情做好，就很好，也很专业。

另外，在工作上，我们也需要尊重规律，做累进的事情。坚持在自己的专业领域积累经验，如果自己的年龄大了或者行业发展不好，也要接受工资不再上涨这些现实。

在工作上，我们还可以尝试杠铃策略，即：同时拥有两个不太相关的专业技能。通过在业余时间利用自己的爱好或者特长来发展副业，如果万一出现什么变动，自己的副业就可以成为主业，保证自己不至于失业。

3、对于退休

退休是人一辈子重要的规划之一，也是人生活法的重大转换。

对于退休，最重要的事情就是让提前规划好兴趣，让兴趣填满自己的时间。否则，人生一下子多了那么多时间，很容易觉得无聊。

这个兴趣最好是无限挑战游戏。这样可以几十年也做不完。

这个兴趣也最好可以锻炼到身体（例如：广场舞、摄影、骑行之类）。

最后，退休还有一个很重要的事情：要管好自己的钱，不冒大的风险，不折腾高风险的投资。因为挣太多钱自己也不一定能花完，但是如果亏很多就会影响自己的退休生活。

4、日常生活

日常生活中，有这些技巧可以带来更多的多巴胺：

一、主动给生活带来变化

我自己的经验是，主动做一些以前没做过的事情，会给生活带来新鲜感。比如：

• 我家每过几年就会尝试换个房子租，每次都有不同的体验。
• 每年出游几次，每次去不同的地方，让自己开眼界。
• 购物，看上什么东西就买买买。
• 庆祝。为自己的成绩庆祝，为朋友的成绩庆祝，为家人的成绩庆祝。

二、自立

不要太依赖别人，或者太依赖于某个工作，或者将自己放到一个困境，或者太陷入一个目标。这不是说我们应该不努力。对于生活，我们应该全情投入，把过程做好；但是对于结果，我们应该顺其自然。

三、终身学习

学习是少有的，可以持续给人带来获得感的事情。而且这个事情是没有终点的，属于一种“无限游戏”，这就让我们永远不会觉得无聊。

我最近因为兴趣又开始学习编程，遇到一个算法没看懂，我就慢慢想，可能想个一周，甚至两周，我感觉这才是一个学习的状态，就是慢慢的，不紧不慢的，学完一个再学下一个。

相对来说，学校的学习更像是一个工业化的人才产出器，每个人需要像机器一样在指定的时间学习完指定的内容，但是每个人的学习能力是不一样的，其实对每个人来说，匹配自己的学习速度才是最佳的学习方案。

四、关注过程，弱化结果

人生是一场体验，并非要留下什么，也留不下什么。

如果我们想想 100 年后谁能记得我们，我们会发现结论是：没有人。即使是自己的亲人，过了三代你可能也不会记得。大家可以想想，你知道你的爷爷的爷爷叫什么名字，长什么样，做过什么成绩吗？就算你记得，你的孩子以后会记得吗？

所以，如果人生到最后不会有任何人记得我们，那么我们人生的意义是什么？我认为核心的意义就是人生本身。就像《活着》中写道：活着就是最大的意义。

对于人生这种重过程，无结果的“游戏”，我们活在当下，关注过程，把自己的人生过好，就是一个非常棒的事情了。别的更多的结果，我们做不到，也没有什么意义。

5、对于家庭

对于家庭，最简单的获得多巴胺的方式是：低预期。比如：

对于家人，不要指望家人一定要为自己付出。家人能够不让你付出，就是超预期。有这样的心态，你每天都是超预期。

对于孩子也一样，低预期，不鸡娃。

• 孩子小的时候，我们只需要尽量培养孩子兴趣，兴趣是最大的老师，对于结果，则需要看孩子的天赋和运气，所以我们只能静待花开。
• 当孩子成年后，她会有自己的生活，作为父母也应该降低预期，孩子能活成什么样，最主要的还是靠孩子自己。
• 当我们老了后，也别指望孩子给自己养老，不啃老就不错了。有这样的低预期，也容易每天获得超预期的结果。

6、对于朋友

我认为有三种朋友，可以给我们提供持续的多巴胺。

• 一种朋友是相互帮助、支持的人。显然你们相互会收获很多。
• 一种是可以给你提供指导的前辈，牛人。你可以收获到成长。
• 一种是你可以给别人提供指导的后辈。你可以收获到成就感。

那哪些是消耗你多巴胺的朋友呢？

• 每次需要你的时候找你，但你需要他的时候总逃避的人。
• 和你话不投机，没有共同语言的人。
• 无法平等对话的人，有可能是对方太过强于你，懒得和你对话；也可能是对方太弱于你，你懒得和他对话。
• 让你感觉到有压力，但是除了消耗你多巴胺外，并不能给你带来任何其他好处的人。
• 你讨厌的人。
• 你嫉妒的人。

我有些时候，有点讨好型人格，就是不喜欢一个人，也不愿意和人家起冲突，很多时候碍于面子还是淡淡地交往。后来我发现这样不对，这完全是一种对多巴胺系统的伤害，想到这些我就主动断开了一些不喜欢的朋友的来往。其实有一些人是很优秀的，但是多巴胺系统为先的决策，让我还是会坚决断开联系。

7、对于伤痛

小孩子如果反复盯着糖果看，最后就会忍不住吃掉糖果。如果有人伤害了你，你反复回忆这个伤害的过程，你就会受到更多的内心部分的伤害。

著名作家蔡澜最近去世了，别人问他，他的爱人离他而去了，他是如何克服下来的。蔡澜说：你如果老去想这件事情，你就会发疯，所以我尽量让自己不去想这件事情。

芒格和巴菲特的公司之前特别看好一个接班人，后来这个接班人做了一些违背公司原则的事情，在收购一家公司前，自己私下提前买了这家公司的股票，自己获利了几百万美元。事情暴露之后，这个接班人辞职了。别人问芒格怎么看这个事情。

面对欺骗与背叛，芒格说：永远不要责备自己，永远不要有受害者心态。当你产生这种心态的时候，只会让你自己难受，不会带来任何其它正面的影响，因此你不应该花时间去感受它，哪怕是一秒钟。所以，更应该的心态是应对这种情况，为未来的不确定性做好准备。

芒格最后总结道：“I am not a victim. I am a survivor.”

所以，站在建立“多巴胺”系统的角度，任何只有负面效果的情绪都是不值得去强化和感受的。如果你忍不住，你可以尽量不去想它。更好的办法是像芒格那样，有一个更加强大的幸存者视角来看待所有的坏运气、灾难、欺骗与背叛。让这些负面情绪不影响自己的多巴胺系统。

8、不内耗和自恰

我后来发现，其他人讲的一些行事原则，在表达角度上虽然不一样，其实也是一样的道理。比如我们讲的“不内耗”原则。

内耗就是一种持续消耗“多巴胺”的心理行为。如果以构建“多巴胺”系统作为人生准则的话，我们会发现内耗没有任何效果。当我们面对不如意的时候，要么改变，要么适应，要么淡化，而内耗是一种既不改变，又不适应，又反复强化负反馈的行为。百害而无一利。

自恰的底层含义是：所有事情能够自圆其说，不矛盾，不冲突，自然也就不内耗了，不消耗多巴胺。

所以，人需要活得“自恰”，只有自恰才能睡好觉，持续获得多巴胺。

主观与客观

“多巴胺”系统有主观的部分，也有客观的部分。

一、主观部分

“多巴胺”系统对于个人内心是一种主观行为和感受，而不是一种客观描述和标准。所以，对于芒格来说，一个重要朋友的背叛不是对“多巴胺”系统的冲击；但换一个人，可能觉得天塌了，一辈子再难信任他人。

因此，我们更应该调整的是自我的行事方式和思考问题的角度，而不是改变其他人。我们可以远离那些影响我们“多巴胺”系统的人和事，但是当坏运气到来的时候，我们只能接受。

二、客观部分

当然，“多巴胺”系统在指导我们行为的时候，是让我们客观上在做具体的行为选择。通过行为选择让我们尽可能构建有利于我们产生多巴胺的外界环境。比如我刚刚提到的：提前规划退休生活、选择终身学习、多搞庆祝活动等。这些有利的环境不但不会消耗我们主观意志来维护多巴胺，还会给我们提供愉悦，贡献多巴胺。

小结

“多巴胺”系统是一种隐喻，是指能够给你带来持续正反馈/正向情绪的事情。我们通过：

• 主观上，调整自己的思考和看待事情的方式
• 客观上，搭建好能够持续供养自己多巴胺的外部环境

利用“多巴胺”系统，让自己的人生少一点内耗，少一点纠结，多一点平静，多一点快乐。

愿每个读者都能过好当下的每一天，谢谢！

GESP 1 级

大题核心考点

1 级主要考查分支和循环结构，所以大题的解法一般都是一个 for 循环，然后循环里面用 if 之类的条件判断做一些事情，最后再输出结果。其代码框架为：

1
2
3

// 循环结构, 例如 for ...
    // 判断条件
// 输出结果

拿 GESP202309 一级题目：小明的幸运数 来说，其核心代码是：

1
2
3
4
5
6
7
8
9
10

// 循环
for (int i = l; i <= r; ++i) {
    // 判断条件
    if (isLucky(i)) {
        // 累加
        ans += i;
    }
}
// 输出结果
cout << ans << endl;

另外一个例子，GESP202503 一级题目：四舍五入，核心代码：

1
2
3
4
5
6
7
8
9
10
11

// 循环
for (int i = 1; i <= n; ++i) {
    cin >> a;
    b = a%10;
    a = a/10;
    // 判断条件
    if (b <= 4) a = a*10;
    else a = a*10 + 10;
    // 输出结果
    cout << a << endl;
}

GESP 2 级

大题核心考点

考点一：双重循环

GESP 2 级相对 1 级，对循环结构的考查进行了加强，一般需要用双层嵌套的循环才能完成大题。有一类双层嵌套循环需要特别关注，就是模拟输出类，这一类题过去考过多次，包括：

• GESP202309，小杨的 X 字矩阵
• GESP202312，小杨的 H 字矩阵
• GESP202403，小杨的日字矩阵
• GESP202409，小杨的 N 字矩阵
• GESP202503，等差矩阵
• GESP202303，画三角形
• 样题，画正方形

以等差矩阵为例，其关键代码为嵌套的 for 循环，参考如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n, m;
int tu[55][55];
int main() {
    cin >> n >> m;
    // 嵌套的 for 循环
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << i*j << " ";
        }
        cout << endl;
    }
    return 0;
}

如果学生还是不熟悉，可以考虑如下更多的练习：

• 模仿 小杨的 X 字矩阵，输出 “又” 字，倒 “N” 字，“工” 字矩阵，“口”字矩阵
• 模仿 画三角形，输出 左对齐、右对齐的正三角形，倒三角形
• 模仿 等差矩阵，输出求和的矩阵，输出只有偶数的等差矩阵（奇数位填 *）

有一些时候，双重循环也不一定以输出图案的方式来进行考查，比如题目 B4356 202506 二级 数三角形 就是一个案例，参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int main() {  
    int n;
    int ans = 0;
    cin >> n;
    for (int a = 1; a<=n; ++a) {
        for (int b = a; b<=n; ++b) {
            if (a*b%2 == 0)
                ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

更多的练习题目如下：

• https://www.luogu.com.cn/problem/B3994
• https://www.luogu.com.cn/problem/B3995
• https://www.luogu.com.cn/problem/B3986
• https://www.luogu.com.cn/problem/B3988

解题思路

对于双重循环输出图形，解题的关键在于：分析图形所代表的序列。例如图形：

1
2
3
4
5

+---+
-+-+-
--+--
-+-+-
+---+

对应的序列是

• (1,1)(2,2)(3,3)(4,4)(5,5)
• (1,5)(2,4)(3,3)(4,2)(5,1)

然后，我们在做双重循环输出的时候，已经有两个序列 i 和 j，分别表示行号和列号。
我们可以分析 i 和 j 与我们需要输出的数据有什么关系，最后就会发现，规律是 i == j 或者 i+j == n+1

我们再看一个复杂的：

1
2
3
4
5

..#..
.#.#.
#...#
.#.#.
..#..

它对应的序列不太好找规律，我们可以用两个变量 a 和 b，分别表示每一行需要输出的 y 坐标。
刚开始 (a,b)=(3,3)，然后：

• 对于上半部分，每增加一行，a--, b++。
• 对下下半部分，每增加一行，a++, b--。

我们再看一些更复杂的：

1
2
3
4
5

..#....#..
.#.#..#.#.
#...##...#
.#.#..#.#.
..#....#..

或：

1
2
3
4
5

..#...#..
.#.#.#.#.
#...#...#
.#.#.#.#.
..#...#..

都可以用刚刚找到的思路来解决。

但对于更复杂的图形，就得再想办法，比如

• https://iai.sh.cn/problem/645
• https://iai.sh.cn/problem/634

这类题目需要根据题目的输出要求，思考问题拆解的办法，每道题的解法可能都不一样。

考点二：常用函数

2 级还会考一些我们经常会实现的函数。包括：

求素数函数

参考题目：GESP202306 找素数

1
2
3
4
5
6
7
8

bool isPrime(int a) {
    for (int i = 2; i*i <=a; i++) {
        if (a%i == 0) {
            return false;
        }
    }
    return true;
}

更多练习：

• P1217 回文质数 Prime Palindromes

求闰年函数

参考题目：GESP202503 时间跨越

关键代码：

1
2
3
4

bool isLeapYear(int year) {
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

把一个数的每一位数字拆分的写法

参考题目：GESP202406 计数

关键代码：

1
2
3
4
5
6
7
8

int count(int a, int k) {
    int ret = 0;
    while (a) {
        if (a%10 == k) ret++;
        a/=10;
    }
    return ret;
}

练习题目：

• GESP202409 数位之和
• B2078 含 k 个 3 的数
• B2081 与 7 无关的数
• B2152 分离整数的各个数
• B2154 数 1 的个数

GESP 3 级

选择、判断题核心考点

• 原码，返码，补码的表示
• 进制转换（二进制、八进制、十进制、十六进制）
• 位运算
• 字符串相关的操作

大题核心考点

考点一：字符串操作

3 级对字符串的操作要求非常高，需要考生灵活掌握字符串的变换、拼接、求子串、判断回文等操作。

求子串可以用 string 类的 substr(int pos, int len) 函数。需要注意该函数的两个参数分别是起始下标和长度。

其中，判断回文的写法如下：

1
2
3
4
5
6
7
8
9

bool isReverse(string &s) {
    int len = s.length();
    for (int i = 0; i < len/2; ++i) {
        if (s[i] != s[len-i-1]) {
            return false;
        }
    }
    return true;
}

以真题 GESP202409 回文拼接 为例，考生需要对字符串进行切分，然后分别判断是否是回文串。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n;
string s;

bool isReverse(string &s) {
    int len = s.length();
    for (int i = 0; i < len/2; ++i) {
        if (s[i] != s[len-i-1]) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    while (n--) {
        cin >> s;
        bool ans = false;
        if (s.length() >= 4) {
            for (int i = 2; i < s.length() - 1; i++) {
                string s1 = s.substr(0, i);
                string s2 = s.substr(i);
                if (isReverse(s1) && isReverse(s2)) {
                    ans = true;
                    break;
                }
            }
        }
        if (ans) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

该考点的相关真题：

• GESP202306 密码合规
• GESP202403 字母求和
• GESP202406 移位
• GESP202412 打印数字
• GESP202309 进制判断

其中 GESP202309 进制判断 看起来是考进制的规则，实际上也是考字符串的查找。参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int isRange(string s, string range) {
    for (int i = 0; i < s.length(); ++i) {
        char ch = s[i];
        int j = 0;
        for (j=0; j<range.length(); ++j) {
            if (ch == range[j]) {
                break;
            }
        }
        if (j == range.length()) return 0;
    } 
    return 1;
}

int main() {
    int n;
    string s;
    cin >> n;
    while (n--) {
        cin >> s;
        cout << isRange(s, "01") << " " 
             << isRange(s, "01234567") << " " 
             << isRange(s, "0123456789") << " " 
             << isRange(s, "0123456789ABCDEF") << endl;
    }
    return 0;
}

考点二：前缀和

前缀和的计算技巧是：用一个累加变量来不停地更新前 N 个数的和，这样我们只需要用 O（N）的时间复杂度，就可以把所有的前缀和求出来。

参考题目：GESP202409 平衡序列

此题解法是：暴力测试，先计算出总和 tot ，然后看前缀和的两倍有没有可能等于 tot。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int t, n, v[10010], tot;
int main() {
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--) {
        cin >> n;
        tot = 0;
        for (int i = 0; i < n; ++i) {
            cin >> v[i];
            tot += v[i];
        }
        int cnt = 0;
        bool ans = false;
        for (int i = 0; i < n && cnt*2<tot; ++i) {
            cnt += v[i];
            if (cnt*2 == tot) {
                ans = true;
            }
        }
        if (ans) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

考点三：位运算

考生需要熟悉二进制，以及数的位运算操作。

典型考题为：GESP202503 2025

此题的思路如下：因为 x 最大是 2025，而如果 y 需要影响 x 的运算，只能与 x 的 bit 位是 1 的位进行操作。所以 y 如果存在，则必定小于 2048。因为 2048 的二进制 1 的 bit 位已经超过 2025 的最高位了。所以直接枚举 1～2048 之间的答案即可。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <bits/stdc++.h>
using namespace std;

int ans = -1;
int x;
int main() {
    cin >> x;
    for (int i = 1; i < 2048; ++i) {
        if ((x & i) + (x | i) == 2025) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

GESP 4 级

大题核心考点

考点比较散，以下是历次考题的考点。

• GESP-202306 幸运数：模拟
• GESP-202309 进制转换：进制转换
• GESP-202309 变长编码：位操作
• GESP-202312 小杨的字典：字符串操作
• GESP-202312 田忌赛马：排序，模拟
• GESP-202403 相似字符串：字符串操作
• GESP-202403 做题：贪心
• GESP-202406 黑白方块：枚举
• GESP-202406 宝箱：枚举，二分
• GESP-202409 黑白方块：枚举
• GESP-202409 区间排序：排序
• GESP-202412 Recamán：枚举
• GESP-202412 字符排序：排序
• GESP-202503 荒地开垦：枚举
• GESP-202503 二阶矩阵：枚举
• GESP-202509 排兵布阵：枚举
• GESP-202509 最长连续段：排序

其中，比较常考的考点：

• 枚举：考了 7 次。
• 排序：考了 4 次。
• 字符串操作：考了 2 次。

GESP 5 级

大题核心考点

待补充

GESP 6 级

大题核心考点

最近公共祖先

• P10109 GESP-202312 六级 工作沟通
• P13016 GESP-202506 六级 最大因数

动态规划

包括 01 背包和完全背包：

• B3873 202309 六级 小杨买饮料
• P13015 202506 六级 学习小组
• P10721 202406 六级 计算得分

基础动态规划：

• P10108 202312 六级 闯关游戏
• P10376 202403 六级 游戏
• P11246 202409 六级 小杨和整数拆分

记忆化搜索：

• P10250 GESP样题 六级 下楼梯

复杂贪心：

• P11247 202409 六级 算法学习

其它

树状数组：

• B3874 202309 六级 小杨的握手问题

暴力枚举：

• P10377 202403 六级 好斗的牛

模拟+高精度：

• P11375 202412 六级 树上游走

相关练习题目

背包

从 这儿 可以获得洛谷上所有的背包相关题目，推荐练习的如下：

• P1734 最大约数和
• P1507 NASA的食物计划
• P1164 小A点菜
• P1060 NOIP 2006 普及组 开心的金明
• P1358 扑克牌
• P1877 HAOI2012 音量调节
• P1910 L 国的战斗之间谍
• P1926 小书童——刷题大军
• P1855 榨取kkksc03
• P2430 严酷的训练
• P1802 5 倍经验日
• P1757 通天之分组背包

GESP 7 级

大题核心考点

动态规划

背包：

• P13018 202506 七级 调味平衡

引言

有些时候，题目给我们 N 个元素的序列，然后让我们求前缀和或者区间和。并且，题目还会动态地修改这个序列的值。如果我们每次暴力求解前缀和，时间复杂度会是 O（N），而使用树状数组，可以将查询前缀和的复杂度降低到 O(LogN)。

树状数组是挺不好教学的一个知识点。它需要以下前置知识：

• 二进制表示法及熟练的位操作
• 前缀和的知识
• 树的基础知识
• 时间复杂度的估算

在教学的时候，我们的教学顺序如下：

• 先引入问题
• lowbit 函数讲解
• 树状数组的结构特点
• 利用树状数组求前缀和的方法
• 怎么修改树状数组的值
• 如何初始化树状数组
• 增加值或替换值
• 二维的树状数组

那么让我们来开始。

问题的引入

P3374 树状数组 1 是一道标准的树状数组问题：该题目给我们了一个数列，我们需要解决以下两个问题：

• 数列的区间求和
• 更新某一个数（加上 x）

我们很容易想到用暴力的方法来做此题。于是我们可以估计一下暴力的时间复杂度：

• 数列的区间求和，时间复杂度 O（N）
• 更新某一个数，时间复杂度 O（1）

题目中提到，求和的次数最多为 M 次，所以最坏情况下，时间复杂度为 O(M*N)。而由于 M 和 N 的最大范围为 5*10^5，所以最大运算次数高达 (5*10^5) * (5*10^5) = 2500亿次，而竞赛中估算 1000 万次的运算时间就接近 1 秒了，这个时间肯定会超时。

数列的区间求和有一个 O（1）的办法，就是提前求出前缀和。假如 Sum(i) 表示前 i 个数的和，那么区间 (i,j] 的和就可以通过 Sum(j) - Sum(i) 来得出。可惜的是，本题还有一个操作是更新某一个数。如果更新的是第一个数，那么整个前缀和数组 Sum 都需要更新，这样更新的时间复杂度会变成 O（N），最坏情况下会有 O(M*N)次更新，造成运算同样超时。

由此，我们需要一个更优秀的数据结构来解决这类问题，这就是树状数组。

lowbit 函数

在讲解树状数组前，我们先学习一下 lowbit 函数。

lowbit 函数实现的功能是：求 x 的二进制最低位 1 以及后面的 0 组成的数。例如：

• 8 (10 进制) = 1000 (2 进制) ，则 lowbit(8) = 8
• 9 (10进制）= 1001（2 进制），则 lowbit(9) = 1
• 10（10 进制）= 1010（2 进制），则 lowbit(10) = 2

所以，我们需要找到目标数的二进制中的最后那个 1 的位置。有两种实现方式：

方法一：x^(x-1) & x

方法一相对比较好理解，我拿二进制数 1100 举例解释如下：

• (x-1)的效果，相当于把二进制的最后一个1变成 0，比如某数 1100 减 1之后，就变成了 1011
• 这个时候，如果我用 x^(x-1),就会得到 1100^1011=0111
• 最后，用 x& 刚刚的 x^(x-1)，就相当于把x的最后一个1留下来了，前面的1都抹掉了：1100 & 0111 = 0100

方法二：x&-x

我们还是拿二进制数 1100 举例，由于负数是用补码表示，所以对于 1100，它的负数：

• 原码为：11100(最高为 1 为符号位)
• 反码为：10011(反码符号位不变，其余位取反)
• 补码为：10100（补码=反码+1）

这样一操作，x&-x 就等于 01100 & 10100 = 0100，同样把最后的 1 取出来了。

在实现中，我们用方法二的更多，因为更短。参考代码如下：

1
2
3

int lowbit(int x) {
    return x & -x;
}

树状数组的定义

对于一个长度为 N 的序列，为了满足上面提到的更快的区间求和和更新的需求，我们可以构造一个树状数组。

树状数组（Binary Index Tree，简称 BIT）通过构造另一个长度为 N 的数组，来做到：

• 区间求和，时间复杂度 O(log N)
• 更新某一个数，时间复杂度 O(log N)

因为树状数组需要另外创建一个长度为 N 的数组，所以它的空间复杂度为O(N)。

我们先创建出这个数组 b ，然后再引入它的元素间的树状逻辑关系。

我们有了数组 b，我们让数组 b 相对于原始序列 a，按如下的关系来保存范围和：

• b[1] 保存 a[1]的值
• b[2] 保存区间 [a[1], a[2]] 的和
• b[3] 保存 a[3]的值
• ….省略若干行
• b[8] 保存区间 [a[1], a[8]] 的和

我们先不管如何做到的，先假设我们按上面的逻辑，初始化好了这个数组，那么它怎么能快速求出前缀和呢？

树状数组求和

我们假设要求 a[1] ~ a[7]的和，如下图所示，我们知道这段和满足：Sum(7) = b[4] + b[6] + b[7]

那么，我们观察一下 b[4],b[6],b[7] 这几个下标有什么特点：

• 4 的二进制：0100
• 6 的二进制：0110
• 7 的二进制：0111

如果结合上我们刚刚教的 lowbit 函数，我们就可以发现如下规律：

• 4 的二进制：0100，4 = 6 - lowbit(6)
• 6 的二进制：0110，6 = 7 - lowbit(7)
• 7 的二进制：0111

于是，如果我们要求 Sum(7)，就可以用 b[7] 开始累加，然后用 7 - lowbit(7) 得到 6，再用 6 - lowbit(6) 得到 4，最后 4 - lowbit(4) = 0，就结束整个求和累加过程。

把以上逻辑转换成代码，是这样的：

1
2
3
4
5
6
7
8

int query(int range) {
    int ret = 0;
    while (range > 0) {
        ret += b[range];
        range -= lowbit(range);
    }
    return ret;
}

有人可能要问了，这个求和都是从序列开头开始的，如果我们想求序列中间一段，比如从 x 到 y 的区间和，应该怎么办呢？这种情况，我们可以：

• 用 query(y) 把从头到 y 位置的和求出来
• 用 query(x-1) 把从头到 x-1 位置的和求出来
• 然后相减 query(y) - query(x-1) 得到区间 [x,y] 的和

更新数据

树状数组也支持更新数据，像P3374 树状数组 1题目中要求的那样，我们可以将某个数加上 x，这种情况应该如何更新数组呢？

我们以更新 a[1]为例，通过观察，我们发现涉及 a[1] 的数组有：b[1],b[2],b[4],b[8]，如下图所示：

你有观察出来规律吗？这刚好是我们构建的这个树从叶子结点到根结点的一条路径。

那同样的问题来了，我们如何求解出b[1],b[2],b[4],b[8]这个路径呢？我们来观察一下：

• 1 的二进制是：0001
• 2 的二进制是：0010, 2 = 1 + lowbit(1)
• 4 的二进制是：0100, 4 = 2 + lowbit(2)
• 8 的二进制是：1000, 8 = 4 + lowbit(4)

我们再验证一个中间结点的更新，比如更新 a[5]，如下图所示：

我们看看规则是不是一样：

• 5 的二进制是 0101，
• 6 的二进制是 0110，6 = 5 + lowbit(5)
• 8 的二进制是 1000，8 = 6 + lowbit(6)

至此，我们总结出更新方法：从数列的下标 idx 开始，不停地更新，并且用 idx += lowbit(idx) 获得下一个更新的下标，直到更新到下标超过上界（N）为止。

1
2
3
4
5
6

void add(int idx, int val) {
    while (idx <= n) {
        b[idx] += val;
        idx += lowbit(idx);
    }
}

初始化

最暴力的初始化方法是：我们假设原序列全是 0，这样树状数组的初始状态也全是 0 即可正常表达上面的树型关系。然后，我们把每一个 a 序列中的数用更新的方式来放入树状数组中。

至此，我们完成了例题P3374 树状数组 1中的所有细节讨论，完整的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
#define MAXN (int)(500000+10)

int n, m;
int a[MAXN], b[MAXN];

int lowbit(int x) {
    return x & -x;
}

void add(int idx, int val) {
    while (idx <= n) {
        b[idx] += val;
        idx += lowbit(idx);
    }
}

int query(int range) {
    int ret = 0;
    while (range > 0) {
        ret += b[range];
        range -= lowbit(range);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <=n; ++i) {
        cin >> a[i];
        add(i, a[i]);
    }
    for (int i = 1; i <= m; ++i) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            add(x, y);
        } else {
            cout << query(y) - query(x-1) << endl;
        }
    }
    return 0;
}

但是，以上的这种初使化方法，时间复杂度为 O(N*logN)，如果数据刚好卡在初始化中，我们可以用以下这种方法来将初始化时间复杂度优化到 O(N)。

初始化（优化）

为了讲明白这种初始化，我们需要观察树状数组 b 中的每个元素代表的数据范围有什么规律。为什么 b[5] 只代表 a[5] 一个元素，但是 b[8]代表的是[a[1],a[8]] 区间的 8 个元素的和 ？

最终我们可以发现，一个数组元素代表的区间范围大小就是它的 lowbit 函数求出来的值。

例如：

• lowbit(5) = 1，所以它只代表 a[5] 一个元素
• lowbit(8) = 8，所以它代表 [a[1],a[8]] 共 8 个元素
• 一个十进制数 88，其二进制为 01011000，lowbit(88)=8，所以它代表的区间为 8 个元素。

进一步的，我们可以观察出，对于一个 b[x]，它代表的区间为[x-lowbit(x)+1, x]。

这对初始化有什么用呢？

• 我们如果构建了数组 a 的前缀和数组 s，s[i]表示前 i 个数的和。
• 那么，我们就可以用前缀和数组 s 来初始化 b[x]。

因为 b[x] 代表的区间和是[x-lowbit(x)+1, x],所以：b[i] = s[i] - s[i-lowbit(i)]

至此，我们可以将例题P3374 树状数组 1的代码更新如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
#define MAXN (int)(500000+10)

int n, m;
int a[MAXN], b[MAXN], s[MAXN];

int lowbit(int x) {
    return x & -x;
}

void add(int idx, int val) {
    while (idx <= n) {
        b[idx] += val;
        idx += lowbit(idx);
    }
}

int query(int range) {
    int ret = 0;
    while (range > 0) {
        ret += b[range];
        range -= lowbit(range);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <=n; ++i) {
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }
    // 初始化
    for (int i = 1; i<=n; ++i) {
        b[i] = s[i] - s[i-lowbit(i)];
    }
    for (int i = 1; i <= m; ++i) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            add(x, y);
        } else {
            cout << query(y) - query(x-1) << endl;
        }
    }
    return 0;
}

管辖区间

上面讲到，树状数组中的元素 b[x] 管辖的区间和是[x-lowbit(x)+1, x]，因此，我们更能理解树状数组的更新逻辑：

• 所谓的更新a[x]，就是把管辖区间涵盖 a[x] 的所有 b[x]都更新一遍。
• 那哪些 b[x]的管辖区间涵盖 a[x]呢？就是从二进制看，就是范围中有 lowbit(x) 的数。

举例来说，如果我们要更新 a[2] 的值，lowbit(2) 的值是 0010，所以，我们要更新：

• b[2], 因为 2 的二进制是 0010，管辖区间是 [1, 2]，宽度是 2
• b[4], 因为 4 的二进制是 0100，管辖区间是 [1, 4]，宽度是 4
• b[8], 因为 8 的二进制是 1000，管辖区间是 [1, 8]，宽度是 8

再举一个例子，如果我们要更新 a[5] 的值，lowbit(5) 的值是 0001，所以我们要更新：

• b[5]，因为 5 的二进制是 0101，管辖区间是 [5, 5]，宽度是 1
• b[6]，因为 6 的二进制是 0110，管辖区间是 [5, 6]，宽度是 2
• b[8]，因为 8 的二进制是 1000，管辖区间是 [1, 8]，宽度是 8

再举一个例子，如果我们要更新 a[7] 的值，lowbit(7) 的值是 0001，所以我们要更新：

• b[7]，因为 7 的二进制是 0111，管辖区间是 [7, 7]，宽度是 1
• b[8]，因为 8 的二进制是 1000，管辖区间是 [1, 8]，宽度是 8

通过上面的例子，我们可以看到，管辖区间在更新的过程中宽度是不断扩大的。不同的数，宽度扩大的倍数不同。但至少是每次翻倍的方式来扩大。

我们再从另一个角度来看管辖区间：我们把数状数组的第 1 个到第 56 个元素的二进制列出来，如下所示：

我们可以观察到：bit 为 1 的位置越低，管辖的区域越小，所以：

• 有一半管辖区域大小为 1 的数（图中为粉色）
• 剩下的一半，有一半管辖区域大小为 2 的数（图中为绿色）
• 再剩的一半，有一半管辖区域大小为 4 的数（图中为紫色）
• 再剩的一半，有一半管辖区域大小为 8 的数（图中为黄色）

再看这些数的间隔：

• 粉色的间隔是 2-1，每 2 个出现一次
• 绿色的间隔是 4-1，每 4 个出现一次
• 紫色的间隔是 8-1，每 8 个出现一次
• 黄色的间隔是 16-1，每 16 个出现一次

所以，其实树状数组是把区间和数据按分治的思想进行了切分，这样可以快速求和。

另外，从管辖区域的角度考虑，每一个数在进行 lowbit 减运算的时候，得到的新数，一定和之前的区间不是重叠的。我们可以这样证明：

• 每个元素 b[x] 管辖的区间和是[x-lowbit(x)+1, x]
• 我们令 y = x - lowbit(x), 则 b[y] 的管辖区间就是：[y-lowbit(y)+1, y],即：[y-lowbit(y)+1, x - lowbit(x)]
• 可以看到，这两个区间 [y-lowbit(y)+1, x - lowbit(x)] 和 [x-lowbit(x)+1, x]其实是相邻的。

所以，每次减 lowbit(x) 的运算，其实是获得了其左侧相邻的一块区间的和。

我们来看一个查询和的例子，如果我们要求前缀和 sum(7)：

• 我们先计算 b[7]，7 的二进制是 0111，管辖区间是 [7, 7]，宽度是 1
• 我们再计算 b[6]，6 的二进制是 0110，管辖区间是 [5, 6]，宽度是 2
• 我们再计算 b[4]，4 的二进制是 0100，管辖区间是 [1, 4]，宽度是 4

我们从上面的例子可以看到：由于每次减掉的都是最小的一个 lowbit 位，所以左侧相邻的新区间一定更宽。所以求和过程中， b[7],b[6],b[4] 对应的管辖宽度从 1 到 2 再到 4.

我们再看一个前缀和 sum(9) 的例子：

• 我们先计算 b[9], 9 的二进制是 1001，管辖区间是 [9, 9]，宽度是 1
• 我们再计算 b[8], 9 的二进制是 1000，管辖区间是 [1, 8]，宽度是 8

和我们刚刚得到的结论相同：求和过程中，随着不断地减 lowbit(x)，获得的新区间更宽。

小结：

• 树状数组中的元素 b[x] 管辖的区间和是[x-lowbit(x)+1, x]
• 每次加 lowbit(x) 的过程，相当于在不断扩展管辖区间。不同的数，宽度扩大的倍数不同。但至少是每次翻倍的方式来扩大。
• 每次减 lowbit(x) 的过程，相当于在查找紧临 b[x] 管辖区间的一块新区间。这个新区间，宽度也是不断扩大的。不同的数，宽度扩大的倍数不同。但至少是每次翻倍的方式来扩大。

差分数组

有些时候，题目会让我们一次更新一段区间，这个时候，我们可以引入差分数组来替代原数组。

差分数组中的每一个元素，是原数组相邻两个数的差。

例如：

• 原数组： 1,2,3,4,5,6
• 差分数组：1,1,1,1,1,1

我们对差分数组求前缀和，就可以还原出原数组。

这个时候，如果我们把原数组的第 3 个数到第 5 个数都加上 2，我们看看效果：

• 原数组： 1,2,5,6,7,6
• 差分数组：1,1,3,1,1,-1

我们观察到，原数组的一个区间都加上 2 之后，在差分数组那里，只有第 3 个数和第 6 个数有变化，其它都没有变化。所以，如果我们用差分数组来代替原数组，就可以只更新两个数值来代表原来的范围更新。

P3368 【模板】树状数组 2此题可以很好地练习差分数组与数状数组的结合运用，相关代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

/**
 * 差分：
 *  - 假设 A 序列为原序列
 *  - 差分数列 C 为原序列每两个数之间的差
 *    - 即：c[i] = a[i] - a[i-1]
 *         c[1] = a[1]
 *         c[2] = a[2] - a[1]
 *         c[3] = a[3] - a[2]
 *  - 所以：
 *    - a[i] = sum(c[1]+c[2]+...c[i])
 * 
 * 对于本题，如果把数组变成差分数组：
 *  - [x,y] 每个数加上 k，等价于:
 *    - c[x] += k
 *    - c[y+1] -= k
 *  - 求第 a[x] 的值，等价于：
 *    - sum(c[1]+c[2]+...c[x])
 *    - 即求前缀和
 * 
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
#define MAXN (int)(500000+10)

int n, m;
int a[MAXN], c[MAXN], b[MAXN];

int lowbit(int x) {
    return x&-x;
}

void add(int idx, int v) {
    while (idx <= n) {
        b[idx] += v;
        idx += lowbit(idx);
    }
}

int query(int range) {
    int ret = 0;
    while (range) {
        ret += b[range];
        range -= lowbit(range);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        c[i] = a[i] - a[i-1];
        add(i, c[i]);
    }
    while (m--) {
        int op, x, y, k;
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> k;
            add(x, k);
            add(y+1, -k);
        } else {
            cin >> x;
            cout << query(x) << endl;
        }
    }
    return 0;
}

二维的树状数组

刚刚讲到，对于一个 b[x]，它代表的区间为[x-lowbit(x)+1, x]

那么对于一个二维的树状数组 b[x, y]，它代表的区间就是 a(x-lowbit(x)+1, y-lowbit(y)+1) - a(x, y) 形成的矩阵的总和。如下图所示：

对于二维的树状数组，更新就需要用两层的循环了。示例代码如下：

1
2
3
4
5
6
7

void add(int x, int y, int v) {
  for (int i = x; i <= n; i += lowbit(i)) {
    for (int j = y; j <= m; j += lowbit(j)) {
      c[i][j] += v;
    }
  }
}

查询前缀和同样需要用循环，示例代码如下：

1
2
3
4
5
6
7
8
9

int query(int x, int y) {
  int res = 0;
  for (int i = x; i > 0; i -= lowbit(i)) {
    for (int j = y; j > 0; j -= lowbit(j)) {
      res += c[i][j];
    }
  }
  return res;
}

如果题目要求区间和，则需要用容斥原理来求解，这里不再展开介绍。

用树状数组求逆序对

什么是逆序对？逆序对是指一个序列中，a[i] > a[j] 且 i < j 的有序对。

比如一个序列是 3 2 1，它的逆序对就有：3 2,3 1,2 1 三组。

树状数组如何和逆序对的数量扯上关系呢？

拿序列 3 2 1 举例，我们知道，树状数组是可以用前缀和的。如果我们：

• 假设序列初始情况下为全 0
• 当处理第一个数 3 的时候，我们让树状数组的下标 3 加 1：update(3, 1)，同时记录插入了 1 个数
• 当处理第二个数 2 的时候，我们统计小于等于 2 的前缀和：query(2)，然后拿总数减 query(2)，得到大于 2 的数字数量
• 这个数量，就是当 2 被处理的时候，前面有一共多少个数大于 2，即与 2 能够组成逆序对的数量

例题：P1908 逆序对

在此题中，我们先要解决两个问题，才能借用上面的思想：

问题1、题中的数据范围太大，我们如何解决?

答案：我们可以用离散化的思想，把 2 10000 1 变成 2 3 1，因为逆序对是统计相对大小，所以这样更改之后，逆序对的数量是不变的。

具体如何离散化呢？我们可以将数据依次标记上编号，然后排序。例如：

• 原始序列为 100 200 50, 我们把它分别标上编号 (100,1), (200,2), (50,3)
• 然后我们将数值排序，得到：(50,3), (100,1), (200,2)
• 然后，我们再将新的序列赋上从 1 开始的编号：(50,3,1), (100,1,2), (200,2,3)
• 然后，我们再将序列按原来的编号(第 2 个数字）排序，得到 (100,1,2), (200,2,3), (50, 3, 1)
• 至此，我们转换得到了新的编号 2,3,1

因为 N 最多是 5*10^5，所以离散化之后，树状数组的大小也缩减到了 5*10^5

在实现的时候，我们可以用结构体来保存上面的三元组。

1
2
3
4
5

struct Node {
    int v;
    int origin_idx;
    int next_idx;
};

问题2、如果有两个相等的元素，会不会计算错误？

我们假设元素是 200 300 200,按我们刚刚的操作：

• 先标号，得到 (200,1) (300,2) (200,3)
• 再排序，得到 (200,1) (200,3) (300,2)
• 再标号，得到 (200,1,1) (200,3,2) (300,2,3)
• 再排序，得到 (200,1,1) (300,2,3) (200,3,2)
• 最后序列是 1,3,2

这种是没问题的，但是，如果我们排序的时候不是用的稳定排序，把第二个 200 排到了前面，就会得到 2,3,1，这样逆序对就会多一个 2 1，而这本来是不存在的。

所以，为了解决这个问题，我们可以用稳定排序stable_sort，或者保证排序的时候，值相同的情况下，标号大的在后面。

以下是完整的参考程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

#define MAXN (int)(5*1e5+10)

struct Node {
    int v;
    int origin_idx;
    int next_idx;
};
Node a[MAXN];
int n,c[MAXN];
long long ans;

bool comp1(const Node &a, const Node &b) {
    return a.v < b.v;
}

bool comp2(const Node &a, const Node &b) {
    return a.origin_idx < b.origin_idx;
}

int lowbit(int x) { return x&-x; }

void add(int a, int v) {
    while (a<=n) {
        c[a]+=v;
        a+=lowbit(a);
    }
}

int query(int a) {
    int ret = 0;
    while(a) {
        ret += c[a];
        a -= lowbit(a);
    }
    return ret;
}


int main() {
    cin >> n;
    for (int i = 1; i <=n; ++i) {
        cin >> a[i].v;
        a[i].origin_idx = i;
    }
    stable_sort(a+1, a+1+n, comp1);
    for (int i = 1; i<=n; ++i) 
        a[i].next_idx = i;
    stable_sort(a+1, a+1+n, comp2);

    for (int i = 1; i <=n; ++i) {
        add(a[i].next_idx, 1);
        ans += i - query(a[i].next_idx);
    }
    cout << ans << endl;

    return 0;
}

相关练习题目

文章中涉及的例题：

• P3374 树状数组 1
• P3368 树状数组 2
• P1908 逆序对

练习题：

B3874 小杨的握手问题

解题思路：

• 把学号为 a 的学生进入教室的行为，转化为第 a 个序列元素的值加 1。
• 这样，找出小于 a 的学生数量，就等价于求序列前 a-1 个元素的前缀和。
• 利用数状数组，就可以快速求前缀和了。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/**
 * 数状数组求逆序对。
 * 
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
#define MAXN int(3e5+10)

int n, b[MAXN];
long long ans;

int lowbit(int a) {
    return a&-a;
}

void add(int idx, int v) {
    while (idx <= n) {
        b[idx] += v;
        idx += lowbit(idx);
    }
}

int query(int range) {
    int ret = 0;
    while (range) {
        ret += b[range];
        range -= lowbit(range);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0); 
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        // 将学号下标从 0 开始改到 1 开始
        a = a + 1;
        ans += query(a - 1);
        add(a, 1);
    }      
    cout << ans << endl;
    return 0;
}

深度优先搜索（DFS）是学生学习算法的第一道门槛，因为它的主要形式是递归。而递归中需要将搜索的相关信息通过参数传递，这一点需要学生深刻理解 DFS。

模版

DFS 有比较标准的模版，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void dfs(int pt) // pt 表示层数
{
    if (终止条件) {
        // 处理
        return;
    }
    for (枚举这个层的所有可选项) {
        if（这个选项是合法的）{
            标记这个选项（保存现场）
            dfs(pt+1); 
            取消标记（恢复现场）
        }
    }
}

我们将运用该模版，完成后面的题目。

递归的深度

递归的时候，程序会占用栈空间来保存函数的环境变量。根据编译器以及编辑参数的不同，栈空间的大小也不同。通常情况下，竞赛中的编译器设定的栈空间为 8M 或者 16M。

假如，我们在一个递归函数中使用了 10 个 int 变量，那么每个递归函数就需要 4*10=40字节的栈空间。8M 一共可以支持 8*1000*1000/40=200000层调用。考虑到栈空间还需要保存当前函数执行的地址等变量，可供支持的调用层数会更小一点。

同学们也可以做如下的递归函数栈空间的测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int dfs(int x) {
    int test[9] = {0};
    cout << x << endl;
    dfs(x + 1);
    return 0;
}

int main() {
    dfs(0);
    return 0;
}

在我的本地，以上程序调用了约 13 万次后栈溢出。为了保险，我们在比赛中如果调用深度小于 1 万层，那应该是稳妥的；否则我们需要考虑是否用别的解法来解题。

教学和练习题目

P7200
P10483

P1219 八皇后 Checker Challenge

这是八皇后的变种，N 皇后问题。可以作为基础练习。具体解法是：

• 我们用变量 v[15] 表示每个皇后的列值。
• 对于新放入的皇后，我们依次检查它与前面的皇后是否在一条斜线上。检查方法是看其“横坐标差”与“纵坐标差”是否相同。检查函数如下：

1
2
3
4
5
6

bool check(int pt) {
    for (int i = 0; i < pt; i++) {
        if (abs(v[i] - v[pt]) == abs(i - pt)) return false;
    }
    return true;
}

完整的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n;
int v[15], ans;
bool flag[15];

bool check(int pt) {
    for (int i = 0; i < pt; i++) {
        if (abs(v[i] - v[pt]) == abs(i - pt)) return false;
    }
    return true;
}

void dfs(int pt) {
    if (pt == n) {
        ans++;
        if (ans <= 3) {
            for (int i = 0; i < n; i++) {
                cout << v[i] << " ";
            }
            cout << endl;
        }
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (flag[i]==false) {
            flag[i] = true;
            v[pt] = i;
            if (check(pt)) dfs(pt + 1);
            flag[i] = false;
        }
    }
    
}

int main() {
    cin >> n;
    dfs(0);
    cout << ans << endl;
    return 0;
}

P1036 选数

此题需要从小到大取数求和，然后再判断是否是素数。用递归的方式来进行枚举。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n, k, tot, ans;
int a[22], p[22];

bool isPrime(int v) {
    for (int i = 2; i*i <= v; ++i) {
        if (v%i == 0) {
            return false;
        }
    }
    return true;
}

void dfs(int pt) {
    if (pt == k+1) {
        if (isPrime(tot)) {
            ans++;
        }
    } else {
        // 每一层都必须取比前一层更大的下标，防止重复取
        for (int i = p[pt-1]+1; i <= n; ++i) {
            p[pt] = i;
            tot += a[i];
            dfs(pt+1);
            tot -= a[i];
        }
    }
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}

P1596 Lake Counting S

此题既可以用 DFS，也可以用 BFS。考虑到 N 和 M 最大值为 100，所以递归的层次最多为 1 万层，所以我们可以试试 DFS。

以下是参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
int n, m;
char tu[105][105];
int ans;
int movex[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int movey[8] = {1, -1, 0, 0, 1, -1, 1, -1};

void dfs(int x, int y) {
    tu[x][y] = '.';
    for (int i = 0; i < 8; i++) {
        int nx = x + movex[i];
        int ny = y + movey[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m 
            || tu[nx][ny] != 'W') continue;
        dfs(nx, ny);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> tu[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (tu[i][j] == 'W') {
                dfs(i, j);
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

P2036 PERKET

因为 N 最多为 10，每种食材可以选或者不选两种情况，所以最多情况数为 2^10=1024 种。搜索时间满足要求。

所以，此题用 DFS 可以非常方便解决。在搜索的时候，我们可以将食材的相关信息带到 DFS 函数的参数中，方便最后答案的求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n;
int s[11], b[11], v[11];
int ans = INT_MAX;

/**
 * pt: 当前处理到的食材
 * cnt: 当前选中的食材数量
 * ss: 当前选中的食材的总酸度
 * bb: 当前选中的食材的总甜度
 */
void dfs(int pt, int cnt, int ss, int bb) {
    if (pt == n) {
        if (cnt > 0) {
            ans = min(ans, abs(ss - bb));
        }
        return;
    }
    v[pt] = 1;
    dfs(pt + 1, cnt + 1, ss * s[pt], bb + b[pt]);
    v[pt] = 0;
    dfs(pt + 1, cnt, ss, bb);
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i] >> b[i];
    }
    dfs(0, 0, 1, 0);
    cout << ans << endl;
    return 0;
}

P12139 黑白棋

此题是搜索题，需要在中间尽可能检查状态来剪枝，以节省搜索次数。

题目有三类限制，分别可以用在不同的剪枝环节。

限制一：在每一行和每一列中，黑色棋子和白色棋子的数量必须相等（即为 3）。

• 我们可以对每一行记录黑子和白子的数量，如果某一行或某一列的一种颜色达到 3，后面则不能用这个颜色。

限制二：不能有超过两个相同颜色的棋子连续排列。

• 我们可以在当前落子的时候，检查它的左边和上面连续的几个格子，看是否有 3 个相同的子。

限制三：行列唯一性

• 可以放到最后检查。

另外，这个棋盘有几个位置已经设定了值，我们需要标记下来，搜索的时候跳过对这些位置的尝试，但需要在这些位置做合法性检查。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int row_cnt[6][2], col_cnt[6][2];
char tu[7][7], mark[7][7];

bool check(int r, int c) {
    // 在每一行和每一列中，黑色棋子和白色棋子的数量必须相等（即为 3）
    if (row_cnt[r][1] > 3 || row_cnt[r][0] > 3 || col_cnt[c][1] > 3 || col_cnt[c][0] > 3) return false;
    
    // 不能有超过两个相同颜色的棋子连续排列
    if (r >= 2) {
        if (tu[r][c] == '1' && tu[r-1][c] == '1' && tu[r-2][c] == '1') return false;
        if (tu[r][c] == '0' && tu[r-1][c] == '0' && tu[r-2][c] == '0') return false;
    }
    if (c >= 2) {
        if (tu[r][c] == '1' && tu[r][c-1] == '1' && tu[r][c-2] == '1') return false;
        if (tu[r][c] == '0' && tu[r][c-1] == '0' && tu[r][c-2] == '0') return false;
    }
    return true;
}

// 行列唯一性检查
bool final_check() {
    set<int> row_set, col_set;
    for (int i = 0; i < 6; i++) {
        int v = 0;
        for (int j = 0; j < 6; ++j) {
            v = v * 10 + (tu[i][j] - '0');
        }    
        row_set.insert(v);
    }
    if (row_set.size() != 6) return false;
    for (int j = 0; j < 6; ++j) {
        int v = 0;
        for (int i = 0; i < 6; ++i) {
            v = v * 10 + (tu[i][j] - '0');
        }
        col_set.insert(v);
    }
    if (col_set.size() != 6) return false;
    return true;
}

void dfs(int r, int c);
void try_dfs(int r, int c) {
    char ch = tu[r][c];
    row_cnt[r][ch - '0']++;
    col_cnt[c][ch - '0']++;
    if (check(r, c)) {
        int nr = r;
        int nc = c + 1;
        if (nc == 6) {
            nr++;
            nc = 0;
        }
        dfs(nr, nc);
    }
    row_cnt[r][ch - '0']--;
    col_cnt[c][ch - '0']--;
}

void dfs(int r, int c) {
    if (r == 6) {
        if (final_check()) {
            for (int i = 0; i < 6; i++) {
                for (int j = 0; j < 6; j++) {
                    cout << tu[i][j];
                }
            }
            cout << endl;
            // 因为只有一个合法解，所以找到答案就退出
            exit(0);
        }
        return;
    }
    
    if (mark[r][c] == 0) {
        tu[r][c] = '1';
        try_dfs(r, c);
        tu[r][c] = '0';
        try_dfs(r, c);
    } else {
        tu[r][c] = mark[r][c];
        try_dfs(r, c);
    }
}

void init() {
    memset(mark, 0, sizeof(mark));
    mark[0][0] = '1';
    mark[0][1] = '0';
    mark[0][3] = '0';
    mark[1][3] = '0';
    mark[2][4] = '0';
    mark[2][5] = '0';
    mark[4][2] = '1';
    mark[4][5] = '1';
    mark[5][1] = '0';
    mark[5][4] = '1';
}

int main() {
    init();
    dfs(0, 0);
    return 0;
}

P1605 迷宫

用 DFS 来枚举，但需要标记走过的路。

• 因为最多只有 5x5=25 个格子，所以递归的深度最大只有 25，不存在溢出情况。
• 因为有陷阱（不能走）和起点终点（不能重复走），所以我们假设平均每次有 2 条支路，
  整个的最坏情况估计只有 2^23=8388608 次，所以也不会超时。

一些陷阱：

• 终点可能也有障碍物，这个时候始终就到不了。
• 起点在走之前需要标记，否则会重复走。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <bits/stdc++.h>
using namespace std;

// 0 - 空地
// 1 - 障碍物
int tu[6][6], n, m, t, sx, sy, ex, ey, ans;

int movex[]={1,-1,0,0};
int movey[]={0,0,-1,1};

void dfs(int x, int y) {
    if (x == ex && y == ey) {
        ans++;
        return;
    }
    for (int i = 0; i < 4; ++i) {
        int tox = x + movex[i];
        int toy = y + movey[i];
        if (tox >=1 && tox<=n && toy>=1 && toy<=m && tu[tox][toy]!=1){
            tu[tox][toy]=1;
            dfs(tox, toy);
            tu[tox][toy]=0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> t;
    cin >> sx >> sy >> ex >> ey;
    while (t--) {
        int x, y;
        cin >> x >> y;
        tu[x][y] = 1;
    }
    tu[sx][sy] = 1;
    dfs(sx, sy);
    cout << ans << endl;
    return 0;
}

P2404 自然数的拆分问题

DFS，有两个技巧：

• 保证后面的数 >= 前面的数。
• 让每个数必须小于 n，这样不会出现 n=n 这种等式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n, tot, v[10];

void dfs(int pt) {
    if (tot == n) {
        cout << v[1];
        for (int i = 2; i < pt; ++i) {
            cout << "+" << v[i];
        }
        cout << endl;
        return;
    }
    for (int i = v[pt-1]; tot + i <=n && i < n ; ++i) {
        tot += i;
        v[pt] = i;
        dfs(pt+1);
        tot -= i;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    v[0] = 1;
    dfs(1);
    return 0;
}

STL 库是 C++ 语言的标准库，我们在比赛中主要用到的有如下内容。

string 类

• substr
• find
• replace
• insert
• erase
• c_str

容器

• pair
• vector
• deque
• list
• stack
• queue
• priority_queue
• map
• unordered_map
• set
• unordered_set

算法库

练习

P4387 验证栈序列

解法：把 A 数组中的元素住栈里面 push，然后如果栈顶元素和 B 数组的当前元素相同，就 pop，同时 B 数组的当前元素后移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int t, n, a[100010], b[100010];

int main() {
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; ++i) 
            cin >> a[i];
        for (int i = 0; i < n; ++i) 
            cin >> b[i];
        stack<int> q;
        int idx = 0;
        for (int i = 0; i < n; ++i) {
            q.push(a[i]);
            while (!q.empty() && q.top() == b[idx]) {
                q.pop();
                idx++;
            }
        }
        if (q.empty()) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

P1540 机器翻译

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int m, n, t, ans = 0;
    cin >> m >> n;
    vector<int> v; 
    while (cin >> t) {
        if (find(v.begin(), v.end(), t) == v.end()) { // 如果不在内存中
            v.push_back(t); 
            ++ans;
        }
        if (v.size() > m) 
            v.erase(v.begin());
    }
    cout << ans << endl;
}

P1449 后缀表达式

表达式计算:

• 不停读入。
• 如果读到数字，就和之前的数字拼接：a = a * 10 + ch - '0'
• 如果读到 . 就压栈
• 如果读到运算符，就出栈两个数进行运算，结果再压栈
• 如果读到 @ 结束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

stack<int> s;
int a, v1, v2;

int main() {
    char ch;
    while (cin >> ch) {
        if (ch == '@') break;
        if (ch >= '0' &&  ch <='9') {
            a = a*10 + ch - '0';
        } else if (ch == '.') {
            s.push(a);
            a = 0;
        } else if (ch == '+') {
            v1 = s.top(); s.pop(); v2 = s.top(); s.pop();
            s.push(v1 + v2);
        } else if (ch == '-') {
            v1 = s.top(); s.pop(); v2 = s.top(); s.pop();
            s.push(v2 - v1);
        } else if (ch == '*') {
            v1 = s.top(); s.pop(); v2 = s.top(); s.pop();
            s.push(v1 * v2);
        } else if (ch == '/') {
            v1 = s.top(); s.pop(); v2 = s.top(); s.pop();
            s.push(v2 / v1);
        }
    }
    cout << s.top() << endl;
    return 0;
}