一、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的結果是偶數,則返回trueif (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,并初始化為1long long lx, ly; // 定義兩個長整型變量lx和ly,用于存儲計算過程中的臨時值// 進入一個無限循環,直到滿足特定條件時跳出循環while (1) {lx = 15 * t; // 計算lx為15乘以tly = 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); // 輸入一個整數 nfor (; 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; // 底數為 2ll sum = 1; // 初始化 sum 為 1while (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 和 dll ans = fastPow(n); // 計算 2^nll 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 和浮點數 dvector<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; // 當前位加 1if(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 加入 tmptmp[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; // 如果沒有找到路徑,輸出-1elsecout << 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; // 初始化子數組和為 0for (int i = l; i <= r; i++) // 遍歷子數組的每個元素s += a[i]; // 累加子數組的元素return s; // 返回子數組的和
}int main() {int n; // 定義整數 n,表示數組的大小cin >> n; // 輸入數組的大小 nfor (int i = 1; i <= n; i++) // 遍歷數組的每個位置cin >> a[i]; // 輸入數組的每個元素ll ans = 1e12; // 初始化答案為一個大值(1e12),用于存儲最小絕對差// 暴力枚舉所有可能的子數組對for (int l1 = 1; l1 <= n; l1++) { // 枚舉第一個子數組的起始位置 l1for (int r1 = l1; r1 <= n; r1++) { // 枚舉第一個子數組的結束位置 r1for (int l2 = r1 + 1; l2 <= n; l2++) { // 枚舉第二個子數組的起始位置 l2for (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++) { // 枚舉第一個子數組的起始位置 l1for (int r1 = l1; r1 <= n; r1++) { // 枚舉第一個子數組的結束位置 r1ll sum1 = sum(l1, r1); // 計算第一個子數組的和for (int l2 = r1 + 1; l2 <= n; l2++) { // 枚舉第二個子數組的起始位置 l2for (int r2 = l2; r2 <= n; r2++) { // 枚舉第二個子數組的結束位置 r2ll 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]; // 計算前綴和}// 枚舉所有可能的子數組和,并將其插入 multisetfor (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),用于存儲最小絕對差// 遍歷所有可能的第一個區間的右端點 ifor (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 中刪除該和}// 遍歷所有可能的第一個區間的左端點 jfor (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; // 程序結束
}