![打卡信奥刷题（3310）用C++实现信奥题 P9166 [省选联考 2023] 火车站](http://pic.xiahunao.cn/yaotu/打卡信奥刷题（3310）用C++实现信奥题 P9166 [省选联考 2023] 火车站)
P9166 [省选联考 2023] 火车站题目描述有n nn个火车站排成一条直线从1 11到n nn编号。一共有m mm条火车轨道每条轨道覆盖一段火车站区间[ l i , r i ] [l_i, r_i][li,ri]。对于一个被多条火车轨道覆盖的火车站火车在经过这里的时候可以在此处改变轨道。但是火车无法掉头只能朝着一个方向运行即只能一直往1 11的方向开或者一直往n nn的方向开。小 A 从火车站x xx出发即搭上了经过x xx的任意一列火车这列火车也可能是从车站x xx出发。这列火车可能行驶在火车站x xx所处的任一条轨道上其运行方向既可能是往1 11的方向开也可能是往n nn的方向开。小 A 上车后就开始昏睡直到乘坐的火车到达某条线路的终点站停下他才醒过来。问小 A 最后可能到达的车站。注意火车应运行至少一个车站且火车切换轨道后不会立刻停下来而是会继续沿着当前轨道前进。输入格式输入的第一行包含三个正整数n , m , x n, m, xn,m,x分别表示火车站的数量火车轨道的数量以及小 A 初始的起点。接下来m mm行每行包含两个正整数l i , r i l_i, r_ili,ri表示一条火车轨道运行的区间。输出格式输出一行包含若干个用单个空格分隔的正整数表示小 A 最后可能到达的车站按照车站编号升序排序输出。输入输出样例 #1输入 #17 5 4 3 4 4 6 1 3 5 7 4 6输出 #11 3 6 7说明/提示【样例 1 解释】火车从车站4 44出发沿着第一条轨道可以运行到终点3 33也可以接着沿第三条轨道运行到终点1 11。火车从车站4 44出发沿着第二条轨道可以运行到终点6 66也可以在车站5 55换到第四条轨道运行到终点7 77。所以最终按顺序输出1 , 3 , 6 , 7 1, 3, 6, 71,3,6,7。【数据范围】对于所有的数据保证1 ≤ n , m ≤ 2 × 10 5 1 \le n, m \le 2 \times 10^51≤n,m≤2×1051 ≤ x ≤ n 1 \le x \le n1≤x≤n1 ≤ l i r i ≤ n 1 \le l_i r_i \le n1≤liri≤n。测试点n , m ≤ n, m \len,m≤特殊性质150 5050无250 5050无35000 50005000无45000 50005000无55000 50005000无62 × 10 5 2 \times 10^52×105A72 × 10 5 2 \times 10^52×105A82 × 10 5 2 \times 10^52×105无92 × 10 5 2 \times 10^52×105无102 × 10 5 2 \times 10^52×105无特殊性质 A保证x 1 x 1x1。C实现#includebits/stdc.h#definelllonglong#defineF1(i,j,n)for(intij;in;i)#defineF2(i,j,n)for(intij;in;i--)usingnamespacestd;constintN1e610,NN1e410;ll n,m,k,x,y,u,w,cnt0,ans0,t0,l,r,len,T;ll miniINT_MAX,maxi0,Mod;boolv[N];structNode{ll l,r;}a[N];boolcmp(Node a,Node b){if(a.lb.l)returna.rb.r;returna.lb.l;}intmain(){cinmnx;F1(i,1,n){cina[i].la[i].r;//双端编号if(a[i].lxxa[i].r){//覆盖x号点即合法区间minimin(mini,a[i].l);//更新合法端点最值maximax(maxi,a[i].r);v[a[i].l]v[a[i].r]1;//线段两端标记为答案}}sort(a1,a1n,cmp);//排序F1(i,1,n)if(a[i].lminia[i].lmaxi)maximax(maxi,a[i].r);//左端与合法线段有重合部分更新最大值F2(i,n,1)if(a[i].rminia[i].rmaxi)minimin(mini,a[i].l);//右端与合法线段有重合部分更新最大值F1(i,1,n){if(a[i].lmini||a[i].rmaxi)continue;//不是合法线段if(a[i].rx)v[a[i].l]1;//由结论得该合法线段在x号点左边时左端点是答案elsev[a[i].r]1;//同上}F1(i,1,m)if(v[i]i!x)couti ;//此编号标记为答案且不是起点return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
打卡信奥刷题（3310）用C++实现信奥题 P9166 [省选联考 2023] 火车站
发布时间：2026/5/24 17:52:44
P9166 [省选联考 2023] 火车站题目描述有n nn个火车站排成一条直线从1 11到n nn编号。一共有m mm条火车轨道每条轨道覆盖一段火车站区间[ l i , r i ] [l_i, r_i][li,ri]。对于一个被多条火车轨道覆盖的火车站火车在经过这里的时候可以在此处改变轨道。但是火车无法掉头只能朝着一个方向运行即只能一直往1 11的方向开或者一直往n nn的方向开。小 A 从火车站x xx出发即搭上了经过x xx的任意一列火车这列火车也可能是从车站x xx出发。这列火车可能行驶在火车站x xx所处的任一条轨道上其运行方向既可能是往1 11的方向开也可能是往n nn的方向开。小 A 上车后就开始昏睡直到乘坐的火车到达某条线路的终点站停下他才醒过来。问小 A 最后可能到达的车站。注意火车应运行至少一个车站且火车切换轨道后不会立刻停下来而是会继续沿着当前轨道前进。输入格式输入的第一行包含三个正整数n , m , x n, m, xn,m,x分别表示火车站的数量火车轨道的数量以及小 A 初始的起点。接下来m mm行每行包含两个正整数l i , r i l_i, r_ili,ri表示一条火车轨道运行的区间。输出格式输出一行包含若干个用单个空格分隔的正整数表示小 A 最后可能到达的车站按照车站编号升序排序输出。输入输出样例 #1输入 #17 5 4 3 4 4 6 1 3 5 7 4 6输出 #11 3 6 7说明/提示【样例 1 解释】火车从车站4 44出发沿着第一条轨道可以运行到终点3 33也可以接着沿第三条轨道运行到终点1 11。火车从车站4 44出发沿着第二条轨道可以运行到终点6 66也可以在车站5 55换到第四条轨道运行到终点7 77。所以最终按顺序输出1 , 3 , 6 , 7 1, 3, 6, 71,3,6,7。【数据范围】对于所有的数据保证1 ≤ n , m ≤ 2 × 10 5 1 \le n, m \le 2 \times 10^51≤n,m≤2×1051 ≤ x ≤ n 1 \le x \le n1≤x≤n1 ≤ l i r i ≤ n 1 \le l_i r_i \le n1≤liri≤n。测试点n , m ≤ n, m \len,m≤特殊性质150 5050无250 5050无35000 50005000无45000 50005000无55000 50005000无62 × 10 5 2 \times 10^52×105A72 × 10 5 2 \times 10^52×105A82 × 10 5 2 \times 10^52×105无92 × 10 5 2 \times 10^52×105无102 × 10 5 2 \times 10^52×105无特殊性质 A保证x 1 x 1x1。C实现#includebits/stdc.h#definelllonglong#defineF1(i,j,n)for(intij;in;i)#defineF2(i,j,n)for(intij;in;i--)usingnamespacestd;constintN1e610,NN1e410;ll n,m,k,x,y,u,w,cnt0,ans0,t0,l,r,len,T;ll miniINT_MAX,maxi0,Mod;boolv[N];structNode{ll l,r;}a[N];boolcmp(Node a,Node b){if(a.lb.l)returna.rb.r;returna.lb.l;}intmain(){cinmnx;F1(i,1,n){cina[i].la[i].r;//双端编号if(a[i].lxxa[i].r){//覆盖x号点即合法区间minimin(mini,a[i].l);//更新合法端点最值maximax(maxi,a[i].r);v[a[i].l]v[a[i].r]1;//线段两端标记为答案}}sort(a1,a1n,cmp);//排序F1(i,1,n)if(a[i].lminia[i].lmaxi)maximax(maxi,a[i].r);//左端与合法线段有重合部分更新最大值F2(i,n,1)if(a[i].rminia[i].rmaxi)minimin(mini,a[i].l);//右端与合法线段有重合部分更新最大值F1(i,1,n){if(a[i].lmini||a[i].rmaxi)continue;//不是合法线段if(a[i].rx)v[a[i].l]1;//由结论得该合法线段在x号点左边时左端点是答案elsev[a[i].r]1;//同上}F1(i,1,m)if(v[i]i!x)couti ;//此编号标记为答案且不是起点return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
