首页 > 其他分享 >【UVA 514】Rails 题解(栈+队列)

【UVA 514】Rails 题解(栈+队列)

时间:2023-10-06 16:02:54浏览次数:57  
标签:文件 队列 题解 队头 int 车厢 车站 UVA 514

PopPush市有一个著名的火车站。那个里的乡村是令人难以置信的丘陵。车站 建于上世纪。不幸的是,当时资金极其有限。有可能 仅建立表面轨迹。此外,事实证明,该站可能只是一个死胡同 (见图片),由于缺乏可用空间,它只能有一个轨道。 当地的传统是,每一列从A方向到达的火车都会继续朝A方向行驶 B与教练以某种方式重组。假设从A方向到达的列车 N≤1000节车厢,按递增顺序1、2、…、,N.列车重组主管必须 知道是否有可能在B方向继续指挥教练,以便他们的命令 是a1.a2,…,aN。帮助他并编写一个程序,决定是否有可能获得所需的 教练的顺序。你可以假设,在他们离开火车之前,单节车厢可以与火车断开 进入车站,他们可以自行移动,直到他们在B方向的轨道上 也可以假设在任何时候都可以根据需要在车站内设置任意数量的客车。 但一旦一辆客车进站,它就不能沿a方向返回轨道,也不能返回一次 它已沿方向B离开车站,它不能返回车站。

输入 输入文件由行块组成。除最后一个区段外,每个区段描述一列列车 对其重组提出更多要求。在块的第一行中,描述了整数N 在上面在块的下一行中的每一行中,N.最后一行 块仅包含“0”。 最后一个块仅包含一行包含“0”。 输出 输出文件包含与输入文件中具有排列的行相对应的行。A行 如果可以按照 输入文件的相应行。否则包含“否”。此外,后面还有一个空行 这些行对应于输入文件的一个块。输出文件中没有对应的行 到输入文件的最后一个“空”块。

【UVA 514】Rails 题解(栈+队列)_ci

Sample Input 5 1 2 3 4 5 5 4 1 2 3 0 6 6 5 4 3 2 1 0 0 Sample Output Yes No

Yes

思路

如果n不为0,且读入的车厢编号不为0,则读入车厢顺序,放入队列b。初始化队列a,将1~n入队。

如果队列a空,且队列b的队头不等于栈s栈顶,说明该情况不可能存在,跳出循环; 如果栈s非空且队列b的队头等于栈s的栈顶,让队列b队头出队且栈s栈顶出栈,车厢驶出车站到达B; 如果队列a非空,且队列a的队头和队列b的队头相等,让队列a和队列b的队头出队,车厢从A到达B; 如果队列a非空,将队列a的队头放入s后出队,车厢从A进入车站。 用while重复,直到将队列a和栈s清空。

队列a和栈s清空后,如果队列b非空,说明该情况不可能存在,输出No,否则输出Yes。

AC代码

/*
stack
AC
 */
#include <iostream>
#include <stack>
#include <queue>
#define AUTHOR "HEX9CF"
using namespace std;

int main()
{
    int n;
    while (cin >> n)
    {
        if (!n)
        {
            break;
        }
        int t;
        while (cin >> t)
        {
            stack<int> s;
            queue<int> a;
            queue<int> b;
            if (t)
            {
                b.push(t);
                for (int i = 1; i <= n; i++)
                {
                    a.push(i);
                }
                for (int i = 0; i < n - 1; i++)
                {
                    cin >> t;
                    b.push(t);
                    // cout << t << endl;
                }
            }
            else
            {
                break;
            }
            while (!(a.empty() && s.empty()))
            {
                if (a.empty() && (b.front() != s.top()))
                {
                    // A空且B与S不能消去
                    break;
                }
                else if (!s.empty() && (b.front() == s.top()))
                {
                    // B与S消去
                    b.pop();
                    s.pop();
                }
                else if (!a.empty() && (b.front() == a.front()))
                {
                    // A与B消去
                    b.pop();
                    a.pop();
                }
                else if (!a.empty())
                {
                    // A放进S
                    s.push(a.front());
                    a.pop();
                }
                // cout << b.empty() << endl;
            }
            if (b.empty())
            {
                cout << "Yes" << endl;
            }
            else
            {
                cout << "No" << endl;
            }
        }
        cout << endl;
    }
    return 0;
}

标签:文件,队列,题解,队头,int,车厢,车站,UVA,514
From: https://blog.51cto.com/HEX9CF/7724916

相关文章

  • 【题解 P4550】 收集邮票
    收集邮票题目描述有\(n\)种不同的邮票,皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买,每次只能买一张,并且买到的邮票究竟是\(n\)种邮票中的哪一种是等概率的,概率均为\(1/n\)。但是由于凡凡也很喜欢邮票,所以皮皮购买第\(k\)次邮票需要支付\(k\)元钱。现......
  • neovim的插件管理器vim-plug导致代码颜色不显示问题解决
    neovim的帮助文件路径F:\Programs\Neovim\share\nvim\runtime\docruntimepath的帮助文档路径F:\Programs\Neovim\share\nvim\runtime\doc\options.txt$VIM环境变量$VIM被用来确定Vim中不同的用户文件的位置,比如用户启动脚本“.vimrc”。这个是系统设置,详见startup。允许每......
  • 关于洛谷题解审核
    我想问一下,大家觉得题解的重点是什么?很显然是思路,代码的正确性,次要的才是格式。但是,洛谷对于题解格式的审核是不是有点过于严格了呢?比如说这段话:如果\(n\)为\(0\),那么便是无解。大家能一眼看出,后面多了空格吗?这种题解其实没什么大问题,别人看题解时根本不会在意这些......
  • 【bitset】【线段树】CF633G Yash And Trees 题解
    CF633G简单题。先看到子树加和子树质数个数和,果断转换为dfs序进行处理。既然有区间求和,考虑线段树。若对于每一个节点维护一个\(cnt\)数组,用二进制数\(x\)来表示,即当\(cnt_i=1\)时第\(i\)位为\(1\)。设当前节点为\(u\),左右子节点分别为\(ls\)和\(rs\)。发现......
  • 【倍增】P3422 [POI2005]LOT-A Journey to Mars 题解
    P3422一道有点意思的题。看到是一个环,先破环为链,即\(a_{n+i}=a_i,b_{n+i}=b_i\),此时就只需要跳到\(x+n\)而无需判环了。如果顺时针走:令\(sum_i=\sum\limits_{j=1}^{i}{a_j-b_j}\),当能从\(x\)跳到\(x+n\)时,有\[sum_{x-1}\lesum_x,sum_{x-1}\lesum_{x+1},\dot......
  • 【DP】ABC273F Hammer 2 题解
    ABC273F一道比较板的区间\(\text{dp}\)。先对坐标离散化,令离散化数组为\(v\)。令\(f_{i,j}\)表示能走到区间\([v_i,v_j]\)的最短路程,显然\(f\)数组初始为\(inf\)。但发现这样无法转移,可以再增加一维\(k\in\{0,1\}\),表示此时在\([v_i,v_j]\)的\(v_i/v_j\)处。......
  • 【线段树合并】CF1805E There Should Be a Lot of Maximums 题解
    CF1805E待补:有另解看到维护树上问题,可以想到线段树合并。但直接维护显然不行,要一点技巧。发现\(val\)的出现次数\(cnt_{val}\)如果\(\ge3\),那么一定是一个候选项,若\(cnt_{val}=1\),那么一定不能作为候选项。于是可以用权值线段树维护对于\(val\)有\(cnt_{val}=......
  • [ABC257F] Teleporter Setting 题解
    1.题目洛谷传送门2.思路我们可以把不确定的点当成真实存在的\(0\)号点,建边的时候就正常连即可。然后我们来看一个样例:1-2-03-4-5当我们把\(0\)号点看成\(3\)号点时,答案就是\(1\)号点到\(0\)号点的距离加上\(3\)号点到\(5\)号点的距离。然后我们再......
  • 【思维】【DP】ABC298Ex Sum of Min of Length 题解
    ABC298Ex简单题。因为有\(\min\)不好做,容易想到讨论\(d(i,L)\)和\(d(i,R)\)的大小。令\(p=\text{LCA}(L,R)\),\(dep_L>dep_R,dist=dep_L+dep_R-2\timesdep_p\),\(now\)满足\(dep_L-dep_{now}=\lfloor\dfrac{dist}{2}\rfloor\)则\(L\)一定在......
  • 【图论】【寻找性质】CF1151E Number of Components 题解
    CF1151E发现每一个\(f(l,r)\)中的连通块总是一条链(一棵树)。那么此时连通块的数量就等于点的数量减去边的数量。先考虑点的总数,一个价值为\(a_i\)的点一定是在\(l\leqslanta_i\)且\(r\geqslanta_i\)的\(f(l,r)\)中才会有一个贡献,根据乘法原理,它会产生\(a_i\time......