D - All Your Paths are Different Lengths
思路：
二进制构造
首先找到最大的t，使得2^t <= l
然后我们就能构造一种方法使得正好存在 0 到 2^t - 1 的路径
方法是：对于节点 i 到 i + 1，添加两条边，一条边权值是2^(i-1)，一条边权值是0
对于剩下的2^t 到 l-1的路径，我们考虑倍增地求，每次添加一条节点 v 到 节点 n 的边，边的权值是 X ，新增的路径是X 到 X + 2^(v-1) - 1
第一次的X是 2^t，之后每次倍增X增加 2^v，使得 X + 2^v <= l
代码：
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head vector<piii> ans; int main() { int l, t, n; scanf("%d", &l); for (int i = 25; ; i--) { if((1<<i) <= l) { t = i; n = t+1; break; } } for (int i = 1; i <= t; i++) { ans.pb({{i, i+1}, 1<<i-1}); ans.pb({{i, i+1}, 0}); } int res = l - (1<<t), now = (1<<t); for (int i = n-1; i >= 1; i--) { if((1<<i-1) <= res) { res -= 1<<i-1; ans.pb({{i, n}, now}); now += 1<<i-1; } } printf("%d %d ", n, (int)ans.size()); for (int i = 0; i < ans.size(); i++) printf("%d %d %d ", ans[i].fi.fi, ans[i].fi.se, ans[i].se); return 0; }