MoreRSS

site iconDevTang | 唐巧修改

博客 iOS 作者 编程 北京
iOS开发，孵化了 小猿搜题 和 小猿口算。斑马智能硬件业务负责人，带领团队研发的产品累计出货量超过 400 万台。著有《iOS 开发进阶》。
RSS: https://blog.devtang.com/atom.xml
请复制 RSS 到你的阅读器，或快速订阅到 :

Inoreader Feedly Follow Feedbin Local Reader

DevTang | 唐巧的 RSS 预览

GESP 202506 5级真题「奖品兑换」题解

2025-07-01 22:29:46

题目描述

分析

此题首先是不能暴力枚举的，因为 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;
}

构建你的“多巴胺”系统

2025-06-22 22:08:32

什么是“多巴胺”系统

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

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

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

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

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

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

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

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

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 核心考点

2025-06-06 22:12:03

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

以等差矩阵为例，其关键代码为嵌套的 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;
}

考点二：常用函数

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;
}

求闰年函数

参考题目：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 数位之和

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;
}

该考点的相关真题：

其中 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 二阶矩阵：枚举

其中，比较常考的考点：

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

GESP 5 级

大题核心考点

待补充

GESP 6 级

大题核心考点

最近公共祖先

动态规划

包括 01 背包和完全背包：

基础动态规划：

记忆化搜索：

复杂贪心：

其它

树状数组：

暴力枚举：

模拟+高精度：

GESP 7 级

大题核心考点

动态规划

背包：

CSPJ 教学总结：树状数组

2025-04-26 20:12:23

引言

有些时候，题目给我们 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;
}

相关练习题目

文章中涉及的例题：

练习题：

题目 描述
B3874 小杨的握手问题 GESP 202309 六级真题
- -

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;
}

CSPJ 教学总结：深度优先搜索（DFS）

2025-04-13 15:27:30

深度优先搜索（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 万层，那应该是稳妥的；否则我们需要考虑是否用别的解法来解题。

教学和练习题目

题目名 说明
P1036 选数 NOIP 2002 普及组
P1219 八皇后 Checker Challenge USACO 1.5
P1596 Lake Counting S USACO10OCT
P2036 PERKET COCI 2008/2009 #2
P12139 黑白棋 蓝桥杯 2025 省 A，写起来较繁琐
P1605 迷宫 标准的 DFS
P2404 自然数的拆分问题
P1019 单词接龙 NOIP 2000 提高组

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;
}

CSPJ 教学总结：STL

2025-04-12 22:00:46

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

string 类

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

容器

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

算法库

函数 调用示意 说明
sort sort(v.begin(), v.end()) 快速排序
stable_sort stable_sort(v.begin(), v.end()) 稳定排序
unique unique(v.begin(), v.end()) 去重，返回的是去重后的元素末地址。可以结合 erase 函数来把多余数据删除。参考代码：v.erase(unique(v.begin(), v.end()), v.end());
next_permutation next_permutation(v, v+n) 返回全排列的下一个值，当没有下一个排列时，函数返回 false
prev_permutation prev_permutation(v, v+n) 返回全排列的上一个值，当没有上一个排列时，函数返回 false
nth_element nth_element(v.begin(), v.begin() + k, v.end()), 函数执行后，v.begin()+k 位置的数为排序后的最终位置，即左边的数都小于它，后面的数都大于它
lower_bounds lower_bounds(v, v+n, a) 查找大于或等于 a 的第一个位置，如果没找到则返回 end()
upper_bounds upper_bounds(v, v+n, a) 查找大于 a 第一个位置，如果没找到则返回 end()
equal_range equal_range(v, v+n, a) equal_range 返回一个 pair，first 元素是查找到的匹配 a 值的左边界，second 元素是匹配到的 a 值的右边界，边界为左闭右开原则。当 first == second 的时候，相当于没找到目标值
__gcd __gcd(a, b) 返回 a 和 b 的最大公约数
reverse reverse(v.begin(), v.end()) 将原序列逆序
min_element min_element(v.begin(), v.end()) 返回的是地址，如果想要值，可以用 * 获得对应下标的值，如果想获得下标，可以让它减去 v.begin()
max_element max_element(v.begin(), v.end()) 返回的是地址，如果想要值，可以用 * 获得对应下标的值，如果想获得下标，可以让它减去 v.begin()
accumulate accumulate(v.begin(), v.end(), 0); 第三个参数是初始值

练习

题号 说明
P1996 约瑟夫问题 适合用 list
P3613 寄包柜 适合用 map 和 pair
P4387 验证栈序列 适合用 stack
P1540 机器翻译 NOIP 2010 提高组，适合用 vector 以及 STL 的 find 算法
P1449 后缀表达式 适合练习 stack
P2058 海港 NOIP 2016 普及组，练习桶和队列
P2234 营业额统计 练习 set 和 lower_bound 函数
P4305 不重复数字 可以练习 unordered_map 以及对比 cin 和 scanf 的速度差别

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;
}

P2058 海港

解法：用一个队列记录所有 24 小时内的船。用一个桶记录每个国家的乘客数量。

  • 每次有新船入队列的时候，更新桶。如果桶更新前是 0，则 ans++
  • 每次新船入队列后，检查最早的队列，如果超24 小时，则出队
  • 出队的时候，更新桶，如果桶的数量减为 0，则 ans-- 
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;

struct Node {
    int t;
    int len;
    vector<int> v;
};

// 桶，记录每个国家的乘客数量
int cnt[100010], n, t, ans;
// 队列
queue<Node> q;

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        Node a;
        cin >> a.t >> a.len;
        a.v.resize(a.len);
        for (int j = 0; j < a.len; ++j) {
            cin >> a.v[j];
            if (cnt[a.v[j]] == 0) ans++;
            cnt[a.v[j]]++;
        }
        q.push(a);
        int min_t = a.t - 86400;
        // 检查出列
        a = q.front();
        while (a.t <= min_t) {
            for (int j = 0; j < a.len; ++j) {
                cnt[a.v[j]]--;
                if (cnt[a.v[j]] == 0) ans--;
            }
            q.pop();
            a = q.front();
        }
        cout << ans << endl;
    }
    return 0;
}

P2234 营业额统计

把营业额往 set 里面放，这样数据就是有序的。然后用 lower_bound 查找大于等于 x 的值。

  • 如果找到了，那么波动就是 0
  • 如果没找到，比较当前位置和上一个位置与 x 的差，取较小那个；同时插入 x

取上一个位置的时候要处理一下边界，如果是在 s.begin()位置的话就不用处理了。

取当前位置的时候要处理一下，看看是不是在 s.end()。

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
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

set<int> s;
int n, x, ans;
bool debug = false;

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    cin >> x;
    ans = x;
    s.insert(x);
    for (int i = 1; i < n; ++i) {
        cin >> x;
        set<int>::iterator it;
        it = s.lower_bound(x);
        if (it != s.end() && *it == x) {
            continue;
        } else {
            int diff = INT_MAX;
            if (it != s.end()) {
                diff = min(diff, abs(*it-x));
            }
            if (it != s.begin()) {
                it--;
                diff = min(diff, abs(*it-x));
            }
            ans += diff;
            s.insert(x);
        }
    }
    cout << ans << endl;
    return 0;
}