题面

题意

你有一个数字串，开始为空，每轮你可以进行下面两个操作中的一个：

1. 从末尾删除若干个数字（可以为 $0$ 个）然后把删除后的数字串的最后一个元素加一。
2. 将数字 $1$ 加入到数字串的末端。

现在告诉你你一共进行了 $n$ 次这样的操作，并且告诉你每一次操作完后数字串末尾的数字，让你找到一种可行的方案，并输出每次操作后的数字串。

分析

考虑如果你在某一次操作后看到的数字串末端元素值为 $x$：

1. 如果 $x=1$，上一次操作只可能是向数字串的末尾添加了一个 $1$。
2. 如果 $x > 1$，上一次操作只可能是删除了末尾若干个数字，删除后数字串末尾元素值为 $x-1$，然后让这个数字加一。

$x=1$ 时的构造方法是固定的，所以我们只需要关注 $x>1$ 时的情况。

容易发现，当数字串中含有多个值为 $x-1$ 的元素时，选取离末尾最近的值为 $x-1$ 的元素产生的答案比选离末尾较远的元素产生的答案不会更劣并且可能更优，所以当 $x>1$ 时我们从数列末尾删数直至末尾元素第一次为 $x-1$，然后停止继续操作，让尾部元素加一。

代码

使用栈模拟上述操作即可。

/**
 * @author Macesuted (macesuted@qq.com)
 * @copyright Copyright (c) 2021
 */

#include <bits/stdc++.h>
using namespace std;

#define maxn 1005

int a[maxn];

int n;

list<int> li;

void work(void) {
    cin >> n;
    for (register int i = 1; i <= n; i++) cin >> a[i];
    for (register int i = 1; i <= n; i++) {
        if (a[i] == 1)
            li.push_back(1);
        else {
            while (!li.empty() && li.back() != a[i] - 1) li.pop_back();
            if (!li.empty()) li.pop_back();
            li.push_back(a[i]);
        }
        for (list<int>::iterator j = li.begin(); j != li.end(); j++) {
            if (j != li.begin()) cout << '.';
            cout << *j;
        }
        cout << endl;
    }
    li.clear();
    return;
}