2025年福建信息竞赛试题及答案

2025年福建信息竞赛试题及答案一、数字统计给定两个正整数L和R（1≤L≤R≤10¹⁸），请统计区间[L,R]内满足各位数字乘积是7的倍数的整数个数。输入格式：第一行包含两个整数L和R。输出格式：一个整数，表示符合条件的数的个数。样例输入：1100样例输出：28二、物流路径某物流网络由n个节点（城市）和m条双向道路组成，每条道路有长度d和最大载重w（即载重超过w的车辆无法通过）。现在需要将一批总重量为W的货物从节点A运到节点B，要求路径上所有道路的最大载重均不小于W。请找到满足条件的路径中总长度最短的，输出该长度。若不存在这样的路径，输出-1。输入格式：第一行包含四个整数n,m,A,B（节点编号从1到n）。接下来m行，每行四个整数u,v,d,w，表示u和v之间有一条长度d、最大载重w的道路。最后一行包含一个整数W。输出格式：一个整数，表示最短路径长度，或-1。样例输入：331312531310523243样例输出：7答案与解析数字统计解答解题思路：各位数字乘积是7的倍数的条件等价于：数字中包含至少一个0（乘积为0），或包含至少一个7且不包含0（乘积含7的因子）。由于L和R的范围极大（10¹⁸），直接遍历不可行，需用数位动态规划（数位DP）计算[0,R]和[0,L-1]的符合条件数，再求差值。数位DP状态设计：`pos`：当前处理到的位数（从高位到低位）。`has_zero`：前面各位是否包含0（前导零不计入，如数字“05”实际是“5”，无0）。`has_seven`：前面各位是否包含7。`tight`：当前位是否受限于原数的对应位（即前面的位是否与原数完全相同）。状态转移：遍历当前位可能的数字（0-9），根据`tight`判断是否受原数限制。若当前位选的数字小于原数对应位，则后续位不受限；若等于，则后续位仍受限。同时更新`has_zero`和`has_seven`的状态：若当前位是0且`has_zero`为false（非前导零），则`has_zero`变为true。若当前位是7，则`has_seven`变为true。结果计算：符合条件的数需满足`has_zero`为true（含0）或`has_seven`为true且`has_zero`为false（含7且无0）。最终答案为`f(R)f(L-1)`，其中`f(x)`表示[0,x]内符合条件的数的个数。代码实现（C++）：```cppinclude<bits/stdc++.h>usingnamespacestd;usingll=longlong;vector<int>get_digits(llx){vector<int>digits;if(x==0){digits.push_back(0);returndigits;}while(x>0){digits.push_back(x%10);x/=10;}reverse(digits.begin(),digits.end());returndigits;}lldfs(intpos,boolhas_zero,boolhas_seven,booltight,constvector<int>&digits,vector<vector<vector<vector<ll>>>>&dp){if(pos==digits.size()){return(has_zero||(has_seven&&!has_zero))?1:0;}if(!tight&&dp[pos][has_zero][has_seven][0]!=-1){returndp[pos][has_zero][has_seven][0];}intupper=tight?digits[pos]:9;llres=0;for(intd=0;d<=upper;++d){boolnew_tight=tight&&(d==upper);boolnew_has_zero=has_zero||(d==0&&!has_zero);//前导零不计入boolnew_has_seven=has_seven||(d==7);res+=dfs(pos+1,new_has_zero,new_has_seven,new_tight,digits,dp);}if(!tight){dp[pos][has_zero][has_seven][0]=res;}returnres;}llf(llx){if(x<0)return0;vector<int>digits=get_digits(x);intn=digits.size();vector<vector<vector<vector<ll>>>>dp(n,vector<vector<vector<ll>>>(2,vector<vector<ll>>(2,vector<ll>(2,-1))));returndfs(0,false,false,true,digits,dp);}intmain(){llL,R;cin>>L>>R;cout<<f(R)f(L1)<<endl;return0;}```物流路径解答解题思路：1.筛选符合条件的边：保留所有最大载重w≥W的边，构建新图。2.最短路径计算：在新图中，使用Dijkstra算法求节点A到B的最短路径。若A和B不连通，输出-1。Dijkstra算法优化：使用优先队列（最小堆）维护当前已知的最短路径，每次取出距离最小的节点，更新其邻接节点的距离。代码实现（C++）：```cppinclude<bits/stdc++.h>usingnamespacestd;usingpii=pair<int,int>;constintINF=0x3f3f3f3f;intmain(){intn,m,A,B;cin>>n>>m>>A>>B;vector<vector<pii>>adj(n+1);//adj[u]存储(v,d)for(inti=0;i<m;++i){intu,v,d,w;cin>>u>>v>>d>>w;//暂不筛选，后续根据W处理adj[u].emplace_back(v,d);adj[v].emplace_back(u,d);}intW;cin>>W;//重新构建只包含w≥W的边的邻接表vector<vector<pii>>valid_adj(n+1);//由于输入中边的w未存储，需重新读取（或修改输入方式）//这里假设重新读取输入（实际中可优化存储）rewind(stdin);cin>>n>>m>>A>>B;//跳过第一行for(inti=0;i<m;++i){intu,v,d,w;cin>>u>>v>>d>>w;if(w>=W){valid_adj[u].emplace_back(v,d);valid_adj[v].emplace_back(u,d);}}//Dijkstra求最短路径vector<int>dist(n+1,INF);dist[A]=0;priority_queue<pii,vector<pii>,greater<pii>>pq;//(distance,node)pq.emplace(0,A);while(!pq.empty()){auto[d,u]=pq.top();pq.pop();if(u==B)break;if(d>dist[u])continue;for(auto[v,len]:valid_adj[u]){if(dist[v]>dist[u]+len){dist[v]=dist[u]+len;pq.emplace(dist[v],v);}}}if(dist[B]==INF