All Your Paths are Different Lengths
题目链接：
题解：
构造题有技巧，如果题目中要求了20和60，那就从这里入手好了。
发现没法入手因为太平凡了....
但是，他要求了每种值只出现了一次，容易联想到弄出来$log$个$2$的幂次。
诶？想到这里发现，$20$好像差不多就是$log$大小。
我们就放$20$个点，第$i$个点指向第$i + 1$个点两条边，$2^{i - 1}$和$0$。
发现不能放20个因为有可能爆，那就放恰好$log$个就好。
接着处理剩下的部分。
其实就是想数位$dp$一样，处理$L$的每个$1$，把当前的$1$变成$0$然后加上前面的所有$1$，看看后面还能有多少连上就好。
诶呀说不明白，看代码吧。
代码：
#include#define N 1000010 using namespace std;int Log[N];char *p1, *p2, buf[100000];#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )int rd() { int x = 0, f = 1; char c = nc(); while (c < 48) { if (c == '-') f = -1; c = nc(); } while (c > 47) { x = (((x << 2) + x) << 1) + (c ^ 48), c = nc(); } return x * f;}int bin[21];int a[20];struct Node { int x, y, z;}e[100];int main() { int n = rd(); n -- ; bin[0] = 1; for (int i = 1; i <= 20; i ++ ) { bin[i] = bin[i - 1] << 1; } int k = 0; int m = n; bool flag = false; while (m) { k ++ ; if (m % 2 == 0) { flag = true; } m /= 2; } int tot = 0; if (!flag) { cout << k + 1 << ' ' ; for (int i = 1; i <= k; i ++ ) { // i -> i + 1 tot ++ ; e[tot].x = i, e[tot].y = i + 1, e[tot].z = bin[i - 1]; tot ++ ; e[tot].x = i, e[tot].y = i + 1, e[tot].z = 0; } cout << tot << endl ; for (int i = 1; i <= tot; i ++ ) { printf("%d %d %d\n", e[i].x, e[i].y, e[i].z); } return 0; } // puts("Fuck"); cout << k << ' ' ; for (int i = 1; i < k; i ++ ) { tot ++ ; e[tot].x = i, e[tot].y = i + 1, e[tot].z = bin[k - i - 1]; tot ++ ; e[tot].x = i, e[tot].y = i + 1, e[tot].z = 0; } int cnt = 0; for (int i = 0; i <= 20; i ++ ) { if (n & bin[i]) { a[ ++ cnt] = i; } } int pre = bin[a[cnt]]; for (int i = cnt - 1; i; i -- ) { tot ++ ; e[tot].x = 1, e[tot].y = k - a[i], e[tot].z = pre; pre += bin[a[i]]; } tot ++ ; e[tot].x = 1, e[tot].y = k, e[tot].z = n; cout << tot << endl ; for (int i = 1; i <= tot; i ++ ) { printf("%d %d %d\n", e[i].x, e[i].y, e[i].z); } return 0;}
小结：Atcoder全是构造世人皆知.....这个因为都只出现一次，很容易想到二进制。然后数位dp就好了。