草庐IT

2022.10.30每日一题

Cocoicobird 2023-03-28 原文

Daimayuan Online Judge-出栈序列判断

题目描述

现在有一个栈，有 \(n\) 个元素，分别为 \(1,2,…,n\)。我们可以通过 push 和 pop 操作，将这 \(n\) 个元素依次放入栈中，然后从栈中弹出，依次把出栈的元素写下来得到的序列就是出栈序列。
比如 \(n=3\)，如果执行 push 1，push 2，pop，push 3，pop，pop，那么我们 pop 操作得到的元素依次是 \(2,3,1\)。也就是说出栈序列就是 \(2,3,1\)。
现在给定一个合法的出栈序列，请输出一个合法的由 push 和 pop 操作构成的操作序列。这里要求 push 操作一定是按 \(1,2,…,n\) 的顺序。

输入格式

第一行一个整数 \(n\)。接下来一行 \(n\) 个整数，表示出栈序列。

输出格式

输出 \(2n\) 行，每行一个 push 或 pop 操作，可以证明一个出栈序列对应的操作序列是唯一的。

样例输入1
3
2 3 1
样例输出1
push 1
push 2
pop
push 3
pop
pop
样例输入2
5
1 3 5 4 2
样例输出2
push 1
pop
push 2
push 3
pop
push 4
push 5
pop
pop
pop
数据范围

对于 \(100\%\) 的数据，保证 \(1≤n≤100000\)，输入一定是个合法的出栈序列。

解题思路

比较基础的模拟题。因为保证是以 \(1,2,3,...,n\) 的顺序进栈，那么我们只需要出栈情况，也就是栈顶元素为当前 \(a[i]\) 对应的元素，那么我们就可以出栈，\(i\) 后移一位。而进栈操作，只要不满足出栈规则，就一直进栈即可。本题记得特判一下栈为空的情况

C++代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;

int n;
int tt = 0;
int stk[N], a[N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &a[i]);
    int num = 1;
    for(int i = 1; i <= n; i ++)
    {
        while(!tt || stk[tt] != a[i])
        {
            printf("push %d\n", num);
            stk[++ tt] = num;
            num ++;
        }
        if(stk[tt] == a[i])
        {
            printf("pop\n");
            tt --;
        }
    }
    return 0;
}
202210codespaninline算法与数据结构

有关2022.10.30每日一题的更多相关文章

  1. 牛客网专项练习30天Pytnon篇第02天 - 2

    1.在Python3中，下列关于数学运算结果正确的是:（B）a=10b=3print(a//b)print(a%b)print(a/b)A.3，3，3.3333...B.3，1，3.3333...C.3.3333...，3.3333...，3D.3.3333...，1，3.3333...解析：    在Python中，//表示地板除（向下取整），%表示取余，/表示除（Python2向下取整返回3）2.如下程序Python2会打印多少个数:（D）k=1000whilek>1:    print(k)k=k/2A.1000 B.10C.11D.9解析：    按照题意每次循环K/2，直到K值小于等

  2. 由于 libgmp.10.dylib 的问题，Ruby 2.2.0 无法运行 - 2

    我刚刚安装了带有RVM的Ruby2.2.0，并尝试使用它得到了这个:$rvmuse2.2.0--defaultUsing/Users/brandon/.rvm/gems/ruby-2.2.0dyld:Librarynotloaded:/usr/local/lib/libgmp.10.dylibReferencedfrom:/Users/brandon/.rvm/rubies/ruby-2.2.0/bin/rubyReason:Incompatiblelibraryversion:rubyrequiresversion13.0.0orlater,butlibgmp.10.dylibpro

  3. ruby - ri 有空文件 – Ubuntu 11.10, Ruby 1.9 - 2

    我正在运行Ubuntu11.10并像这样安装Ruby1.9:$sudoapt-getinstallruby1.9rubygems一切都运行良好，但ri似乎有空文档。ri告诉我文档是空的，我必须安装它们。我执行此操作是因为我读到它会有所帮助:$rdoc--all--ri现在，当我尝试打开任何文档时:$riArrayNothingknownaboutArray我搜索的其他所有内容都是一样的。 最佳答案 这个呢？apt-getinstallri1.8编辑或者试试这个:(非rvm)geminstallrdocrdoc-datardoc-da

  4. ruby-on-rails - gem install rmagick -v 2.13.1 错误 Failed to build gem native extension on Mac OS 10.9.1 - 2

    我已经通过提供MagickWand.h的路径尝试了一切，我安装了命令工具。谁能帮帮我？$geminstallrmagick-v2.13.1Buildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingrmagick:ERROR:Failedtobuildgemnativeextension./Users/ghazanfarali/.rvm/rubies/ruby-1.8.7-p357/bin/rubyextconf.rbcheckingforRubyversion>=1.8.5...yescheckingfor/

  5. ruby - 安装 tiny_tds 在 mac os 10.10.5 上出现错误 - 2

    我正在使用macos，我想使用ruby​​驱动程序连接到sqlserver。我想使用tiny_tds，但它给出了缺少free_tds的错误，但它已经安装了。怎么能过这个？~brewinstallfreetdsWarning:freetds-0.91.112alreadyinstalled~sudogeminstalltiny_tdsBuildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingtiny_tds:ERROR:Failedtobuildgemnativeextension.完整日志如下:/System

  6. ruby - rails 3.2.2(或 3.2.1)+ Postgresql 9.1.3 + Ubuntu 11.10 连接错误 - 2

    我正在使用PostgreSQL9.1.3(x86_64-pc-linux-gnu上的PostgreSQL9.1.3，由gcc-4.6.real(Ubuntu/Linaro4.6.1-9ubuntu3)4.6.1，64位编译)和在ubuntu11.10上运行3.2.2或3.2.1。现在，我可以使用以下命令连接PostgreSQLsupostgres输入密码我可以看到postgres=#我将以下详细信息放在我的config/database.yml中并执行“railsdb”，它工作正常。开发:adapter:postgresqlencoding:utf8reconnect:falsedat

  7. ruby-on-rails - 在 osx 10.9.3 上使用 RVM 安装 ruby​​-1.9.3-p547 时出错 - 2

    如何解决这个错误:$rvminstall1.9.3Searchingforbinaryrubies,thismighttakesometime.Nobinaryrubiesavailablefor:osx/10.9/x86_64/ruby-1.9.3-p547.Continuingwithcompilation.Pleaseread'rvmhelpmount'togetmoreinformationonbinaryrubies.Checkingrequirementsforosx.Certificatesin'/usr/local/etc/openssl/cert.pem'arealr

  8. 映宇宙2022年营收63亿元：同比下降三成，毛利率提升4.3个百分点 - 2

    3月26日，映宇宙（HK:03700，即“映客”）发布截至2022年12月31日的2022年度业绩财务报告。财报显示，映宇宙2022年的总营收为63.19亿元，较2021年同期的91.76亿元下降31.1%。2022年，映宇宙的经营亏损为4698.7万元，2021年同期则为净利润4.57亿元；期内亏损（净亏损）为1.68亿元，2021年同期的净利润为4.33亿元；非国际财务报告准则经调整净利润为3.88亿元，2021年同期为4.82亿元，同比下降19.6%。 映宇宙在财报中表示，收入减少主要是由于行业竞争加剧，该集团对旗下产品采取更为谨慎的运营策略以应对市场变化。不过，映宇宙的毛利率则有所提升

  9. u盘安装系统(win10为例) - 2

    下载微PE工具箱进入官网下载微PE工具箱-下载 安装好后,打开微PE工具箱客户端,选择安装PE到U盘 PE壁纸可选择自己喜欢的壁纸,勾选上包含DOS工具箱,个性化盘符图标 下载原版系统进入网站下载镜像NEXT,ITELLYOU如果没有账号,注册一下就好进入选择开始使用选择win10 这里我们选择消费者版,用迅雷把BT种子下载下来 下面的两个盘符,是PE工具箱安装进U盘后,分成的盘符,注意EFI的盘符,这里面不能删东西,也不能添东西,另一个盘符可以当做正常的U盘空间使用,我们现在需要把下载下来的景象文件复制到正常的U盘空间中去 这个时候我们的系统U盘就只做好了 安装系统我们将U盘插入电脑,开机,

  10. ruby-on-rails - OSX 10.7.5 - Ruby on Rails LoadError : Could not open library 'sodium' : dlopen(sodium, 5) - 2

    输入rakedb:create后我得到:LoadError:Couldnotopenlibrary'sodium':dlopen(sodium,5):imagenotfound.Couldnotopenlibrary'libsodium.dylib':dlopen(libsodium.dylib,5):imagenotfound这里还有一些输出。/Users/Mao/.rvm/gems/ruby-2.0.0-p451/gems/ffi-1.9.3/lib/ffi/library.rb:133:in`blockinffi_lib'/Users/Mao/.rvm/gems/ruby-2.0

随机推荐