? ? ? ? 做之前的真題就可以發現，藍橋杯特別喜歡出找規律的題，但是我還是低估了官方的執念。本博客用于記錄第一次藍橋的過程，代碼寫的很爛，洛谷已經有的題解，這里不再贅述，只說自己遇到的問題。用于以后回顧和查找資料，畢竟自己總結的印象更深。
? ? ? ? 本博客，沒有多少借鑒價值，基本全是暴力破解和吐槽。
試題 A: 移動距離? （填空 5分）
? ? ? ? 洛谷鏈接：P12130 [藍橋杯 2025 省 B] 移動距離 - 洛谷
? ? ? ?我不會，豆包說“在平面直角坐標系中，從原點(0,0)到點(x,y)?，如果先沿x軸正方向移動到(x,0)?，再沿以原點為圓心，半徑為x2+02?=x的圓移動到(x,y)?，這種移動方式的總距離最短。” ，但是我沒有理解。
豆包代碼：
#include <iostream>
#include <cmath>
using namespace std;int main() {double x = 233;double y = 666;double r = sqrt(x * x + y * y);double distance = r + r * atan(y / x);cout << distance << endl;// 四舍五入到整數int result = round(distance);cout << result << endl;return 0;
}試題 B: 客流量上限（填空 5分）
????????洛谷鏈接：P12131 [藍橋杯 2025 省 B] 客流量上限 - 洛谷
? ? ? ? ?比賽的時候，感覺是有什么規律的，我一直在思考如何保證2025個分店的客流量上限不同，感覺dfs可以，但是又不知道如何判斷和
?的乘積不得超過 i × j + 2025,故作罷。
?????????在洛谷上，看到大佬的題解，思路特別好：（P12131 [藍橋杯 2025 省 B] 客流量上限 - 洛谷）：
#include <bits/stdc++.h>
using namespace std;int main(){int n;cin >> n;vector<int> a;for(int i=1;i<=n;i++){a.push_back(i);}long long cnt=0;do{bool flag=true;for(int i=0;i<n;i++){//位置for(int j=0;j<n;j++){//位置if(a[i]*a[j]>(i+1)*(j+1)+n){//printf("%d %d\n",a[i],a[j]);flag=false;i=n;break;}}}if(flag){cnt++;cnt%=1000000007;}}while(next_permutation(a.begin(),a.end()));cout << cnt;
}? ? ? ? 1? ? ? ? 1
? ? ? ? 2? ? ? ? 1
????????3? ? ? ? 2
? ? ? ? 4? ? ? ? 2
? ? ? ? 5? ? ? ? 4
? ? ? ? 6? ? ? ? 4
? ? ? ? 7? ? ? ? 8
? ? ? ? 8? ? ? ? 8
?“1、1、2、2、4、4、8、8”，發現次數等于
? ? ? ? 只需要再根據規律，算出結果即可。?
#include<bits/stdc++.h>
using namespace std;
int main() {int n;cin >> n;long long flag=(n-1)/2;long long sum=1;for (int i = 0; i < flag; i++){sum*=2;sum%=1000000007;}cout << sum << endl;return 0;
}試題 C: 可分解的正整數（10分）
洛谷鏈接：P12132 [藍橋杯 2025 省 B] 可分解的正整數 - 洛谷
????????
【輸入格式】
輸入的第一行包含一個正整數 N ，表示數據的個數。第二行包含 N 個正整數 A 1 , A 2 , . . . , A N ，表示需要判斷是否可分解的正整數序列。
【輸出格式】
輸出一個整數，表示給定數據中可分解的正整數的數量。
【樣例輸入】?
33 6 15
【樣例輸出】
3
【樣例說明】
A i = 3 是可分解的，因為 [0 , 1 , 2] 的和為 0 + 1 + 2 = 3 。A i = 6 是可分解的，因為 [1 , 2 , 3] 的和為 1 + 2 + 3 = 6 。A i = 15 是可分解的，因為 [4 , 5 , 6] 的和為 4 + 5 + 6 = 15 。所以可分解的正整數的數量為 3 。
【評測用例規模與約定】
對于 30 % 的評測用例， 1 ≤ N ≤ 100 ， 1 ≤? ≤ 100 。
對于 100 % 的評測用例， 1 ≤ N ≤， 1 ≤
。
? ? ? ? 這道題再知乎上也被很多人吐槽了，除了1全部可以。我的思路是從找規律開始，找他的樣例：
0+1+2 = 3
1+2+3 = 6
2+3+4 = 9
會發現長度為三的序列可以輸出所有三的倍數，所以只要是3的倍數都可以分解。?
? ? ? ? 但是要注意題目條件是“序列長度至少為3”，那如果長度為4，就是4的倍數也全部可分解，長度為5，就是5的倍數可以分解......這樣下去，豈不是所有正整數都可以。恰好?“1 ≤ ?≤
”。
? ? ? ? 而且可以有負數，那么...：
-1 + 0?+ 1 + 2 = 2
-2 + -1 + 0 + 1 + 2 + 3 = 3
? ? ? ? 這樣下去就是除了1，都可以“因為不能“-1+0+1+1”。
? ? ? ? 故找到規律后代碼就很簡單了，相信大家都知道怎么寫了，但是我犯了一個很蠢的錯誤：
#include <bits/stdc++.h>
using namespace std;int main()
{int n=0;long long flag=0;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%lld",&flag);if(flag==1)n--; }printf("%d",n);return 0;
}? ? ? ? 大家可以看一下是什么問題，下面是通過的代碼：
#include <bits/stdc++.h>
using namespace std;int main()
{int n=0;long long flag=0;scanf("%d",&n);for(int i=n;i>0;i--){scanf("%lld",&flag);if(flag==1)n--; }printf("%d",n);return 0;
}?試題 D: 產值調整(10分)
洛谷鏈接：P12133 [藍橋杯 2025 省 B] 產值調整 - 洛谷
【輸入格式】
輸入的第一行包含一個整數 T ，表示測試用例的數量。接下來的 T 行，每行包含四個整數 A ， B ， C ， K ，分別表示金礦、銀礦和銅礦的初始產值，以及需要執行的調整次數。
【輸出格式】
對于每個測試用例，輸出一行，包含三個整數，表示經過 K 次調整后金礦、銀礦和銅礦的產值，用空格分隔。
【樣例輸入】
210 20 30 15 5 5 3
【樣例輸出】
25 20 155 5 5
【評測用例規模與約定】
對于 30 % 的評測用例， 1 ≤ T ≤ 100 ， 1 ≤ A , B , C , K ≤對于 100 % 的評測用例， 1 ≤ T ≤ 10 5 ， 1 ≤ A , B , C , K ≤
? ? ? ? 看到這道題，思路不難，那就可能會出現超時問題，那就代表可能有規律，但是我沒看出來，所以就先寫出暴力解法看看：
#include <bits/stdc++.h>
using namespace std;int main()
{int n;scanf("%d",&n);long long A,B,C,K;for(int j=0;j<n;j++){scanf("%lld%lld%lld%lld",&A,&B,&C,&K);int flag_A=A;int flag_B=B;int flag_C=C;for(int i=0;i<K;i++){A=(flag_B+flag_C)/2;B=(flag_A+flag_C)/2;C=(flag_A+flag_B)/2;flag_A=A;flag_B=B;flag_C=C;}printf("%lld %lld %lld\n",A,B,C); }return 0;
}?????????運行例題通過了，那么就稍微改一下樣例試試，加大看看是否超時：
210 20 30 505 5 5 30
? ? ? ? 結果為：
18 18 18
5 5 5
? ? ? ? ！！發現兩組數A、B、C都相同，再讓它輸出中間值發現，除了前幾次運算A、B、C不同，后邊運算全相同，再換幾個數也發現同樣的規律。
? ? ? ? 故我想到的便是在三個數相同的時候跳出循環，這就是本題的答案：
#include <bits/stdc++.h>
using namespace std;int main()
{int n;scanf("%d",&n);long long A,B,C,K;for(int j=0;j<n;j++){scanf("%lld%lld%lld%lld",&A,&B,&C,&K);int flag_A=A;int flag_B=B;int flag_C=C;for(int i=0;i<K;i++){A=(flag_B+flag_C)/2;B=(flag_A+flag_C)/2;C=(flag_A+flag_B)/2;flag_A=A;flag_B=B;flag_C=C;if(A==B&&B==C&&A==C){
// printf("yes\n");break;}// printf("A=%d B=%d C=%d\n",A,B,C);}printf("%lld %lld %lld\n",A,B,C); }return 0;
}試題 E: 畫展布置?（15分）
? ? ? ? 洛谷鏈接：P12134 [藍橋杯 2025 省 B] 畫展布置 - 洛谷
?????????
【輸入格式】
輸入共兩行。第一行包含兩個正整數 N 和 M ，分別表示畫作的總數和需要挑選的畫作數量。第二行包含 N 個正整數 A 1 , A 2 , . . . , A N ，表示每幅畫作的藝術價值。
【輸出格式】
輸出一個整數，表示 L 的最小值。
【樣例輸入】
4 21 5 2 4
【樣例輸出】
3
【評測用例規模與約定】
對于 40 % 的評測用例， 2 ≤ M ≤ N ≤ 10 3 ， 1 ≤ A i ≤。
對于 100 % 的評測用例， 2 ≤ M ≤ N ≤ 10 5 ， 1 ≤ A i ≤
? ? ? ? ?這道題思路洛谷上題解也已經講的很清楚（P12134 [藍橋杯 2025 省 B] 畫展布置 - 洛谷），我再做的時候遇到一個問題：
#include <bits/stdc++.h>
using namespace std;int data[100004]={0};int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&data[i]); sort(data,data+n+1);// for(int i=1;i<=n;i++)// printf("%d ",data[i]);// printf("\n");long long sum=0,flag_min=0;flag_min=data[m]*data[m]-data[1]*data[1];for(int i=2;i+m-1<=n;i++){// flag_min = min(flag_min,data[i+m-1]*data[i+m-1]-data[i]*data[i]);sum=data[i+m-1]*data[i+m-1]-data[i]*data[i];if(sum<flag_min)flag_min=sum;} printf("%lld",flag_min);return 0;
}? ? ? ? 這套代碼再VScode會報錯的：“"data" 不明確”，這是因為頭文件中包含了同名的函數“data”造成的，所以要把“int data[100004]={0};”放在main函數里面，或者重命名。
? ? ? ? 另外他也不能通過全部測試點：
? ? ? ? 這是因為類型問題：?data是“int”型，而sum和flag_min是long long型；data改為“long long”類型，便全部通過了：
#include <bits/stdc++.h>
using namespace std;int main()
{long long data[100004]={0};int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&data[i]); sort(data,data+n+1);// for(int i=1;i<=n;i++)// printf("%d ",data[i]);// printf("\n");long long sum=0,flag_min=0;flag_min=data[m]*data[m]-data[1]*data[1];for(int i=2;i+m-1<=n;i++){flag_min = min(flag_min,data[i+m-1]*data[i+m-1]-data[i]*data[i]);} printf("%lld",flag_min);return 0;
}試題 F: 水質檢測（15分）
【輸入格式】
輸入共兩行，表示一個 2 × n 的河床。每行一個長度為 n 的字符串，僅包含 ‘#’ 和 ‘.’ ，其中 ‘#’ 表示已經存在的檢測器， ‘.’ 表示空白。
【輸出格式】
輸出共 1 行，一個整數表示答案。
【樣例輸入】
.##.....#.#.#.#...
【樣例輸出】
5
【樣例說明】
其中一種方案：.###....#.#.######增加了 5 個檢測器
【評測用例規模與約定】
對于 100 % 的評測用例，保證 n ≤ 1000000 。
? ? ? ? ?對于這道題，我一開始想到的是暴力，通過dfs，第一個水質檢測器作為起點，最后一個作為終點。比賽的時候是能過案例，同時我也自己試了幾組數據也都是通過的，我當時想到的可能會有幾個超時的，畢竟是遍歷。但是我在洛谷運行的時候，竟然有WA。：
? ? ? ? 代碼如下：?
#include <bits/stdc++.h>
using namespace std;string str[2]={"\0"};
int flag_min=0;
int book[2][1000004]={0};
//int sum=0;
int beg_x=0,beg_y=0;
int end_x=0,end_y=0;
int up[2][2]={0,1,/*右*/1,0 /*下*/
};void dfs(int x,int y,int sum)
{if(x==end_x&&y==end_y){
// printf("sum=%d end!\n",sum);if(sum<flag_min)flag_min=sum;return ;}else if(x>=2||y>=str[0].size()) return ;if(book[x][y]==0)for(int i=0;i<2;i++){book[x][y]=1;if(str[x][y]=='.')sum++; dfs(x+up[i][0],y+up[i][1],sum);book[x][y]=0;}return ;
} int main()
{char c;int n=0;cin>>str[0]>>str[1];flag_min=str[0].size()*2;int flag=0;for(int i=0;i<str[0].size();i++){for(int j=0;j<2;j++){
// printf("begin_test!\n");if(str[j][i]=='#'){flag=1;beg_x=j;beg_y=i;
// printf("%d %d\n",beg_x,beg_y);break;} }if(flag==1) break;}if(flag==0) printf("0");/*表示一個#都沒有*/else{flag=0;for(int i=str[0].size()-1; i>=0;i--){for(int j=1;j>=0;j--){
// printf("end_test!\n");if(str[j][i]=='#'){flag=1;end_x=j;end_y=i;
// printf("%d %d\n",end_x,end_y);break;} }if(flag==1) break;}// /*min_road*/dfs(beg_x,beg_y,0);printf("%d",flag_min);}return 0;
}? ? ? ? 先找出起終點，然后通過dfs遍歷，像迷宮問題一樣（萬能搜索算法-CSDN博客） ，TLE在預料之中，但WA不再，所以我開始找問題，最后發現，問題出在dfs的遍歷方向上，我只遍歷了“左”，“上”連個方向，這種情況只適用于，起點在第一行的情況，但如果出現在第二行，便永遠不能到達第一行了，所以我又加了一個向上的方向。
int up[3][2]={{0,1}, /*右*/{1,0}, /*下*/{-1,0} /*上*/
};? ? ? ? 得到如下結果：
? ? ? ? ?在預料之中。洛谷大佬已經給出了正解：P12135 [藍橋杯 2025 省 B] 水質檢測 - 洛谷。這種解法我是真想不出來，所以便不強行解釋了。目前就暴力解法了。
試題 G: 生產車間（20分）
? ? ? ? 洛谷鏈接：P12136 [藍橋杯 2025 省 B] 生產車間 - 洛谷
【輸入格式】
輸入共 n + 1 行。第一行為一個正整數 n 。第二行為 n 個由空格分開的正整數 w 1 , w 2 , ..., w n 。后面 n ? 1 行，每行兩個整數表示樹上的一條邊連接的兩個結點。
【輸出格式】
輸出共一行，一個整數代表答案。
【樣例輸入】
99 7 3 7 1 6 2 2 71 21 32 42 52 66 76 86 9
【樣例輸出】
8
【樣例說明】
刪掉結點 4 、 9 后生產線滿足條件，根結點 1 每單位時間將打包出 8 單位的成品。
【評測用例規模與約定】
對于 20 % 的評測用例， 2 ≤ n ≤ 100 。對于 100 % 的評測用例， 2 ≤ n ≤ 1000 ， w i ≤ 1000 。
? ? ? ? ?這道題的樹就已經難到我了，因為我當時已經忘了怎么構建樹了，而且這是一個多叉樹，還不是二叉樹。所以考試的時候是通過鄰接矩陣 加01背包構造的,代碼如下：
#include<bits/stdc++.h>
using namespace std;int dfs(int root,int x,vector<vector<int>> tree,vector<int> w,int n)
{ vector<vector<int>> data(x,vector<int>(w[root]+1,0));/*0-x*/int first=0;for(int j=1;j<=n;j++){if(tree[root][j]==2){first=j;break;} }for(int i=0;i<=w[root];i++){if(i>w[i])data[0][i]=w[i];}if(x==n)for(int i=0;i<x;i++){for(int j=0;j<=w[root];j++)if(i<w[i])data[i][j]=data[i-1][j];elsedata[i][j]=max(data[i-1][j],data[i-1][j-w[i]]+w[i]);}return data[x-1][w[root]];
}int main()
{int n;scanf("%d",&n);vector<vector<int>> tree(n+1,vector<int>(n,0));vector<int> w(n+1,0);for(int i=1;i<=n;i++){scanf("%d",&w[i]);}for(int i=0,a=0,b=0;i<n-1;i++){scanf("%d%d",&a,&b);tree[a][b]=1;
// tree[a].push_back(b);}int sum=0,num=0; for(int i=1;i<=n;i++)/*從葉到根*/{sum=0,num=0;for(int j=1;j<=n;j++)/*從小到大尋找父節點*/{if(tree[j][i]==1)/*j為父節點*/{for(int k=1;k<=n;k++)/*遍歷子節點*/{if(tree[j][k]==1){num++;tree[j][k]=2;sum+=w[k];}}if(sum>w[j]){w[j]=dfs(j,num,tree,w,n);}}}}cout<<w[1];return 0;
}? ? ? ? 因為我連測試點都沒過，不出所料一片紅：
? ? ? ? 與上一題一樣，暴力的解法應該只有AC和TLE，所以我又開始找錯誤之旅。?
? ? 經過我的不斷修改，我決定放棄上邊這套爛代碼，用鄰接表代替鄰接矩陣來寫（鄰接矩陣太麻煩），并且通過dfs搜索，來實現樹的遍歷，但依舊采用01背包的思路去做：代碼如下：
#include <iostream>
#include <vector>
using namespace std;const int N = 1010;
int n, w[N];
vector<int> g[N];/*鄰接表*/
int f[N][N]={0};// 深度優先搜索
void dfs(int u) {// 葉節點情況（g[u].empty()為NULL 輸出1），葉節點的材料產出就是其權值if (g[u].empty()) {f[u][w[u]] = w[u];return;}// 對當前節點的每個子節點進行DFSfor (int i = 0; i < g[u].size(); i++) {int v = g[u][i];dfs(v);}for (int i = 1; i <= w[u]; i++)/*初始化*/{if(w[g[u][0]]<=i)f[u][i]=w[g[u][0]];} for (int i = 1; i < g[u].size(); i++)/*物品*/{for (int j=w[u];j>=0;j--)/*背包*/f[u][j]=max(f[u][j],f[u][j-w[g[u][i]]]+w[g[u][i]]);}
}int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> w[i];}for (int i = 1; i < n; i++) {/*鄰接表*/int a, b;cin >> a >> b;g[a].push_back(b);}dfs(1);cout << f[1][w[1]] << endl;return 0;
}? ? ? ? 通過的測試點如下：
? ? ? ? 比上次多了兩個，呃，但是我想的應該是除了AC就是TLE，這顯然不滿足。最后我發現了這個致命的問題，雖然用了動態規劃，但動態規劃只造成了局部最優（每一個父節點與它的子節點），局部最優不代表全局最優，現在應該算是貪心，所以應該還有一層動態規劃。
? ? ? ? 這里又發現一個問題！！我們來看輸入，“每行兩個整數表示樹上的一條邊連接的兩個結點”假設為a,b；這里并沒有說輸入的兩個數順序是a是b的入度，或者a是b的出度。題目中也沒有明確說明哪個是根節點，但樣例中是1，所以我們只能推測小數在前，即為根節點和父節點，故修改輸入代碼：
for (int i = 1; i < n; i++) {/*鄰接表*/int a, b;cin >> a >> b;if(a>b) swap(a,b);g[a].push_back(b);}? ? ? ? 多過了一個測試點：?
? ? ? ? 這兩層動態規劃是難到我了，我感覺應該是繞到坑里了，所以我就直接去看洛谷題解了。 關鍵詞：樹形DP、分組背包。
試題 H: 裝修報價(20分)
? ? ? ? 洛谷鏈接：P12137 [藍橋杯 2025 省 B] 裝修報價 - 洛谷
【輸入格式】
第一行輸入一個整數 N ，表示裝修相關費用的項數。第二行輸入 N 個非負整數 A 1 , A 2 , . . . , A N ，表示各項費用。
【輸出格式】
輸出一個整數，表示所有可能的總和對 10 9 + 7 取余后的結果。
?【樣例輸入】
30 2 5
【樣例輸出】
11
【樣例說明】
對于輸入樣例中的三個數 A = [0 , 2 , 5] ，所有可能的運算符組合共有 9 種。計算結果如下：0 ⊕ 2 ⊕ 5 = 7 ,0 ⊕ 2 + 5 = 7 ,0 ⊕ 2 ? 5 = ? 3 ,0 + 2 ⊕ 5 = 7 ,0 + 2 + 5 = 7 ,0 + 2 ? 5 = ? 3 ,0 ? 2 ⊕ 5 = ? 7 ,0 ? 2 + 5 = 3 ,0 ? 2 ? 5 = ? 7 .所有結果的總和為：7 + 7 + ( ? 3) + 7 + 7 + ( ? 3) + ( ? 7) + 3 + ( ? 7) = 1111 對 10 9 + 7 取余后的值依然為 11 ，因此，輸出結果為 11 。
【評測用例規模與約定】
對于 30 % 的評測用例， 1 ≤ N ≤ 13 ， 0 ≤對于 60 % 的評測用例， 1 ≤ N ≤ 10 3 ， 0 ≤對于 100 % 的評測用例， 1 ≤ N ≤ 10 5 ， 0 ≤
? ? ? ? 通過dfs搜索，應該是能得到部分分的，但是考試時我沒寫這道題，因為我忘記了異或是什么。。。。dfs暴力我就不演示了，懶得寫了。
? ? ? ? AC題解，也是先找規律。。。具體可以看洛谷題解。正和負相互抵消了。
吐槽
? ? ? ? 感覺藍橋杯的題更適合高中、初中的同學來寫，今年都是些規律題，與CSP、CCSP差遠了。而且今年的提交方式已經和計挑賽有的一拼了，只能提交，不能調試（模擬賽還能知道答案是否正確，到正式比賽卻又換了）。
