题目链接：ARC 102B

给定一个整数 $L$，构造一张满足如下条件的有向图。图中可以包含重边，可以证明这样的图一定是存在的。

• 这张图的点数 $n$ 至多为 $20$，点从 $1$ 到 $n$ 标号。
• 这张图的边数 $m$ 至多为 $60$，边的长度为 $[0, 10 ^ 6]$。
• 每条边从标号小的点连向标号大的点，也就是说 $1, 2, \cdots, n$ 是这张图的一种可能的拓扑序。
• 从点 $1$ 到 $n$ 有 $L$ 条不同的路径，这些路径的长度两两不同，长度分别为 $0$ 到 $L - 1$。

此处路径的长度为这条路径上所有边的长度之和。当两条路径包含的边的集合不同时，这两条路径是不同的。

数据范围：$2 \le L \le 10 ^ 6$。

Solution

发现 $2 ^ n =2 ^ {20} \approx 10 ^ 6$，于是考虑二进制拆分。我们构造一条类似链的东西：将 $n$ 个点排成一行，在 $i$ 和 $i + 1$ 之间连上 $2$ 条边，很显然这样有 $2 ^ {n - 1}$ 条不同的路径（此处满足 $2 ^ {n - 1} \le L$ 且 $n$ 为满足该式子的最大值）。

接下来考虑 $0$ 到 $L - 1$ 的路径长度。首先思考一下这 $2(n - 1)$ 条边的长度。有一个很直接的想法为：点 $i$ 到 $i + 1$ 的路径长度分别为 $0$ 和 $2 ^ {i - 1}$。

最后我们尝试给那些新加上的边赋上长度。我们从第 $n - 1$ 个点往前考虑，如果在这个点加上之前不能构成的值中的最小值得到的长度合法（小于 $L$），那么就加上边 $(i, n)$，长度为这个最小值。

讲得比较粗浅，具体实现详见代码。

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

Code

#include <cstdio>

int n, m, L;

struct Edge {
    int u, v, w;
    Edge(int _u = 0, int _v = 0, int _w = 0) {
        u = _u, v = _v, w = _w;
    }
} e[65];

void add(int u, int v, int w) {
    e[++m] = Edge(u, v, w);
}
int main() {
    scanf("%d", &L);
    for (; (1 << n) <= L; n++);
    for (int i = 1; i < n; i++) {
        add(i, i + 1, 1 << (i - 1));
        add(i, i + 1, 0);
    }
    int v = 1 << (n - 1);
    for (int i = n - 1; i >= 1; i--) {
        if (v + (1 << (i - 1)) - 1 < L) {
            add(i, n, v);
            v += 1 << (i - 1);
        }
    }
    printf("%d %d\n", n, m);
    for (int i = 1; i <= m; i++) {
        printf("%d %d %d\n", e[i].u, e[i].v, e[i].w);
    }
    return 0;
}