原题链接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
题目分析这个题就类似于之前的费解的开关的题目，每次翻硬币会同时带动两个硬币，问最少需要多少次到达目标状态
这一类问题其实是有一个固定形式的，是给定初态和末态，然后...
原题链接1209. 带分数
题目难度：简单（我感觉挺难的）
题目来源：第四届蓝桥杯省赛C++B/C组,第四届蓝桥杯省赛JAVAA/B组
题目描述100 可以表示为带分数的形式：$100 = 3 + \frac{69258}{714}$
还可以表示为：$100 = 82 + \frac{3546}{197}$
注意特征：带分数中，数字 $1 \sim 9$ 分别出现且只出现一次（不包含 0）。
类似这样的带分数，100 有 11 种表示法。
输入格式一个正整数。
输出格式输出输入数字用数码 $1∼9$ 不重复不遗漏地组成带分数表示的全部种数。
数据范围$1 \le N < 10^6$
输入样例1：1100
输出样例1：111
输入样例2：1105
输出样例2：16
题目分析这个题目的理解是比较简单的，就是将一共数字分解成一个整数加一个分数的形式，这里可以形式化的理解为将数字n分解为$n = a + \frac{b}{c}$的形式，需要注意的是b除c并不是整除，在a、b、c中需要出现数字1到9
数据范围是到10的...
原题链接93. 递归实现组合型枚举
题目难度：简单
题目来源：《算法竞赛进阶指南》
题目描述从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
输入格式两个整数 n,m 在同一行用空格隔开。
输出格式按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。
数据范围n>0 ,0≤m≤n ,n+(n−m)≤25
输入样例：15 3
输出样例：123456789101 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
思考题：如果要求使用非递归方法，该怎么做呢？
题目分析这道题和我们之前做到指数类型枚举和排列类型枚举有一定的相关性
组合类型的枚举指的是从n个数中选取m个数，不考虑顺序
首先考虑在手算情况下是如何确保不重不漏的枚举出所有情况的，例如从1到5这5个数字中选取3个数字，一种比较容易想到的方法就是，优先取最小的数...