有趣的构造 Continuous City

· · 题解

一道有趣的构造题。

原有的题解都只讲了构造方法，没有做其它说明，看上去不明不白的，所以搞懂后自己写一篇。讲得比较详细。

情况一

因为要构造 $[1, 2^k]$ 每个数字各一个，而数据范围中点数又是 $32$, 启发我们进行二进制拆分。 另第 $i$ 个点表示 $2^i$，$i$ 走到 $i+1$ 就是这一位取上，不走就是不取上，所以从 $i$ 号点对所有大于 $i$ 的点连上一条 $2^i$ 的边，这样所有的走法就对应着每一个二进制位取不取，即 $00...001$ 到 $111...111$， 就是要求的 $[1, 2^k-1]$。如图。 [![6f4gUK.png](https://s4.ax1x.com/2021/03/20/6f4gUK.png)](https://imgtu.com/i/6f4gUK) 注意题目中要求点是从 $1$ 开始的。 ## 情况二 $L=1,R = 2^k+t

那么如果不是恰好的 2^k-1 怎么办呢? 考虑新开一个节点。

我们原来的图显然有这样一个性质，那就是从开始的节点到每一个节点 i 满足有长度为 [1,2^i-1] 恰好一条，所以对于 R 的二进制，从某一位开始截断向后的 00...000 到 11..111 都是有的，举个例子，如果 R 的二进制是 101000, 那么路径就必然包含长度 [100000, 100111] 的，而我们的 2 号节点恰好是满足起始点到它的路径 [001, 111] 的，所以对于 [100001, 100111]， 只需要连一条 2 号点到新来的那个点，长度为 100000 的就可以了。

那问题来了，这样一来我们就没有长度为 100000 和 101000 的这样两条路径了啊！原因是我们第一步中做的 [1, 2^k-1] 的做法没有包含左(0)右(2^k)端点，我们需要让其包含一个端点以覆盖所有情况。

改为 [1,2^k] 可以采用这样一个方法：把所有节点向后移一个编号，从新的起始点向所有的节点连一条长度为 1 边。

但对于最大的一位，前面没有东西了，这样一连有一条长度为 0 的边，但长度不能为 0, 为了解决这个问题，可以把 R 减去 1 的加边法做出来，再给每一个边加上一个 1。

对于上面那副图，若我们的输入是 10(即 (1010)_2), 那么就是这样子的了（经过加边和上述的修正后，并将节点从 1 开始编号）

(省略了 1 开始的边，不然图太糊了)

情况三

用情况二构造一个 L = 1, R' = R-L+1 的图，再开一个新节点，加一条原来最后一个节点到他的，长度为 L-1 的边就可以了。

代码

需要处理一些节点编号与幂之间关系的细节。

#include <cstdio>
#include <vector>
int L, R;
struct twt { int u, v, c; };
std::vector<twt> edge;
void add(int u, int v, int c) { edge.push_back((twt){u, v, c}); }
int solve(int L, int R) {
    if(L > 1) { // 情况三
        int n = solve(1, R-L+1);
        add(n, n+1, L-1);
        return n+1;
    }
    if((R & -R) == R) { // ex情况一
        int k = 0, R_ = R;
        while(R_) R_ /= 2, k++;
        k--;
        add(1, 2, 1);
        for(int i = 3; i <= k+2; i++) {
            add(1, i, 1);
            for(int j = 2; j < i; j++) add(j, i, (1 << (j-2)));
        }
        return k+2;
    }
    int n = 0; // 情况二
    while(1 << (n+1) <= R-1) n++;
    solve(1, 1 << n);
    add(1, n+3, 1);
    for(int i = 0; i <= n; i++)
        if((R-1) >> i & 1) 
            add(i+2, n+3, 1 + ((R - 1) >> (i + 1) << (i + 1)));
    return n+3;
}
int main() {
    scanf("%d%d", &L, &R);
    puts("YES");
    int n = solve(L, R);
    printf("%d %d\n", n, (signed)edge.size());
    for(int i = 0; i < (signed)edge.size(); i++) printf("%d %d %d\n", edge[i].u, edge[i].v, edge[i].c);
}