#include <iostream>
#include <iomanip>  // 用于设置输出格式
using namespace std;double a, b, c, d;// 定义方程 f(x) = ax^3 + bx^2 + cx + d
double fc(double x) {return a * x * x * x + b * x * x + c * x + d;
}int main() {double l, r, m, x1, x2;int s = 0;// 输入系数 a, b, c, dcin >> a >> b >> c >> d;// 循环遍历区间 [-100, 100]for (int i = -100; i < 100; i++) {l = i; r = i + 1;x1 = fc(l); x2 = fc(r);// 如果左端点是根，直接输出if (x1 == 0) {cout << fixed << setprecision(2) << l << " ";s++;}// 判断区间内是否有根if (x1 * x2 < 0) {// 使用二分法找到根while (r - l >= 0.001) {m = (l + r) / 2;  // 计算中点if (fc(m) * fc(r) <= 0)l = m;elser = m;   // 缩小区间}cout << fixed << setprecision(2) << r << " ";s++;}// 如果已经找到3个根，则退出if (s == 3)break;}return 0;
}

 遍历区间，寻找零点

    // 循环遍历区间 [-100, 100]for (int i = -100; i < 100; i++) {l = i; r = i + 1;x1 = fc(l); x2 = fc(r);

• for (int i = -100; i < 100; i++)：循环遍历区间 [−100,100]，每次选择一个整数区间 [i,i+1]。
• l = i; r = i + 1;：设置当前的区间为 [i,i+1]。
• x1 = fc(l); x2 = fc(r);：计算区间两端点的函数值 f(l) 和 f(r)。

判断区间内是否有根，使用二分法逼近 

        // 判断区间内是否有根if (x1 * x2 < 0) {// 使用二分法找到根while (r - l >= 0.001) {m = (l + r) / 2;  // 计算中点if (fc(m) * fc(r) <= 0)l = m;elser = m;   // 缩小区间}cout << fixed << setprecision(2) << r << " ";s++;}

• if (x1 * x2 < 0)：如果区间端点的符号相反，即 f(l) 和 f(r) 的乘积小于 0，说明区间内有根。根据 中值定理，如果一个连续函数在区间的两端有不同的符号，那么区间内必定存在一个根。

• while (r - l >= 0.001)：使用二分法缩小区间，直到区间的宽度小于 0.001。这里 0.001 是控制精度的阈值。

• m = (l + r) / 2;：计算区间的中点 m。

• if (fc(m) * fc(r) <= 0)：检查中点和右端点的函数值符号，如果符号相反，根在左半区间，将左端点更新为中点 l = m；否则，根在右半区间，将右端点更新为中点 r = m。

• cout << fixed << setprecision(2) << r << " ";：输出右端点（即当前区间的一个近似根），保留两位小数。

• s++：增加根计数器。

---

 

这个问题的核心思想是通过计算每个士兵的路径上经过的最大伤害值来安排士兵的行进路线，最终我们需要找到最小的最大伤害代价。换句话说，我们希望找到一种路径，使得所有士兵的最大伤害值最小。

思路：

1. 问题转化为路径的最大值问题：

   • 每个士兵从第 1 行任意一个单元格出发，最终到达第 n 行的每个单元格。每个士兵的路径是从上到下的，路径上经过的最大伤害值决定了这个士兵的伤害值。
   • 我们希望通过合理分配路径，找出所有路径中的“最大伤害值”中的最小值。

2. 关键分析：

   • 由于我们关心的是路径上的最大伤害值，因此可以将问题转化为：对于一个给定的最大伤害值 xxx，判断是否可以找到一种方式，使得所有的士兵从第 1 行到达第 n 行，同时路径上的最大伤害值都不超过 xxx。
   • 这个问题可以通过 二分法 进行优化，搜索最小的最大伤害值。

3. 二分法+BFS/DFS判断可行性：

   • 使用二分法确定可能的最小最大伤害值。
   • 对于每个中间值 xxx，通过广度优先搜索（BFS）或者深度优先搜索（DFS）来判断从第 1 行到第 n 行是否可以找到一条路径，路径上的最大伤害值不超过 xxx。
   • 如果可以找到路径，说明当前伤害值是可行的，继续尝试更小的值；否则，增加伤害值。

解法步骤：

1. 初始化：

   • 读取输入，并建立一个 n×m 的伤害矩阵 p。

2. 二分查找：

   • 设置伤害值的搜索范围为 0 到 max(p)，然后进行二分查找。

3. 广度优先搜索（BFS）判断可行性：

   • 对于每个中间值 xxx，我们用 BFS 检查从第 1 行到第 n 行是否存在路径，并且路径上的最大伤害值不超过 xxx。

4. 输出最小的最大伤害值。

代码实现：

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>using namespace std;struct Point {int x, y;
};int n, m;
vector<vector<int>> p;  // 储存伤害值
vector<vector<bool>> visited;bool canReach(int maxDamage) {queue<Point> q;visited.assign(n, vector<bool>(m, false));// 将第 1 行的所有位置加入队列for (int j = 0; j < m; ++j) {if (p[0][j] <= maxDamage) {q.push({0, j});visited[0][j] = true;}}// 四个方向：上、下、左、右int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};while (!q.empty()) {Point cur = q.front();q.pop();// 如果到了最后一行，说明找到了一条有效路径if (cur.x == n - 1) {return true;}// 探索相邻的四个方向for (auto& dir : dirs) {int nx = cur.x + dir[0], ny = cur.y + dir[1];if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && p[nx][ny] <= maxDamage) {visited[nx][ny] = true;q.push({nx, ny});}}}return false;
}int main() {cin >> n >> m;p.resize(n, vector<int>(m));// 读入伤害矩阵for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> p[i][j];}}// 二分查找最小的最大伤害值int left = 0, right = 1000; // 最大伤害值范围为 [0, 1000]int answer = right;while (left <= right) {int mid = left + (right - left) / 2;if (canReach(mid)) {answer = mid;right = mid - 1;  // 尝试找到更小的最大伤害值} else {left = mid + 1;  // 增加最大伤害值}}cout << answer << endl;return 0;
}

代码解释：

1. 输入读取：

   • 通过 cin 读取迷阵的大小和伤害值矩阵。

2. canReach 函数：

   • 给定一个最大伤害值 maxDamage，通过 BFS 判断是否可以找到一条从第 1 行到第 n 行的路径，使得路径上所有房间的伤害值都不超过 maxDamage。
   • 如果找到路径，返回 true，否则返回 false。

3. 二分查找：

   • 我们对伤害值进行二分查找，初始范围为 [0, 1000]，中间值 mid 表示当前尝试的最大伤害值。
   • 对于每个中间值，使用 canReach 函数检查是否可行。如果可行，尝试找到更小的最大伤害值，否则增加伤害值。

4. 输出结果：

   • 最终的 answer 是最小的最大伤害值，即部队受到的最小伤害代价。

---

 

 

#include<iostream> // 包含输入输出流库
using namespace std; // 使用标准命名空间// 二进制幂取模函数
// a: 底数
// b: 指数
// p: 模数
long long binpow(long long a, long long b, long long p) {long long res = 1; // 初始化结果为1while(b > 0) { // 当指数大于0时循环if(b & 1) // 如果当前指数的最低位是1res = (res * a) % p; // 更新结果a = (a * a) % p; // 更新底数b >>= 1; // 指数右移一位，相当于除以2}return res; // 返回最终结果
}int main() {long long a, b, p; // 定义长整型变量a, b, pcin >> a >> b >> p; // 从标准输入读取a, b, p的值// 输出a的b次幂取p的模的结果cout << a << "^" << b << " mod " << p << "=" << binpow(a, b, p) << endl;return 0; // 程序正常结束
}

---

 

#include<iostream>
#include<vector>
#include<string>
using namespace std;// 递归函数：将整数n转化为2的幂次方的表示
string powering(int n) {// 基本情况：当 n 为 0 时，返回 "0"if (n == 0) return "0";// 用来存储所有二进制位为1的幂次方vector<int> powers;// 遍历二进制位，找出所有为1的位for (int i = 0; (1 << i) <= n; i++) {if (n & (1 << i)) {  // 判断第 i 位是否为 1powers.push_back(i);  // 如果为 1，则记录该位的幂次方}}// 用于存储最终的结果表达式string result = "";// 从高位开始处理幂次方for (int i = powers.size() - 1; i >= 0; i--) {int power = powers[i];  // 获取当前的幂次方if (power == 0) {// 对于 2^0，直接用 "2(0)" 表示result += "2(0)";} else if (power == 1) {// 对于 2^1，直接用 "2" 表示result += "2";} else {// 对于大于 2^1 的幂次方，递归调用powering生成子表达式result += "2(" + powering(power) + ")";}// 如果当前不是最后一个幂次方，加上加号 "+"if (i > 0) {result += "+";}}// 返回生成的表达式return result;
}int main() {int n;cin >> n;  // 输入一个正整数 ncout << powering(n) << endl;  // 调用 powering 函数生成并输出结果return 0;
}

    vector<int> powers;  // 用于存储二进制表示中为1的所有幂for (int i = 0; (1 << i) <= n; ++i) {if (n & (1 << i)) {powers.push_back(i);}}

• 这里我们声明一个 vector<int> powers，用来存储二进制表示中每一位为 1 的幂次方。
• for (int i = 0; (1 << i) <= n; ++i)：这个循环通过位移操作逐步检查整数 n 的每一位。如果当前位对应的 2 的幂小于等于 n，就继续检查下一位。
  • (1 << i) 是将 1 左移 i 位，等价于计算 2^i。
  • n & (1 << i) 是进行位与操作，如果该位为 1，说明 n 在二进制中该位是 1。
• 如果某一位为 1，我们将 i （表示当前的幂次方）加入 powers 向量中。

---