在比赛中，我们经常会遇到看到题目一时想不到正解的情况。这时我们要做的并不是放弃题目启动扫雷，而是应该先从部分分的思路想起。因为许多题目正解的解题思路，就隐藏在部分分的解决方法中。 从部分分到正解 解决一道题目时，依照不同的部分分写不同复杂度的算法是 很简单的，这只是一个经验问题。今天要讲的是如何根据部分分（特殊情况），找到突破口，进而解决全部问题。 一般来讲，典型的部分分（特殊情况）的转...
在信息学的诸多题目中，凡是求解单调函数或单峰函数，总是离不开二分和三分两种相似的算法，那么这篇BLOG，就让我们学习一下二分和三分算法吧！ 应对单调函数的二分法 什么是二分法 二分法，顾名思义，就是把一个区间不断平分为两段的方法，其主要运用在求解单调函数上，比如下图，我们有个定义域在【l，r】上的单调递增函数f(x)，我要查询函数值为k的函数上的点的横坐标是多少，我们就可以查看一下f((...
提到NOIP高分的秘诀，不少人脱口而出的就是“暴力”。但是纯纯的暴力，也就是朴实无华的搜索肯定是无法通过大部分NOIP题目的（签到题当我没说），今天我们就从十道例题一起来学习一下搜索的艺术（为了提升学习效果，请阅读这篇BLOG的同学在阅读每道题思路之前自觉独立思考十分钟左右）。 题一 扑克牌 题目描述: 给你 n 张扑克牌，保证这 n 张来自于同一副（也就是说相同数字的牌不会超过四张）...
看了中山纪念中学宋新波dalao在NOI2018雅礼冬令营的分治算法后，大受启发，参考了一下dalao的PPT，下面就来讲一下神奇的分治算法的四种经典应用。 分治思想 分治(Divide-And-Conquer)就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。 其三个步骤如下： ①划分问题(D...