洛谷解题日记||基础篇3
#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, d
cin >> 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;
else
r = 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;
else
r = 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 行任意一个单元格出发，最终到达第 n 行的每个单元格。每个士兵的路径是从上到下的，路径上经过的最大伤害值决定了这个士兵的伤害值。
- 我们希望通过合理分配路径，找出所有路径中的“最大伤害值”中的最小值。
-
关键分析：
- 由于我们关心的是路径上的最大伤害值，因此可以将问题转化为：对于一个给定的最大伤害值 xxx，判断是否可以找到一种方式，使得所有的士兵从第 1 行到达第 n 行，同时路径上的最大伤害值都不超过 xxx。
- 这个问题可以通过 二分法 进行优化，搜索最小的最大伤害值。
-
二分法+BFS/DFS判断可行性：
- 使用二分法确定可能的最小最大伤害值。
- 对于每个中间值 xxx，通过广度优先搜索（BFS）或者深度优先搜索（DFS）来判断从第 1 行到第 n 行是否可以找到一条路径，路径上的最大伤害值不超过 xxx。
- 如果可以找到路径，说明当前伤害值是可行的，继续尝试更小的值；否则，增加伤害值。
解法步骤：
-
初始化：
- 读取输入，并建立一个 n×m 的伤害矩阵
p。
- 读取输入，并建立一个 n×m 的伤害矩阵
-
二分查找：
- 设置伤害值的搜索范围为 0 到 max(p)，然后进行二分查找。
-
广度优先搜索（BFS）判断可行性：
- 对于每个中间值 xxx，我们用 BFS 检查从第 1 行到第 n 行是否存在路径，并且路径上的最大伤害值不超过 xxx。
-
输出最小的最大伤害值。
代码实现：
#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;
}
代码解释：
-
输入读取：
- 通过
cin读取迷阵的大小和伤害值矩阵。
- 通过
-
canReach函数：- 给定一个最大伤害值
maxDamage，通过 BFS 判断是否可以找到一条从第 1 行到第 n 行的路径，使得路径上所有房间的伤害值都不超过maxDamage。 - 如果找到路径，返回
true，否则返回false。
- 给定一个最大伤害值
-
二分查找：
- 我们对伤害值进行二分查找，初始范围为
[0, 1000]，中间值mid表示当前尝试的最大伤害值。 - 对于每个中间值，使用
canReach函数检查是否可行。如果可行，尝试找到更小的最大伤害值，否则增加伤害值。
- 我们对伤害值进行二分查找，初始范围为
-
输出结果：
- 最终的
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; // 初始化结果为1
while(b > 0) { // 当指数大于0时循环
if(b & 1) // 如果当前指数的最低位是1
res = (res * a) % p; // 更新结果
a = (a * a) % p; // 更新底数
b >>= 1; // 指数右移一位，相当于除以2
}
return res; // 返回最终结果
}
int main() {
long long a, b, p; // 定义长整型变量a, b, p
cin >> 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 位是否为 1
powers.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; // 输入一个正整数 n
cout << 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向量中。
原文地址：https://blog.csdn.net/ke_wu/article/details/143637197
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！