题解 AT4433 【[ARC103C] Tr/ee】

· · 题解

神仙构造orz。

其实本质上这种构造树形态的题目，只要熟悉不同形态的树的性质就不难做了吧？

首先显然的是 s_n=0，s_1=1 ，否则无解。并且这东西是有对称性的，割掉一个大小为 k 的连通块一定也会割出一个大小为 n-k 的连通块。所以可以如此判断是否存在解。

这种构造，如果强行定义的话，可能存在某种套路。思考这一种比较自然的构造方式：找到最大的连通块，让其成为 1 的一棵子树，这样迭代做下去，最后再拿散点连上去，看上去有点合理，因为 1 的连通块必然存在。但仔细思考就会发现这样做会使得很多不应该存在的大小的连通块出现。

但是至少发现，连散点是个比较好的方式，而上一个方法欠缺的就是难以准确构造连通块。这就可以把思路引到「菊花」上。发现对于一个 k 阶菊花，只会产生大小为 k-1 和 1 的连通块。那么可以知道大概可以如此设计思路：枚举连通块大小 p ，如果 s_p=0 ，那么就应该把 p+2 号点也连在之前的某个菊花上 ，这样就不会出现 size=p 的连通块；否则把 p+2 连向单独拿出来作为一个新的新的菊花的重心连向 p+1 ，这样就会有 size=p 的连通块了。

形式化地讲，考虑设 1<q_1<q_2<\cdots <q_m<n 表示 \{s_n\} 中那些值为 1 的位置。那么构造出来的只需要是一个链套菊花，每个菊花大小是 q_k-q_{k-1} 即可（差分）。

显然这种构造方式能凑出所有 s_p=1 的 p 来。接下来只需要考虑这样做为什么也可以保证 s_p=0 的位置不构造出来。发现如果砍掉的边是菊花边而不是链边，那么只会有 n-1 和 1 这两种连通块；如果是链边，那么只会是某个 q_k 和 n-q_k ，由于之前已经判过了对称性，所以不难证明这样做是对的。

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std ;

const int N = 200010 ;

int n ;
int m ;
int top ;
int cnt ;
char s[N] ;
int sz[N] ;
int stk[N] ;

int main(){
    cin >> (s + 1) ;
    n = strlen(s + 1) ;
    if (s[1] == '0') return puts("-1"), 0 ;
    if (s[n] == '1') return puts("-1"), 0 ;
    for (int i = 1 ; i < n ; ++ i)
        if (s[i] != s[n - i]) return puts("-1"), 0 ;
    /*
    for (int i = 1 ; i < n ; ++ i)
        if (s[i] == '1') stk[++ top] = i ;
    stk[++ top] = n ; int k ; cnt = 0 ;
    while (top) sz[++ cnt] = stk[top --] ;
    for (int i = 1 ; i < cnt ; ++ i)
        printf("%d %d\n", i, i + 1), sz[i] -= sz[i + 1] ;
    k = cnt ;
    for (int i = 1 ; i <= cnt ; ++ i)
        for (int j = 1 ; j <= sz[i] ; ++ j)
            printf("%d %d\n", i, ++ cnt) ;
    */
    m = 1 ;
    for (int i = 1 ; i < n ; ++ i){
        cout << i + 1 << " " << m << endl ;
        if (s[i] == '1') m = i + 1 ;
    }
    return 0 ;
}