当前位置：首页 > news >正文

题解：洛谷 P2233 [HNOI2002] 公交车路线

news 2026/8/11 21:16:14

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P2233 [HNOI2002] 公交车路线

【题目描述】

在长沙城新建的环城公路上一共有8 88个公交站，分别为 A、B、C、D、E、F、G、H。公共汽车只能够在相邻的两个公交站之间运行，因此你从某一个公交站到另外一个公交站往往要换几次车，例如从公交站 A 到公交站 D，你就至少需要换3 33次车。

Tiger 的方向感极其糟糕，我们知道从公交站 A 到公交 E 只需要换4 44次车就可以到达，可是 tiger 却总共换了n nn次车，注意 tiger 一旦到达公交站 E，他不会愚蠢到再去换车。现在希望你计算一下 tiger 有多少种可能的乘车方案。

【输入】

仅有一个正整数n nn，表示 tiger 从公交车站 A 到公交车站 E 共换了n nn次车。

【输出】

输出一个正整数表示方案数，由于方案数很大，请输出方案数除以1000 10001000后的余数。

【输入样例】

【输出样例】

【核心思想】

问题分析：给定8 88个公交站环形排列（A~H，编号0 00~7 77），相邻站之间有直达路线。Tiger 从 A 站（编号0 00）出发，恰好换乘n nn次后到达 E 站（编号4 44），且一旦到达 E 站就不再换乘。求方案数对1000 10001000取模。这是一个线性 DP问题，核心在于状态转移时排除从 E 站出发的路径（吸收态）。
算法选择：
- 一维线性 DP（滚动数组）：f [ i ] [ j ] f[i][j]f[i][j]表示换乘i ii次后到达第j jj个站的方案数
- 环形邻接：每个站j jj的相邻站为( j − 1 + 8 ) % 8 (j-1+8) \% 8(j−1+8)%8和( j + 1 ) % 8 (j+1) \% 8(j+1)%8，A 和 H 也相邻
- 吸收态处理：到达 E 站（编号4 44）后停止，因此 E 站不能作为转移来源
关键步骤：
- 初始化：f [ 0 ] [ 0 ] = 1 f[0][0] = 1f[0][0]=1（换乘0 00次在 A 站，1 11种方案），其余为0 00
- DP 递推（i ii从1 11到n nn）：
  - 使用滚动数组c u r = i % 2 cur = i \% 2cur=i%2，p r e = ( i − 1 ) % 2 pre = (i-1) \% 2pre=(i−1)%2
  - 遍历当前站j jj（0 00到7 77）：
    - 计算左右邻站：l e f t = ( j − 1 + 8 ) % 8 left = (j-1+8) \% 8left=(j−1+8)%8，r i g h t = ( j + 1 ) % 8 right = (j+1) \% 8right=(j+1)%8
    - 状态转移：f [ c u r ] [ j ] = ( f [ p r e ] [ l e f t ] ⋅ [ l e f t ≠ 4 ] + f [ p r e ] [ r i g h t ] ⋅ [ r i g h t ≠ 4 ] ) m o d 1000 f[cur][j] = (f[pre][left] \cdot [left \neq 4] + f[pre][right] \cdot [right \neq 4]) \bmod 1000f[cur][j]=(f[pre][left]⋅[left=4]+f[pre][right]⋅[right=4])mod1000
    - 其中[ c o n d i t i o n ] [condition][condition]为指示函数，排除从 E 站转移来的路径
- 输出答案：f [ n % 2 ] [ 4 ] f[n \% 2][4]f[n%2][4]（换乘n nn次后到达 E 站的方案数）
时间/空间复杂度：
- 时间复杂度：O ( n × 8 ) = O ( n ) O(n \times 8) = O(n)O(n×8)=O(n)，每次换乘枚举8 88个站，每个站O ( 1 ) O(1)O(1)转移
- 空间复杂度：O ( 8 ) = O ( 1 ) O(8) = O(1)O(8)=O(1)，滚动数组仅维护两行
线性 DP 的核心思想：
- 状态定义清晰：f [ i ] [ j ] f[i][j]f[i][j]精确刻画"换乘i ii次后在j jj站"的方案数，满足无后效性
- 吸收态建模：E 站作为终点，到达后不再离开，通过禁止从 E 站向其他站转移实现，而非将 E 站方案数清零（因为需要统计最终到达 E 站的方案）
- 环形结构处理：取模运算( j ± 1 + 8 ) % 8 (j \pm 1 + 8) \% 8(j±1+8)%8优雅处理 A-H 的环形邻接
- 滚动数组优化：由于f [ i ] f[i]f[i]仅依赖f [ i − 1 ] f[i-1]f[i−1]，用两行数组交替使用，将空间从O ( n ) O(n)O(n)降至O ( 1 ) O(1)O(1)
- 适用于环形图上的路径计数、带吸收态的随机游走、有限状态转移类问题

【算法标签】

#普及+ #线性DP-一维

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=10000005,mod=1000;// N:最大换乘次数上限, mod:取模基数intf[2][8];// 滚动数组：f[cur][j]表示换乘i次后到达第j个公交站（0=A,1=B,...,4=E,...,7=H）的方案数intn;// tiger实际换乘的次数intmain(){cin>>n;// 读入换乘次数f[0][0]=1;// 初始状态：换乘0次时在A站（编号0），方案数为1for(inti=1;i<=n;i++)// 外层循环：枚举每次换乘{intcur=i%2;// 当前轮次的数组下标（滚动数组优化空间）intpre=(i-1)%2;// 上一轮次的数组下标for(intj=0;j<8;j++)// 内层循环：枚举当前所在的公交站（0~7对应A~H）{// 计算当前站j的左右相邻站（环形结构：A和H也相邻）intleft=(j-1+8)%8,right=(j+1)%8;intsum=0;// 累加到达当前站的方案数// 可以从左邻站到达当前站，但不能从E站（编号4）转移（到达E就停止）if(left!=4)sum+=f[pre][left];// 可以从右邻站到达当前站，同样不能从E站转移if(right!=4)sum+=f[pre][right];f[cur][j]=sum%mod;// 对1000取模存储}}// 输出换乘n次后到达E站（编号4）的方案数cout<<f[n%2][4]<<endl;return0;}