第十六屆藍橋杯大賽軟件賽省賽 C/C++ 大學B組

由于官方沒有公布題目的數據, 所以代碼僅供參考

1. 移動距離??

題目鏈接：P12130 [藍橋杯 2025 省 B] 移動距離 - 洛谷

【問題描述】
小明初始在二維平面的原點，他想前往坐標 (233, 666)。在移動過程中，他
只能采用以下兩種移動方式，并且這兩種移動方式可以交替、不限次數地使用：
1. 水平向右移動，即沿著 x 軸正方向移動一定的距離。
2. 沿著一個圓心在原點 (0, 0)、以他當前位置到原點的距離為半徑的圓的圓
周移動，移動方向不限（即順時針或逆時針移動不限）。
在這種條件下，他到達目的地最少移動多少單位距離？
你只需要輸出答案四舍五入到整數的結果。
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可。本題的結果為一
個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。

解題思路：

1.目標點(233,666) tan a=666/233, a=arctan(666/233)=70.67, r=sqrt(233^2+666^2)=705.05

2.題目中說到只能沿x軸方向移動和沿r進行順/逆時針旋轉,?沿x軸方向移動改變r/角度a,?沿r進行順/逆時針旋轉只改變角度a

3.先沿x軸直線移動, 將r增加到目標r=705.05 ->(移動到點(705.05,0)), 沿半徑為705.05的逆時針轉動, 角度a變為70.67

4. 直線移動距離 x=705.05, 弧度y=r*a=705.05*70.67*(π/180)=705.05*1.233=869.67

? ? ?所以總距離為 x+y=705.05+869.67=1574,72, 四舍五入為1575, 有誤差, 代碼跑的話是1576

代碼如下：?

#include <bits/stdc++.h>
using namespace std;
int main() {double x = 233, y = 666;double r = sqrt(x * x + y * y);double t = atan2(y, x); double d= r + r * t;cout  << round(d) << endl;return 0;
}

2. 客流量上限?

?題目鏈接：P12131 [藍橋杯 2025 省 B] 客流量上限 - 洛谷

【問題描述】
一家連鎖旅館在全國擁有 2025 個分店，分別編號為 1 至 2025。隨著節日
臨近，總部決定為每家分店設定每日客流量的上限，分別記作 A1, A2,. . . , A2025。
這些上限并非隨意分配，而是需要滿足以下約束條件：
1. A1, A2,. . . , A2025 必須是 1 至 2025 的一個排列，即每個 Ai 均是 1 至 2025
之間的整數，且所有 Ai 互不相同。
2. 對于任意分店 i 和 j（1 ≤ i, j ≤ 2025，i 可等于 j），它們的客流量上限 Ai
和 Aj 的乘積不得超過 i × j +2025。
這些約束旨在平衡各分店客流壓力，確保服務質量和運營穩定性。
現在，請你計算這樣的分配方案究竟有多少種。由于答案可能很大，你只
需輸出其對 109 +7 取余后的結果即可。
【答案提交】
這是一道結果填空題，你只需要算出結果后提交即可。本題的結果為一個
整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。?

暫時沒有啥思路, 我用全排列寫, n一超過10/11就超時, 代碼如下??

#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;vector<int> p(n);iota(p.begin(), p.end(), 1); //生成1-n的數int count = 0;do {bool f = true;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (p[i] * p[j] > (i + 1) * (j + 1) + n) {f= false;break;}}if (!f) break;}if (f) count++;} while (next_permutation(p.begin(), p.end()));cout << count << endl;return 0;
}

3.??可分解的正整數

?題目鏈接：P12132 [藍橋杯 2025 省 B] 可分解的正整數 - 洛谷

【問題描述】
定義一種特殊的整數序列，這種序列由連續遞增的整數組成，并滿足以下
條件：
1. 序列長度至少為 3。
2. 序列中的數字是連續遞增的整數（即相鄰元素之差為 1），可以包括正整
數、負整數或 0。
例如，[1, 2, 3]、[4, 5, 6, 7] 和 [?1, 0, 1] 是符合條件的序列，而 [1, 2]（長度不
足）和 [1, 2, 4]（不連續）不符合要求。
現給定一組包含 N 個正整數的數據 A1, A2,. . . , AN。如果某個 Ai 能夠表示
為符合上述條件的連續整數序列中所有元素的和，則稱 Ai 是可分解的。
請你統計這組數據中可分解的正整數的數量。

【輸入格式】
輸入的第一行包含一個正整數 N，表示數據的個數。
第二行包含 N 個正整數 A1, A2,. . . , AN，表示需要判斷是否可分解的正整數
序列。
【輸出格式】
輸出一個整數，表示給定數據中可分解的正整數的數量。?

?

數據范圍：

對于 30% 的評測用例，1 ≤ N ≤ 100，1 ≤ Ai ≤ 100。
對于 100% 的評測用例，1 ≤ N ≤ 105，1 ≤ Ai ≤ 109。

解題思路：舉個例子, A1=3 -> 可以分解成0+1+2; A2=6 -> 可以分解成1+2+3 A3=2 -> 可以分解成-1+0+1+2....

通解：就是任意一個數x, 都可以寫成-2+-1+0+1+2+x... 這個排列, 除了1是不行, 其他>=1數都可以

代碼如下：

#include <bits/stdc++.h>
using namespace std;
int main() {int n, count = 0;cin >> n;for (int i = 0; i < n; ++i) {int x;cin >> x;if (x!=1) count++;}cout << count << endl;return 0;
}
//3 -> 0 1 2
//6 -> 1 2 3
//15 -> 4 5 6
//2 -> -1 0 1 2
//1 -> -1 0 1 不可以
//0 -> Ai>=1

4. 產值調整

?題目鏈接：P12133 [藍橋杯 2025 省 B] 產值調整 - 洛谷

【問題描述】
偏遠的小鎮上，三兄弟共同經營著一家小型礦業公司 “兄弟礦業”。公司旗
下有三座礦山：金礦、銀礦和銅礦，它們的初始產值分別用非負整數 A、B 和
C 表示。這些礦山的產出是小鎮經濟的核心，支撐著三兄弟和許多礦工家庭的
生計。
然而，各礦山的產值波動劇烈，有時金礦收益高而銀礦、銅礦低迷，有時
則相反。這種不穩定性讓公司收入難以預測，也常引發兄弟間的爭執。為了穩
定經營，三兄弟設計了一個公平的產值調整策略，每年執行一次，每次調整時，
將根據當前的產值 A、B、C，計算新產值：
1. 金礦新產值 A′ = ? B+2C ?；
2. 銀礦新產值 B′ = ?A+2C ?；
3. 銅礦新產值 C′ = ?A+2 B ?。
其中，?? 表示向下取整。例如，?3.7? =3，?5.2? =5。
計算出 A′、B′、C′ 后，同時更新：A 變為 A′，B 變為 B′，C 變為 C′，作
為下一年調整的基礎。
三兄弟認為這個方法能平衡產值波動，于是計劃連續執行 K 次調整。現
在，請你幫他們計算，經過 K 次調整后，金礦、銀礦和銅礦的產值分別是多
少。

【輸入格式】
輸入的第一行包含一個整數 T ，表示測試用例的數量。
接下來的 T 行，每行包含四個整數 A，B，C，K，分別表示金礦、銀礦和
銅礦的初始產值，以及需要執行的調整次數。

【輸出格式】
對于每個測試用例，輸出一行，包含三個整數，表示經過 K 次調整后金
礦、銀礦和銅礦的產值，用空格分隔。

?

【評測用例規模與約定】
對于 30% 的評測用例，1 ≤ T ≤ 100，1 ≤ A, B, C, K ≤ 105。
對于 100% 的評測用例，1 ≤ T ≤ 105，1 ≤ A, B, C, K ≤ 109。

?解題思路：題目中讓你怎么調整, 你就怎么調整，eg: A1->(B+2*C)/2

代碼如下：

#include <bits/stdc++.h>
using namespace std;
int main() {int T;cin >> T;while (T--) {int a, b, c;long long k;cin >> a >> b >> c >> k;for (long long i = 0; i < k; ++i) {int na = (b + c) / 2;int nb = (a + c) / 2;int nc = (a + b) / 2;if (na == a && nb == b && nc == c) {break;}a = na;b = nb;c = nc;}cout << a << " " << b << " " << c << endl;}return 0;
}

?5.畫展布置

?題目鏈接：P12134 [藍橋杯 2025 省 B] 畫展布置 - 洛谷

畫展策展人小藍和助理小橋為即將舉辦的畫展準備了 N 幅畫作，其藝術價
值分別為 A1, A2,. . . , AN。他們需要從這 N 幅畫中挑選 M 幅，并按照一定順序
布置在展廳的 M 個位置上。如果隨意挑選和排列，藝術價值的變化可能會過于
突兀，導致觀眾的觀展體驗不夠流暢。
為了優化布置，他們查閱了《畫展布置指南》。指南指出，理想的畫展應使
觀眾在欣賞畫作時，藝術價值的過渡盡量平緩。指南建議，選擇并排列 M 幅
畫，應使藝術價值的變化程度通過一個數值 L 來衡量，且該值越小越好。數值
L 的定義為：
L =M∑?1i=1|B2i+1 ? B2i |
其中 Bi 表示展廳第 i 個位置上畫作的藝術價值。
現在，他們希望通過精心挑選和排列這 M 幅畫作，使 L 達到最小值，以
提升畫展的整體協調性。請你幫他們計算出這個最小值是多少。
【輸入格式】
輸入共兩行。
第一行包含兩個正整數 N 和 M，分別表示畫作的總數和需要挑選的畫作數
量。
第二行包含 N 個正整數 A1, A2,. . . , AN，表示每幅畫作的藝術價值。
【輸出格式】
輸出一個整數，表示 L 的最小值。

數據范圍：

對于 40% 的評測用例，2 ≤ M ≤ N ≤ 103，1 ≤ Ai ≤ 103。
對于 100% 的評測用例，2 ≤ M ≤ N ≤ 105，1 ≤ Ai ≤ 105。

?1.題意解釋從N副畫中選出M副畫, 然后計算出M對應的L, 輸出L的最小值

題目中說的是盡量讓M個數的平方差的絕對值之和的最小值

2. 先排序不就得了, 例如, 1 7 8 9比1 9 8 7更平滑啊

3. 平方后選連續的元素更優,?

所以我們只需要在[平方 + 排序]后的序列上找一段長度為 M 的子序列，使得相鄰差的絕對值之和最小，這不就是滑窗嗎, 去除最left側的元素，增加下一個元素，同時維護一個和最小值

代碼如下：?

#include <bits/stdc++.h>
using namespace std;
int main() {int N, M;cin >> N >> M;vector<long long> A(N);for (int i = 0; i < N; ++i) {int x;cin >> x;A[i] = 1LL * x * x;  }sort(A.begin(), A.end());vector<long long> diff(N - 1); for (int i = 0; i < N - 1; i++) {diff[i] = abs(A[i + 1] - A[i]);}long long L = 0;for (int i = 0; i < M - 1; i++) {L += diff[i];}long long minL = L;for (int i = 1; i <= N - M; i++) {L = L - diff[i - 1] + diff[i + M - 2];minL = min(minL, L);}cout << minL << endl;return 0;
}

6. 水質檢測

題目鏈接：P12135 [藍橋杯 2025 省 B] 水質檢測 - 洛谷

【問題描述】
小明需要在一條 2 × n 的河床上鋪設水質檢測器。在他鋪設之前，河床上已
經存在一些檢測器。如果兩個檢測器上下或者左右相鄰，那么這兩個檢測器就
是互相連通的。連通具有傳遞性，即如果 A 和 B 連通，B 和 C 連通，那么 A
和 C 也連通。現在他需要在河床上增加鋪設一些檢測器使得所有的檢測器都互
相連通。他想知道最少需要增加鋪設多少個檢測器？
【輸入格式】
輸入共兩行，表示一個 2 × n 的河床。
每行一個長度為 n 的字符串，僅包含 ‘#’ 和 ‘.’，其中 ‘#’ 表示已經存在的
檢測器，‘.’ 表示空白。
【輸出格式】
輸出共 1 行，一個整數表示答案。

?讓字符串a和字符串b進行連通

#include <bits/stdc++.h>
using namespace std;
int main(){string a, b;cin >> a >> b;int ans = 0;int c = -1, d = -1;for(int i = 0; i < a.size(); i++) {if(a[i] == '.' && b[i] == '.') continue;if(c != -1) {ans += i - c - 1;}if(a[i] == '#' && b[i] == '#') {d = 3;} else if(a[i] == '#' && b[i] == '.') {if(d == 2) {ans++;d = 3;} else {d = 1;}} else if(a[i] == '.' && b[i] == '#') {if(d == 1) {ans++;d = 3;} else {d = 2;}}c = i;}cout << ans << endl;
}

7. 生產車間

?題目鏈接：P12136 [藍橋杯 2025 省 B] 生產車間 - 洛谷

【問題描述】
小明正在改造一個生產車間的生產流水線。這個車間共有 n 臺設備，構成
以 1 為根結點的一棵樹，結點 i 有權值 wi。其中葉節點的權值 wi 表示每單位時
間將產出 wi 單位的材料并送往父結點，根結點的權值 wi 表示每單位時間內能
打包多少單位成品，其他結點的權值 wi 表示每單位時間最多能加工 wi 單位的
材料并送往父結點。
由于當前生產線中某些結點存在產能不夠的問題導致生產線無法正常運行，
即存在某些結點每單位時間收到的材料超過了當前結點的加工能力上限。小明
計劃刪除一些結點使得所有結點都能正常運行。他想知道刪除一些結點后根結
點每單位時間內最多能打包多少單位的成品？
【輸入格式】
輸入共 n +1 行。
第一行為一個正整數 n。
第二行為 n 個由空格分開的正整數 w1, w2,..., wn。
后面 n ? 1 行，每行兩個整數表示樹上的一條邊連接的兩個結點。
【輸出格式】
輸出共一行，一個整數代表答案。

如果你直接暴力dfs的話, 應該是能過掉不少的樣例的, 但是要, 貪心選擇能貢獻最大但不超容量的子節點，我在洛谷測的時候過了百分70, 比賽的時候你寫這個沒問題, 盡量cheat更多的分,。下面我提供的是樹形DP的優化代碼。

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> w;
vector<vector<int>> tree;
bitset<1001> dfs(int u, int parent) {bool isLeaf = true;for (int v : tree[u]) {if (v != parent) { isLeaf = false; break; }}if (isLeaf) {bitset<1001> B;B.reset();B[0] = 1;B[w[u]] = 1;return B;}int cap = w[u];bitset<1001> dp_child;dp_child.reset();dp_child[0] = 1;for (int v : tree[u]) {if (v == parent) continue;auto Bv = dfs(v, u);bitset<1001> next;next.reset();for (int x = Bv._Find_first(); x <= cap; x = Bv._Find_next(x)) {next |= (dp_child << x);}dp_child = next;}bitset<1001> Bu;Bu.reset();Bu[0] = 1;for (int x = dp_child._Find_first(); x <= cap; x = dp_child._Find_next(x)) {Bu[x] = 1; }return Bu;
}int main(){cin >> n;w.resize(n+1);for (int i = 1; i <= n; ++i) {cin >> w[i];}tree.resize(n+1, {});for (int i = 0; i < n-1; ++i) {int u,v;cin >> u >> v;tree[u].push_back(v);tree[v].push_back(u);}auto Broot = dfs(1, 0);int ans = 0;for (int x = Broot._Find_first(); x <= w[1]; x = Broot._Find_next(x)) {ans = x;  }cout << ans << endl;return 0;
}

8. 裝修報價

?題目鏈接：P12137 [藍橋杯 2025 省 B] 裝修報價 - 洛谷

【問題描述】
老王計劃裝修房子，于是聯系了一家裝修公司。該公司有一套自動報價系
統，只需用戶提供 N 項裝修相關費用 A1, A2,. . . , AN，系統便會根據這些費用生
成最終的報價。
然而，當老王提交數據后，他發現這套系統的運作方式并不透明：系統只
會給出一個最終報價，而不會公開任何運算過程或中間步驟。
公司對此解釋稱，這套系統會依據某種內部算法，在每對相鄰數字之間插
入 +（加法）、?（減法）或 ⊕（異或）運算符，并按照特定優先級規則計算結
果：異或運算優先級最高，其次是加減。但由于保密性，具體的運算符組合以
及中間過程都不會對外公開。
為了驗證系統報價是否合理，老王決定模擬其運作方式，嘗試每種可能的
運算符組合，計算出所有可能出現的結果的總和。如果最終報價明顯超出這個
范圍，他就有理由懷疑系統存在異常或誤差。只是老王年事已高，手動計算頗
為吃力，便向你求助。
現在，請你幫老王算出所有可能的結果的總和。由于該總和可能很大，你
只需提供其對 10^9 +7 取余后的結果即可。
【輸入格式】
第一行輸入一個整數 N，表示裝修相關費用的項數。
第二行輸入 N 個非負整數 A1, A2,. . . , AN，表示各項費用。
【輸出格式】
輸出一個整數，表示所有可能的總和對 10^9 +7 取余后的結果。

?異或和的優先級最高, 異或和在后面的, 有+AxorB/-AxorB 直接抵消了，所以對答案產生貢獻的，只有一段前綴的異或, 因此我們枚舉前綴異或的長度?i，具體的代碼如下。

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
long long qPow(long long a, long long b, long long p) {long long ans = 1;a %= p;while(b) {if(b & 1) ans = (ans * a) % p;b >>= 1;a = (a * a) % p;}return ans % p;
}
int main(){int n;cin >> n;int S = 0;int ans = 0;for(int i = 1, x; i <= n; i++) {cin >> x;S ^= x;if(i < n) {ans += S * 2 * qPow(3LL, n - i - 1, mod) % mod;} else {ans += S;}ans %= mod;}cout << ans << endl;return 0;
}