题目链接：ARC 103C

你有一个长度为 $n$ 的字符串 $s$。是否存在一棵有 $n$ 个节点的树满足如下条件？

• 节点从 $1$ 到 $n$ 标号。边从 $1$ 到 $n - 1$ 标号。
• 如果字符串 $s$ 的第 $i$ 个字符为 $1$，那么我们可以通过删掉其中一条边得到一个大小为 $i$ 的连通块。
• 如果字符串 $s$ 的第 $i$ 个字符为 $0$，那么我们不能通过删掉任何一条边得到一个大小为 $i$ 的连通块。

如果存在这样一棵树，求出这棵树。

数据范围：$2 \le n \le 10 ^ 5$。

Solution

通过如下限制条件可以判断无解情况：

• 大小为 $1$ 的连通块一定可以得到，大小为 $n$ 的一定不可以得到。
• 大小为 $i$ 和 $n - i$ 的连通块的情况一定相同。

接下来考虑构造方法。首先尝试找到一种树形结构，设其大小为 $m$，那么我们只能得到大小为 $1$ 和 $m - 1$ 的连通块。稍加思索可以发现这就是一个菊花图。

构造出这种结构的意义是：删掉这种结构上的任何一条边都是没有实际意义的。这样我们把若干个菊花图连在一起，那么只有删掉菊花图之间的连边才是有意义的。

假设我们将大小为 $a_1, a_2, \cdots, a_k$ 的菊花图连在一起，那么我们可以得到大小为 $1, a_1, a_1 + a_2, \cdots, \sum_{i = 1} ^ k a_i$ 等的连通块。直接这样构造一棵树就行了。

时间复杂度：$\mathcal O(n)​$。

Code

#include <cstdio>
#include <cstring>
#define fail return puts("-1"), 0

const int N = 1e5 + 5;

char s[N];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    if (s[1] == '0' || s[n] == '1') fail;
    for (int i = 1; i < n; i++) {
        if (s[i] != s[n - i]) fail;
    }
    for (int i = 2, r = 1; i <= n; i++) {
        printf("%d %d\n", r, i);
        if (s[i - 1] == '1') r = i;
    }
    return 0;
}