【题解】Tree 构造 ARC103E ——quhengyi11

喵呜

题目描述

规定 $s[i]=$树中是否存在一条边使得删掉后有联通块的 $size=i$

请构造一棵这样的树

naive 的思考

显然 $s[1]=1,s[n]=0,s[i]==s[n-i](i \in [1, n – 1])$就不用说了吧

然后我们可以发现题目给的条件就相当于 $s[i]=1$的时候你构造的树中要有一个子树的 $size=i$，反之亦然

考虑从小到大构造

记当前点为 $u$

如果 $s[u]=0$那么我们可以给它加一个兄弟节点，那么它的 size 不变，并且不会有其它大于 1 的新 size 产生

如果 $s[u]=1$那么我们就将当前的所有节点全部连到点 $u$上来，那样 $size[u]=u$并且除 $u$点以外不会产生新的 size

最后把剩下的点全跟 $n$点连上就好了。

#include<bits/stdc++.h> 
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
#define N 1000005
#define M 4000005
int n, f[N][2], a[N], tmp[2];
int main ()
{
    char c;
    while (c != '\n')
    {
        c = getchar();
        if (isdigit(c)) a[++n] = (c == '1');
    }
    if (!a[1] || a[n]) {printf("-1"); return 0;}
    fo (i, 1, n - 1) if (a[i] ^ a[n - i]) {printf("-1"); return 0;}
    int last = 1;
    fo (i, 2, n)
        if (a[i])
        {
            fo (j, last, i - 1)
                printf("%d %d\n", i, j);
            last = i;
        }
    printf("%d %d\n", last, n);
    return 0;
}