ACM模版

描述

题解

按照我的思路，这里我们首先通过第二个方法恢复到原序列，接着呢，就是按照一方法遍历一遍即可。

这里我们很容易想到，我们需要用到递归来恢复序列，那么怎么递归呢？仔细观察可以发现，方法二表示这个 pop 元素被压上了几个，那么我们可以将序列划分为两部分进行递归，一个是在该元素下的，一个是在该元素上的，所以呢，当我们处理过前者后，需要对该元素进行一次 push 操作，当我们处理过后者后，需要对该元素进行一次 pop 操作，这里我们可以使用 vector 来记录 push 和 pop 的过程，当然这部分用数组也是完全可以的。

另外，注意输入量有些感人，所以呢，注意输入输出外挂哦~~~

代码

#include <stdio.h>
#include <vector>

using namespace std;

const int MAXN = 1e6 + 5;

int sta[MAXN];
vector<int> vi;

// 1 push 0 pop
void solve(int l, int r)
{
    if (l > r)
    {
        return ;
    }
    solve(l, r - sta[r] - 1);
    vi.push_back(1);
    solve(r - sta[r], r - 1);
    vi.push_back(0);
}

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

inline void out(int x)
{
    if (x > 9)
    {
        out(x / 10);
    }
    putchar(x % 10 + '0');
}

int main()
{
    int n;
    scan_d(n);

    for (int i = 1; i <= n; i++)
    {
        scan_d(sta[i]);
    }
    solve(1, n);

    int res = 0;
    bool flag = true;
    for (int i = 0; i < vi.size(); i++)
    {
        if (vi[i] == 1)
        {
            res++;
        }
        else
        {
            if (flag)
            {
                flag = false;
            }
            else
            {
                putchar(32);
            }
            out(res);
        }
    }

    return 0;
}