2025年藍(lán)橋杯c語言B組歷屆試題及答案問題描述：給定一個(gè)整數(shù)n（2≤n≤1000），計(jì)算1到n的所有排列中，相鄰兩個(gè)數(shù)的差的絕對(duì)值之和的平均值。結(jié)果保留兩位小數(shù)。輸入格式：輸入一個(gè)整數(shù)n。輸出格式：輸出平均值，保留兩位小數(shù)。輸入樣例1：3輸出樣例1：2.67輸入樣例2：2輸出樣例2：1.00解題思路：通過分析排列的數(shù)學(xué)規(guī)律，發(fā)現(xiàn)每個(gè)相鄰位置的差絕對(duì)值之和具有對(duì)稱性。對(duì)于n個(gè)數(shù)的排列，任意兩個(gè)不同的數(shù)a和b會(huì)在相鄰位置出現(xiàn)2(n-2)!次（a在前b在后或b在前a在后）。所有相鄰位置的總差和可推導(dǎo)為n(n-1)2(n+1)/3，排列總數(shù)為n!，因此平均值為(n2-1)/(3(n-2)!)。當(dāng)n=2時(shí)，直接計(jì)算得1.00；n≥3時(shí)按公式計(jì)算。代碼實(shí)現(xiàn)：```cinclude<stdio.h>intmain(){intn;scanf("%d",&n);if(n==2){printf("1.00\n");return0;}doublenumerator=(double)(nn1);doubledenominator=3.0;for(inti=1;i<=n2;i++){denominator=i;}doubleavg=numerator/denominator;printf("%.2f\n",avg);return0;}```2023年藍(lán)橋杯C語言B組試題：問題描述：給定一個(gè)n×n的矩陣，部分位置為-1（障礙物）。從左上角(0,0)出發(fā)，每一步只能向右或向下移動(dòng)，到達(dá)右下角(n-1,n-1)的路徑。求所有可行路徑中的最大數(shù)值和，若無法到達(dá)則輸出-1。輸入格式：第一行輸入n（2≤n≤100），接下來n行每行n個(gè)整數(shù)（-1≤數(shù)值≤1000）。輸出格式：輸出最大和或-1。輸入樣例1：31-13456789輸出樣例1：29解題思路：使用動(dòng)態(tài)規(guī)劃。定義dp[i][j]為到達(dá)(i,j)的最大和。初始化時(shí)處理起點(diǎn)和障礙物，第一行和第一列只能從左或上轉(zhuǎn)移。其他位置取上方和左方的最大值加上當(dāng)前值。若終點(diǎn)不可達(dá)則輸出-1。代碼實(shí)現(xiàn)：```cinclude<stdio.h>include<string.h>defineMAXN105defineINF-1e9intgrid[MAXN][MAXN];intdp[MAXN][MAXN];intmain(){intn;scanf("%d",&n);for(inti=0;i<n;i++){for(intj=0;j<n;j++){scanf("%d",&grid[i][j]);}}if(grid[0][0]==-1||grid[n-1][n-1]==-1){printf("-1\n");return0;}for(inti=0;i<n;i++){for(intj=0;j<n;j++){dp[i][j]=INF;}}dp[0][0]=grid[0][0];for(intj=1;j<n;j++){if(grid[0][j]!=-1&&dp[0][j-1]!=INF){dp[0][j]=dp[0][j-1]+grid[0][j];}}for(inti=1;i<n;i++){if(grid[i][0]!=-1&&dp[i-1][0]!=INF){dp[i][0]=dp[i-1][0]+grid[i][0];}}for(inti=1;i<n;i++){for(intj=1;j<n;j++){if(grid[i][j]==-1)continue;intup=dp[i-1][j];intleft=dp[i][j-1];if(up==INF&&left==INF)continue;dp[i][j]=(up>left?up:left)+grid[i][j];}}if(dp[n-1][n-1]==INF){printf("-1\n");}else{printf("%d\n",dp[n-1][n-1]);}return0;}```2024年藍(lán)橋杯C語言B組試題：問題描述：給定有向圖，求節(jié)點(diǎn)1到節(jié)點(diǎn)n的最短路徑長度及路徑數(shù)目（數(shù)目對(duì)1e9+7取模）。若不可達(dá)輸出-10。輸入格式：第一行m和n（2≤n≤1e5，1≤m≤2e5），后續(xù)m行每行u,v,w表示u到v權(quán)值w的有向邊。輸出格式：輸出最短路徑長度和路徑數(shù)目。輸入樣例1：33121231133輸出樣例1：21輸入樣例2：34121241131341輸出樣例2：22解題思路：使用Dijkstra算法求最短路徑，同時(shí)維護(hù)路徑數(shù)。優(yōu)先隊(duì)列優(yōu)化遍歷，當(dāng)找到更短路徑時(shí)更新距離和路徑數(shù)，等長時(shí)累加路徑數(shù)。代碼實(shí)現(xiàn)：```cinclude<stdio.h>include<stdlib.h>include<string.h>defineMOD1000000007defineMAXN100005defineMAXM200005defineINF1e18typedeflonglongll;structEdge{intv;llw;structEdgenext;}edges[MAXM],head[MAXN];intedge_cnt=0;structNode{lldist;intu;}heap[MAXN2];intheap_size=0;lldist[MAXN];intcnt[MAXN];intvis[MAXN];voidadd_edge(intu,intv,llw){edges[edge_cnt].v=v;edges[edge_cnt].w=w;edges[edge_cnt].next=head[u];head[u]=&edges[edge_cnt++];}voidheap_insert(lldist,intu){heap[heap_size].dist=dist;heap[heap_size].u=u;inti=heap_size++;while(i>0){intparent=(i1)/2;if(heap[parent].dist<=heap[i].dist)break;structNodetmp=heap[parent];heap[parent]=heap[i];heap[i]=tmp;i=parent;}}structNodeheap_extract(){structNoderes=heap[0];heap[0]=heap[--heap_size];inti=0;while(1){intleft=2i+1;intright=2i+2;intmin=i;if(left<heap_size&&heap[left].dist<heap[min].dist)min=left;if(right<heap_size&&heap[right].dist<heap[min].dist)min=right;if(min==i)break;structNodetmp=heap[i];heap[i]=heap[min];heap[min]=tmp;i=min;}returnres;}intmain(){intm,n;scanf("%d%d",&m,&n);for(inti=0;i<m;i++){intu,v;llw;scanf("%d%d%lld",&u,&v,&w);add_edge(u,v,w);}for(inti=1;i<=n;i++){dist[i]=INF;cnt[i]=0;vis[i]=0;}dist[1]=0;cnt[1]=1;heap_insert(0,1);while(heap_size>0){structNodenode=heap_extract();lld=node.dist;intu=node.u;if(vis[u])continue;vis[u]=1;if(u==n)break;for(structEdgee=head[u];e!=NULL;e=e->next){intv=e->v;llw=e->w;if(dist[v]>d+w){dist[v]=d+w;cnt[v]=cnt[u];heap_insert(dist[v],v);}elseif(dist[v]==d+w){cnt[v]=(cnt[v]+cnt[u])%MOD;}}}if(dist[n]==INF){printf("-10\n");}else{printf("%lld%d\n",dist[n],cnt[n]);}return0;}```2021年藍(lán)橋杯C語言B組試題：問題描述：給定兩個(gè)整數(shù)a和b（1≤a,b≤1e5），計(jì)算它們的最小公倍數(shù)（LCM）。輸入格式：輸入兩個(gè)整數(shù)a和b。輸出格式：輸出a和b的LCM。輸入樣例1：46輸出樣例1：12解題思路：利用最小公