原题链接1227. 分巧克力
题目难度：简单
题目来源：第八届蓝桥杯省赛C++ A/B组,第八届蓝桥杯省赛Java A/B/C组
题目描述儿童节那天有 K 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力，其中第 i 块是 $H_i \times W_i$ 的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
切出的巧克力需要满足：
形状是正方形，边长是整数
大小相同
例如一块 $6 \times 5$ 的巧克力可以切出 6 块 $2 \times 2$ 的巧克力或者 2 块 $3 \times 3$ 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入格式第一行包含两个整数 N 和 K。
以下 NN 行每行包含两个整数 $H_i$ 和 $W_i$。
输入保证每位小朋友至少能获得一块 $1 \times 1$ 的巧克力。
输出格式输出切出的正方形巧克力最大可能的边长。
数据范围$1 \le N,K \le 10^5$,$1 ...
原题链接99. 激光炸弹
题目难度：简单
题目来源：《算法竞赛进阶指南》, HNOI2003
题目描述地图上有 N 个目标，用整数 $X_{i}, Y_{i}$ 表示目标在地图上的位置，每个目标都有一个价值 $W_i$。
注意：不同目标可能在同一位置。
现在有一种新型的激光炸弹，可以摧毁一个包含$R \times R$ 个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 $x，y$ 轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式第一行输入正整数 N 和 R，分别代表地图上的目标数目和正方形包含的横纵位置数量，数据用空格隔开。
接下来 N 行，每行输入一组数据，每组数据包括三个整数 $X_{i}, Y_{i}, W_{i}$，分别代表目标的 x 坐标，y 坐标和价值，数据用空格隔开。
输出格式输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围$0 \le R \le 10^9 $$0 < N \le 10000$,$0 \le X_{i}, Y_{i} \le 5000...
原题链接796. 子矩阵的和
题目难度：简单
题目描述输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 $x_1, y_1, x_2, y_2$，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式第一行包含三个整数 n，m，q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含四个整数 $x_1, y_1, x_2, y_2$，表示一组询问。
输出格式共 q 行，每行输出一个询问的结果。
数据范围1≤n,m≤1000,1≤q≤200000,1≤x1≤x2≤n,1≤y1≤y2≤m,−1000≤矩阵内元素的值≤1000
输入样例：12345673 4 31 7 2 43 6 2 82 1 2 31 1 2 22 1 3 41 3 3 4
输出样例：123172721
题目分析对于一维的前缀和，就是求某一段的前缀和，这道题是二维数组中的前缀和，是求任意区域的数字之和
如果每一次询问都是暴力算的话，复杂度其实是极高的，因此同样的，我们还是需要用前缀和的做法
对于这个前缀和矩阵，其中的每...
原题链接789. 数的范围
题目难度：简单
题目描述给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围1≤n≤100000 1≤q≤10000 1≤k≤10000
输入样例：123456 31 2 2 3 3 4345
输出样例：1233 45 5-1 -1
题目分析这道题就是给了一个长度为n的排好序的数组，还有q次询问，对于每次询问，我们需要返回这个元素的起始位置和终止位置
由于这个数组是已经排好序了的，那么我们要寻找的元素必然是挨在一起的
这道题其实有很多做法，我们这里主要讲使用二分的做法
n是数组长度，所...
原题链接790. 数的三次方根
题目难度：简单
题目描述给定一个浮点数 n，求它的三次方根。
输入格式共一行，包含一个浮点数 n。
输出格式共一行，包含一个浮点数，表示问题的解。
注意，结果保留 6 位小数。
数据范围−10000≤n≤10000
输入样例：11000.00
输出样例：110.000000
题目分析这道题就很简单了，就是给我们一个数求他的三次方根，首先三次方根的函数图像如下
他的图像是具有单调性的，因此可以使用二分法进行逼近
我们确定一个区间范围，最大的范围就是在负一万到正一万之间，之后逐渐缩小
对于这个判断条件，其实可以选择小于等于目标值也可以取大于等于目标值，我们只需要每次取中点，自乘三次，与输入值比较即可，如果大于等于，说明M取大了，要将右端点缩小，如果小于等于，说明M取小了，将左端点向右移动即可
补充，这里对于浮点数的等于比较，受限于精度，我们只要求他的差值小于某一个极小的数，则认为他们两个数相等
示例代码12345678910111213141516171819#include<iostream>#include<cmath&...
二分二分法是我们在高中数学就学习过的一种思想，他也是一种效率较高的查找算法，在编写代码的过程中，初学者很容易就会陷入死循环
二分的基本步骤如下
第一步是需要确定一个区间，使得我们的目标值一定是在区间中出现的
第二步需要确定一个性质，使得这个性质满足两点，第一点是可以根据这个性质把这个区间分为左和右连续的两段，第二点是我们最终的答案一定是二分的某一个分界点（绝大多数）
整数二分是很容易出现死循环的一种情况，因为整数是离散的，因此对应的答案在边界的情况也是两种
其实相对应的，我们也可以将二分分为两大类，一种是答案在左边的终点，另一种是答案在右边的起点
我们来具体看一下这两种问题是如何二分的
第一类目标值在红色区间的右端点
我们把区间进行标注，如图
M是L和R的中点，其实就把区间[L,R]分成[L,M-1]和[M,R]
分成两段之后，我们只需要判断M的颜色(性质)，如果是在红色区间，就说明目标值一定在绿色区间[M,R]内，否则说明目标值在红色区间[L,M-1]内
对应到代码上，我们可以这样写
12345678while (L < R){ M = (L + R ...
原题链接116. 飞行员兄弟
题目难度：简单
题目来源：《算法竞赛进阶指南》
题目描述“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 16 个把手的冰箱。
已知每个把手可以处于以下两种状态之一：打开或关闭。
只有当所有把手都打开时，冰箱才会打开。
把手可以表示为一个 4×4 的矩阵，您可以改变任何一个位置 [i,j] 上把手的状态。
但是，这也会使得第 i 行和第 j 列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式输入一共包含四行，每行包含四个把手的初始状态。
符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式第一行输出一个整数 N，表示所需的最小切换把手次数。
接下来 N 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。
注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。
数据范围1≤i,j≤4
输入样例：1234-+-----------+--
输出样例：123456761 11 31 44 1...
原题链接1208. 翻硬币
题目难度：简单
题目来源：第四届蓝桥杯省赛C++B组
题目描述小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：**oo***oooo
如果同时翻转左边的两个硬币，则变为：oooo***oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。
输入格式两行等长的字符串，分别表示初始状态和要达到的目标状态。
输出格式一个整数，表示最小操作步数
数据范围输入字符串的长度均不超过100。数据保证答案一定有解。
输入样例1：12**********o****o****
输出样例1：15
输入样例2：12*o**o***o****o***o**o***
输出样例2：11
题目分析这个题就类似于之前的费解的开关的题目，每次翻硬币会同时带动两个硬币，问最少需要多少次到达目标状态
这一类问题其实是有一个固定形式的，是给定初态和末态，然后...