题目描述在一个蚂蚁王国中有mmm只蚂蚁包括Carl\texttt{Carl}Carl要沿着Carl\texttt{Carl}Carl预先走出的路径前进。Carl\texttt{Carl}Carl从原点(0,0)(0, 0)(0,0)出发沿若干条平行于坐标轴的线段行走最终钻入终点。Carl\texttt{Carl}Carl在行走过程中会在每个格子留下气味即他离开该格子时的方向。其他蚂蚁从原点出发按照Carl\texttt{Carl}Carl留下的气味方向决定下一步走向。当多只蚂蚁相遇时优先级规则决定谁先走。计算Carl\texttt{Carl}Carl完成时间、所有蚂蚁完成的顺序以及最后一只蚂蚁的完成时间。输入格式第一行一个整数TTT表示测试用例数量。每个测试用例第一行三个整数nnn、mmm、ddd1≤n≤501 \le n \le 501≤n≤501≤m≤1001 \le m \le 1001≤m≤1001≤d≤1001 \le d \le 1001≤d≤100。接下来nnn行每行两个整数xxx、yyy−100≤x,y≤100-100 \le x, y \le 100−100≤x,y≤100表示 Carl 路径的端点按行走顺序给出。路径从(0,0)(0,0)(0,0)开始由平行于坐标轴的线段组成且线段之间除端点外不相交。输出格式对于每个测试用例输出Case C: Carl finished the path at time t1 The ants finished in the following order: a1 a2 ... am The last ant finished the path at time t2其中CCC为测试用例编号aia_iai​为蚂蚁编号按完成顺序排列t1t_1t1​和t2t_2t2​分别为Carl\texttt{Carl}Carl和最后一只蚂蚁的完成时间。相邻测试用例之间输出一个空行。样例输入2 4 7 4 0 4 2 4 2 2 -2 2 4 7 2 0 4 2 4 2 2 -2 2输出Case 1: Carl finished the path at time 13 The ants finished in the following order: 0 2 1 3 4 5 6 The last ant finished the path at time 29 Case 2: Carl finished the path at time 13 The ants finished in the following order: 0 4 1 5 2 6 3 The last ant finished the path at time 19题目分析本题是一道离散时间模拟问题核心难点在于路径表示Carl\texttt{Carl}Carl的路径由若干水平或垂直线段组成需要转换为逐格移动的方向序列。气味传播Carl\texttt{Carl}Carl在路径上每走一步会在当前格子留下他离开时的方向后续蚂蚁会依据该方向前进。蚂蚁优先级在同一格子相遇时比较每只蚂蚁已行走步数即沿Carl\texttt{Carl}Carl原始路径上的长度步数大的优先。如果步数相同则比较在该格子等待的时间等待更久的优先。阻塞传播若一只蚂蚁被其他蚂蚁阻塞而阻塞它的蚂蚁可以移动则它也可以移动。起点特殊处理Carl\texttt{Carl}Carl离开起点后起点才释放给后续蚂蚁使用。由于蚂蚁数量较少m≤100m \le 100m≤100路径总长度不超过n⋅100≤5000n \cdot 100 \le 5000n⋅100≤5000因此可以采用按秒模拟的方法。解题思路1. 路径预处理将输入线段转换为逐格方向序列road[]使用四个方向常量dx[4] {-1,0,1,0}dy[4] {0,1,0,-1}。从(0,0)(0,0)(0,0)开始按给定端点逐格移动记录每一步的方向。2. 坐标偏移原始坐标范围是[−100,100][-100,100][−100,100]直接作为数组下标会越界。因此引入OFFSET 100将所有坐标映射到[0,200][0,200][0,200]用二维数组存储气味和占用信息。3. 数据结构smell[x][y]格子(x,y)(x,y)(x,y)的气味方向Carl\texttt{Carl}Carl最后一次离开时的方向。occupied[x][y][d]格子(x,y)(x,y)(x,y)上方向为ddd的蚂蚁编号−1-1−1表示无。ants[i]第iii只蚂蚁的状态位置、步数、等待时间、方向、是否完成。road[]Carl\texttt{Carl}Carl的路径方向序列。4. 模拟流程主循环按秒递增时间now直到所有蚂蚁完成Carl\texttt{Carl}Carl移动如果now cnt更新当前格子的气味Carl\texttt{Carl}Carl走一步记录终点。生成新蚂蚁每隔DDD秒如果起点未被占用生成一只新蚂蚁起点坐标(OFFSET, OFFSET)。模拟所有蚂蚁调用simulate()处理移动、冲突、阻塞。simulate()函数细节第一轮对每只蚂蚁检查所在格子是否有其他方向上的蚂蚁。如果有比较等待时间和步数决定当前蚂蚁是否要等待。第二轮阻塞传播若有蚂蚁被阻塞但它的目标格子被一只可以移动的蚂蚁占据则它可以移动。反复传播直到稳定。更新状态根据wait标志更新每只蚂蚁的步数、等待时间并清除旧格子的占用。执行移动对可移动的蚂蚁按气味方向移动一步。若到达终点记录完成顺序否则在新格子记录占用。5. 优先级与阻塞传播优先级比较的关键代码if(ants[t].waitants[i].wait||(ants[t].waitants[i].waitants[t].walkedants[i].walked))wait[i]1;这里wait[i] 1表示当前蚂蚁需要等待因为格子里有优先级更高的蚂蚁。阻塞传播if(!wait[i]!ants[i].done){intdsmell[ants[i].x][ants[i].y];intxants[i].xdx[d],yants[i].ydy[d];inttoccupied[x][y][d];if(t0wait[t])wait[i]1;}即如果一只蚂蚁不需要等待但它要去的格子有另一只在等待的蚂蚁那么它也要等待。6. 复杂度分析路径长度L≤5000L \le 5000L≤5000。每秒模拟O(m)O(m)O(m)只蚂蚁每只蚂蚁检查444个方向。总时间TTT不超过Lm⋅d延迟L m \cdot d \text{延迟}Lm⋅d延迟约为O(104)O(10^4)O(104)。总体复杂度O(LT⋅m)O(L T \cdot m)O(LT⋅m)完全可行。代码实现// Carl the Ant// UVa ID: 1028// Verdict: Accepted// Submission Date: 2026-06-15// UVa Run Time: 0.060s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintdx[4]{-1,0,1,0},dy[4]{0,1,0,-1},OFFSET100;structAnt{intx,y,walked,wait,dir,done;};intN,M,D;intcnt,finished,born,now,ex,ey;introad[210*210],smell[210][210],occupied[210][210][4],order[110],wait[110];Ant ants[110];voidinitialize(){memset(occupied,-1,sizeofoccupied);cinNMD;intcx0,cy0;cnt0;for(inti0;iN;i){intnx,ny;cinnxny;intd;if(cxnx)d0;elseif(cyny)d1;elseif(cxnx)d2;elsed3;while(cx!nx||cy!ny){road[cnt]d;cxdx[d],cydy[d];}}finishedborn0;}voidsimulate(){memset(wait,0,sizeofwait);for(inti0;iborn;i)if(!ants[i].done){intxants[i].x,yants[i].y;for(intd0;d4;d){inttoccupied[x][y][d];if(t0)if(ants[t].waitants[i].wait||(ants[t].waitants[i].waitants[t].walkedants[i].walked)){wait[i]1;break;}}}intchanged;do{changed0;for(inti0;iborn;i)if(!wait[i]!ants[i].done){intdsmell[ants[i].x][ants[i].y];intxants[i].xdx[d],yants[i].ydy[d];inttoccupied[x][y][d];if(t0wait[t]){wait[i]changed1;continue;}}}while(changed);for(inti0;iborn;i)if(!ants[i].done)if(!wait[i]){ants[i].walked;ants[i].wait0;occupied[ants[i].x][ants[i].y][ants[i].dir]-1;}elseants[i].wait;for(inti0;iborn;i)if(!wait[i]!ants[i].done){intxants[i].x,yants[i].y;if(xOFFSETyOFFSETi!born-1)occupied[OFFSET][OFFSET][smell[OFFSET][OFFSET]]i1;intdsmell[x][y];ants[i].xdx[d],ants[i].ydy[d],ants[i].dird;if(ants[i].xexants[i].yey){order[finished]i;ants[i].done1;}elseoccupied[ants[i].x][ants[i].y][d]i;}}voidsolve(intcs,intT){initialize();intcxOFFSET,cyOFFSET;exey-1;for(now0;finishedM;now){if(nowcnt){smell[cx][cy]road[now];cxdx[road[now]],cydy[road[now]];if(nowcnt-1)excx,eycy;}if(now%D0bornM){intsdsmell[OFFSET][OFFSET];if(occupied[OFFSET][OFFSET][sd])occupied[OFFSET][OFFSET][sd]born;ants[born]{OFFSET,OFFSET,0,0,sd,0};}simulate();}coutCase cs:\n;coutCarl finished the path at time ants[0].walked1\n;coutThe ants finished in the following order:\n;for(inti0;iM;i)coutorder[i] \n[iM-1];coutThe last ant finished the path at time now1\n;if(csT)cout\n;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intT;cinT;for(intcs1;csT;cs)solve(cs,T);return0;}总结本题的核心技巧包括离散时间模拟按秒推进每步处理所有蚂蚁的移动、冲突、阻塞。优先级的两阶段判断先根据步数和等待时间确定等待关系再通过阻塞传播完善依赖。气味方向的动态更新Carl\texttt{Carl}Carl每走一步更新当前格子的气味后续蚂蚁据此决定方向。坐标偏移将原始坐标[−100,100][-100,100][−100,100]映射到[0,200][0,200][0,200]避免数组下标越界。独立完成标记使用done字段标记已完成的蚂蚁避免与坐标值混淆。本题是模拟题的典型代表要求对细节的精确把握。掌握按秒推进、优先级传播、阻塞处理等技巧对解决类似复杂模拟问题有很大帮助。