一、0握手问题 - 蓝桥云课
算法代码:
#include <iostream>
using namespace std;
int main()
{
int sum=0;
for(int i=49;i>=7;i--)
sum+=i;
cout<<sum<<endl;
return 0;
}
直接暴力,题意很清晰,累加即可。
二、0小球反弹 - 蓝桥云课
算法代码:
#include<iostream> // 引入输入输出流库,用于标准输入输出操作
#include<iomanip> // 引入输入输出操纵库,用于格式化输出(如设置小数点精度)
#include<cmath> // 引入数学函数库,用于数学运算(如平方根)
using namespace std; // 使用标准命名空间,避免每次调用标准库函数时都要加std::
// 定义一个函数check,用于检查两个整数a和b是否满足特定条件
bool check(int a, int b) {
// 如果a能被b整除,并且a除以b的结果是偶数,则返回true
if (a % b == 0 && (a / b) % 2 == 0) return true;
return false; // 否则返回false
}
// 主函数
int main() {
long long x = 343720, y = 233333; // 定义两个长整型变量x和y,并赋予初始值
long long t = 1; // 定义长整型变量t,并初始化为1
long long lx, ly; // 定义两个长整型变量lx和ly,用于存储计算过程中的临时值
// 进入一个无限循环,直到满足特定条件时跳出循环
while (1) {
lx = 15 * t; // 计算lx为15乘以t
ly = 17 * t; // 计算ly为17乘以t
// 如果lx和x满足check函数的条件,且ly和y也满足check函数的条件,则跳出循环
if (check(lx, x) && check(ly, y)) break;
t++; // 否则,t自增1,继续循环
}
// 输出lx和ly的平方和的平方根,保留两位小数
cout << setprecision(2) << fixed << sqrt(lx * lx + ly * ly);
return 0; // 程序正常结束,返回0
}
问题背景
小球运动:
小球在长方形内以固定的速度比 dx:dy=15:17运动。
当小球碰到长方形的边框时,会发生反弹(入射角等于反射角)。
我们需要计算小球第一次回到起点时所经过的总路径长度。
反弹的等效路径:
反弹问题可以通过“镜像反射法”简化。将长方形无限复制,形成一个网格,小球的路径可以看作一条直线穿过这些镜像长方形。
小球第一次回到起点,等价于这条直线第一次穿过一个镜像长方形的左上角顶点。
数学分析
路径条件:
小球在水平方向(长)移动的总距离必须是长方形长度 x=343720 的偶数倍。这是因为每次反弹都会改变方向,只有偶数倍才能让小球回到起点的水平位置。
同理,小球在垂直方向(宽)移动的总距离必须是长方形宽度 y=233333 的偶数倍。
公式推导:
小球在水平方向的移动距离为 lx=15t。
小球在垂直方向的移动距离为 ly=17t。
为了满足回到起点的条件,必须同时满足:
lx=15t=2k⋅x(水平方向)ly=17t=2m⋅y(垂直方向)其中 k 和 m 是正整数。
简化条件:
我们需要找到最小的 t,使得 15t 是 x 的偶数倍,且 17t是 y的偶数倍。
这等价于:
setprecision(2)
是 C++ 标准库 <iomanip>
中的一个操纵符,用于设置浮点数输出的精度。具体来说,它控制输出流中浮点数的小数点后的位数。
详细解释
setprecision(n)
:设置浮点数输出的小数点后的位数为n
。例如,setprecision(2)
表示输出浮点数时保留两位小数。fixed
:与setprecision
结合使用,表示使用固定小数格式输出。这意味着小数点后的位数是固定的,而不是科学计数法。
三、0好数 - 蓝桥云课
算法代码:
#include <stdio.h>
int main()
{
int n, i;
scanf("%d", &n); // 输入一个整数 n
for (; n > 0; n--) // 从 n 开始,递减到 1
{
for (int m = n; m > 0;) // 对每个数字 m = n,检查其每一位
{
if (m % 2 != 0) m /= 10; // 如果最低位是奇数,去掉最低位
else break; // 如果最低位是偶数,退出循环
if (m % 2 == 0) m /= 10; // 如果新的最低位是偶数,去掉最低位
else break; // 如果新的最低位是奇数,退出循环
if (m == 0) i++; // 如果 m 变为 0,说明满足条件,计数器 i 增加
}
}
printf("%d", i); // 输出满足条件的数字的数量
return 0;
}
题意清晰,直接一个一个数地循环递减,然后按规则,直接判断奇数位和偶数位是不是符合条件。
四、0R 格式 - 蓝桥云课
自己写的:算法代码(只能通过50%的测试用例)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 快速幂函数,计算 2^n
ll fastPow(int n) {
ll a = 2; // 底数为 2
ll sum = 1; // 初始化 sum 为 1
while (n) {
if (n & 1) {
sum = sum * a; // 如果当前位为 1,累乘到 sum
}
a = a * a; // 底数平方
n >>= 1; // 右移一位
}
return sum;
}
int main() {
int n;
double d;
cin >> n >> d; // 输入 n 和 d
ll ans = fastPow(n); // 计算 2^n
ll end_format = round(d * ans); // 将 d 乘以 2^n 并四舍五入
//round 函数用于对浮点数进行四舍五入操作
printf("%lld\n", end_format); // 输出结果
return 0;
}
罗勇军老师的几行代码(50%)(高下立判了属于是哈哈)算法代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long n;
double s;
cin>>n>>s;
long long a = 1<<n;
long long b= (long long)(a*s*1.0+0.5);//加0.5四舍五入
cout << b;
}
题解:
#include<bits/stdc++.h> // 包含所有标准库头文件
using namespace std; // 使用标准命名空间
int main()
{
int n;
string d; // 由于数字可能非常大,使用字符串来读取
cin >> n >> d; // 输入转换参数 n 和浮点数 d
vector<int> b; // 使用 vector 来存储数字的每一位,方便处理进位
int sum = 0, k = 0; // sum 用于记录总位数,k 用于记录小数点的位置
// 从字符串末尾开始遍历,将字符转换为整数并存储到 vector 中
for(int i = d.size() - 1; i >= 0; i--)
{
if(d[i] != '.')
b.push_back(d[i] - '0'); // 将字符转换为整数并存储
else {
k = sum; // 记录小数点的位置
}
sum++; // 记录总位数
}
int u = b.size(); // 记录当前数字的位数
// 进行 n 次乘以 2 的操作
while(n--)
{
int t = 0; // t 用于记录进位
for(int i = 0; i < b.size(); i++)
{
b[i] = b[i] * 2 + t; // 当前位乘以 2 并加上进位
if(b[i] >= 10)
{
t = b[i] / 10; // 计算新的进位
b[i] = b[i] % 10; // 取余数作为当前位的值
}
else {
t = 0; // 如果没有进位,置为 0
}
}
if(t) // 如果最后还有进位,添加到 vector 中
b.push_back(t);
}
u = b.size(); // 更新数字的位数
int t = 1; // 用于处理四舍五入的进位
if(k && b[k - 1] >= 5) // 如果需要四舍五入
{
for(int i = k; i < u; i++)
{
b[i] = b[i] + 1; // 当前位加 1
if(b[i] <= 9) { // 如果不需要继续进位
t = 0;
break;
}
else {
b[i] -= 10; // 如果需要继续进位
}
}
if(t) // 如果最后还有进位,添加到 vector 中
b.push_back(t);
}
// 从最高位开始输出结果,忽略小数部分
for(int i = b.size() - 1; i >= k; i--)
cout << b[i];
return 0; // 程序结束
}
1. 输入处理
输入:读取整数
n
和浮点数d
。n
是转换参数,表示需要将浮点数乘以 2^n。d
是待转换的浮点数,可能非常大,因此用字符串存储。
目标:将浮点数
d
转换为整数形式,方便后续计算。
2. 将浮点数转换为整数形式
遍历浮点数字符串:
从字符串末尾开始遍历,将每个数字字符转换为整数,并存储到
vector<int> b
中。如果遇到小数点
.
,记录小数点的位置k
,表示小数点后有k
位。
结果:
b
中存储的是浮点数d
的整数形式(去掉小数点)。k
记录了小数点的位置,用于后续四舍五入。
3. 高精度乘以 2^n
循环乘以 2:
进行
n
次乘以 2 的操作,每次操作都模拟高精度乘法。每次乘以 2 时,遍历
b
中的每一位,计算当前位乘以 2 并加上进位。如果当前位的结果大于等于 10,则计算进位,并将当前位的结果取余。
如果最后还有进位,将其添加到
b
的末尾。
结果:
b
中存储的是浮点数d
乘以 2^n的结果,仍然是一个高精度整数。
4. 四舍五入
判断是否需要四舍五入:
根据小数点的位置
k
,检查小数点后的第一位(即b[k-1]
)是否大于等于 5。如果大于等于 5,则需要进行四舍五入。
四舍五入操作:
从小数点位置开始,向高位逐位加 1,直到没有进位为止。
如果最高位仍有进位,将其添加到
b
的末尾。
结果:
b
中存储的是四舍五入后的最终结果。
5. 输出结果
从最高位开始输出:
从
b
的最高位开始,输出每一位数字。忽略小数部分(即小数点后的位数)。
结果:
输出的是浮点数
d
乘以 2^n 并四舍五入后的整数结果。
6. 代码的核心思想
高精度计算:
由于浮点数和 2^n 可能非常大,普通数据类型无法存储,因此使用字符串和
vector<int>
来模拟高精度计算。
逐位处理:
通过逐位遍历和进位处理,实现了高精度乘法和四舍五入。
四舍五入:
根据小数点后的第一位决定是否需要进位,模拟了四舍五入的过程。
五、 0宝石组合 - 蓝桥云课
(这道题我只会暴力,而且没拿到该拿的分,别提了,都是泪)
牛逼的题解:
#include <bits/stdc++.h> // 包含所有标准库头文件
#define N 500010 // 定义常量 N,表示数组的最大大小
int gem[N], num[N]; // 定义两个数组:gem 用于存储输入的宝石编号,num 用于统计每种宝石的数量
int main() {
int n;
scanf("%d", &n); // 输入整数 n,表示宝石的数量
int max = -0x3f3f3f3f; // 初始化 max 为一个很小的值,用于记录宝石编号的最大值
for (int i = 0; i < n; i++) {
scanf("%d", &gem[i]); // 输入每个宝石的编号
num[gem[i]]++; // 统计每种宝石的数量
if (gem[i] > max) max = gem[i]; // 更新宝石编号的最大值
}
// 从最大值开始,尝试找到满足条件的三个宝石
for (int i = max; i >= 1; i--) { // i 是可能的公因数
int tmp[3], pos = 0; // tmp 用于存储符合条件的宝石编号,pos 用于记录 tmp 中的位置
int cnt = 0; // cnt 用于统计符合条件的宝石数量
// 遍历所有 i 的倍数,检查是否存在对应的宝石
for (int j = i; j <= max; j += i) { // j 是 i 的倍数
if (num[j]) { // 如果宝石 j 存在
cnt += num[j]; // 统计宝石 j 的数量
for (int k = 0; k < num[j] && pos < 3; k++) { // 将宝石 j 加入 tmp
tmp[pos++] = j;
}
}
if (cnt == 3) break; // 如果找到三个宝石,跳出循环
}
// 如果找到三个宝石,输出结果并结束程序
if (cnt == 3) {
for (int j = 0; j < 3; j++) {
printf("%d ", tmp[j]); // 输出三个宝石的编号
}
break; // 结束程序
}
}
return 0; // 程序结束
}
代码思路:
六、0数字接龙 - 蓝桥云课
题解代码:
#include <bits/stdc++.h> // 包含所有标准库头文件
using namespace std;
const int N = 11; // 定义棋盘的最大大小为11×11
int n, k; // n为棋盘大小,k为数字循环的范围
int g[N][N]; // 存储棋盘上的数字
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; // 定义8个方向的x坐标偏移
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1}; // 定义8个方向的y坐标偏移
string path; // 存储路径的方向编号
bool st[N][N]; // 标记棋盘上的格子是否被访问过
bool edge[N][N][N][N]; // 检查路径是否交叉
// 深度优先搜索函数,用于寻找路径
bool dfs(int a, int b) {
// 如果到达右下角格子,检查路径长度是否为n*n-1(因为起点不计入路径)
if (a == n - 1 && b == n - 1)
return path.size() == n * n - 1;
st[a][b] = true; // 标记当前格子已访问
for (int i = 0; i < 8; i++) { // 遍历8个方向
int x = a + dx[i], y = b + dy[i]; // 计算目标格子的坐标
// 检查目标格子是否越界、是否访问过、数字是否满足循环序列要求
if (x < 0 || x >= n || y < 0 || y >= n) continue;
if (st[x][y]) continue;
if (g[x][y] != (g[a][b] + 1) % k) continue;
// 检查路径是否交叉(对于斜向移动,检查是否有反向的路径)
if (i % 2 && (edge[a][y][x][b] || edge[x][b][a][y])) continue;
edge[a][b][x][y] = true; // 标记路径
path += i + '0'; // 将方向编号加入路径
if (dfs(x, y)) return true; // 递归搜索下一个格子
path.pop_back(); // 回溯,移除路径中的最后一个方向
edge[a][b][x][y] = false; // 回溯,取消路径标记
}
st[a][b] = false; // 回溯,取消当前格子的访问标记
return false; // 如果所有方向都无法到达终点,返回false
}
int main() {
cin >> n >> k; // 输入棋盘大小和数字循环范围
for (int i = 0; i < n; i++) // 读取棋盘上的数字
for (int j = 0; j < n; j++)
cin >> g[i][j];
// 从起点(0,0)开始搜索路径
if (!dfs(0, 0))
cout << -1 << endl; // 如果没有找到路径,输出-1
else
cout << path << endl; // 输出路径的方向编号序列
return 0;
}
罗勇军老师的分析:(有道理)
七、0拔河 - 蓝桥云课
算法代码(20%暴力枚举)
//20%:暴力枚举
#include<bits/stdc++.h> // 包含所有标准库头文件
using namespace std; // 使用标准命名空间
const int N = 1e3 + 100; // 定义常量 N,表示数组的最大大小
typedef long long ll; // 定义 long long 类型的别名 ll
ll a[100]; // 定义数组 a,用于存储输入的数字
// 计算子数组和的函数
ll sum(int l, int r) {
ll s = 0; // 初始化子数组和为 0
for (int i = l; i <= r; i++) // 遍历子数组的每个元素
s += a[i]; // 累加子数组的元素
return s; // 返回子数组的和
}
int main() {
int n; // 定义整数 n,表示数组的大小
cin >> n; // 输入数组的大小 n
for (int i = 1; i <= n; i++) // 遍历数组的每个位置
cin >> a[i]; // 输入数组的每个元素
ll ans = 1e12; // 初始化答案为一个大值(1e12),用于存储最小绝对差
// 暴力枚举所有可能的子数组对
for (int l1 = 1; l1 <= n; l1++) { // 枚举第一个子数组的起始位置 l1
for (int r1 = l1; r1 <= n; r1++) { // 枚举第一个子数组的结束位置 r1
for (int l2 = r1 + 1; l2 <= n; l2++) { // 枚举第二个子数组的起始位置 l2
for (int r2 = l2; r2 <= n; r2++) { // 枚举第二个子数组的结束位置 r2
// 计算两个子数组和的绝对差,并更新最小值
ans = min(ans, abs(sum(l2, r2) - sum(l1, r1)));
}
}
}
}
cout << ans; // 输出最小绝对差
return 0; // 程序结束
}
算法代码(40%暴力枚举+前缀和优化)
#include<bits/stdc++.h> // 包含所有标准库头文件
using namespace std; // 使用标准命名空间
const int N = 1e3 + 100; // 定义常量 N,表示数组的最大大小
typedef long long ll; // 定义 long long 类型的别名 ll
ll a[N], prefix[N]; // 定义数组 a 和前缀和数组 prefix
// 计算子数组和的函数
ll sum(int l, int r) {
return prefix[r] - prefix[l - 1]; // 返回子数组 [l, r] 的和
}
int main() {
int n; // 定义整数 n,表示数组的大小
cin >> n; // 输入数组的大小 n
// 读取数组并计算前缀和
for (int i = 1; i <= n; i++) {
cin >> a[i]; // 输入数组的每个元素
prefix[i] = prefix[i - 1] + a[i]; // 计算前缀和
}
ll ans = 1e12; // 初始化答案为一个大值(1e12),用于存储最小绝对差
// 枚举所有子数组对
for (int l1 = 1; l1 <= n; l1++) { // 枚举第一个子数组的起始位置 l1
for (int r1 = l1; r1 <= n; r1++) { // 枚举第一个子数组的结束位置 r1
ll sum1 = sum(l1, r1); // 计算第一个子数组的和
for (int l2 = r1 + 1; l2 <= n; l2++) { // 枚举第二个子数组的起始位置 l2
for (int r2 = l2; r2 <= n; r2++) { // 枚举第二个子数组的结束位置 r2
ll sum2 = sum(l2, r2); // 计算第二个子数组的和
ans = min(ans, abs(sum2 - sum1)); // 更新最小绝对差
}
}
}
}
cout << ans; // 输出最小绝对差
return 0; // 程序结束
}
逆天题解:(真的想不出来,我是个只会暴力的fw)
#include<bits/stdc++.h> // 包含所有标准库头文件
using namespace std; // 使用标准命名空间
const int N = 1e3 + 10; // 定义常量 N,表示数组的最大大小
long long a[N]; // 定义数组 a,用于存储前缀和
int n; // 定义整数 n,表示数组的大小
multiset<long long> s; // 定义 multiset,用于存储所有可能的子数组和
// 自定义函数,返回两个数中的较小值
long long minn(long long a, long long b) {
if (a < b) return a;
else return b;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 取消同步流,加速输入输出
cin >> n; // 输入数组的大小 n
// 读取数组并构造前缀和
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] += a[i - 1]; // 计算前缀和
}
// 枚举所有可能的子数组和,并将其插入 multiset
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
s.insert(a[j] - a[i - 1]); // 计算子数组 [i, j] 的和,并插入 multiset
}
}
long long res = 1e9; // 初始化结果为一个大值(1e9),用于存储最小绝对差
// 遍历所有可能的第一个区间的右端点 i
for (int i = 1; i < n; i++) {
// 删除以 i 作为右端点的所有子数组和
for (int j = i; j <= n; j++) {
auto k = a[j] - a[i - 1]; // 计算子数组 [i, j] 的和
s.erase(s.find(k)); // 从 multiset 中删除该和
}
// 遍历所有可能的第一个区间的左端点 j
for (int j = 1; j <= i; j++) {
auto k = a[i] - a[j - 1]; // 计算第一个子数组 [j, i] 的和
// 在 multiset 中查找最接近 k 的值
auto p = s.lower_bound(k); // 找到第一个 >= k 的值
if (p != s.end()) {
res = minn(res, abs(*p - k)); // 更新最小绝对差
}
if (p != s.begin()) {
p--; // 找到第一个 < k 的值
res = minn(res, abs(*p - k)); // 更新最小绝对差
}
}
}
cout << res << endl; // 输出最小绝对差
return 0; // 程序结束
}