【构造】Atcoder102 All Your Paths are Different Lengths

题意:

构造一个N个点，M条边的有向图，每条边严格从编号小的指向编号大的。允许重边。要求满足从1号点到N号点恰好有$L$种不同的路径。其路径总长度分别为0,1,2,……$L-1$

分析：

没看清题意wa了5次。。。

其实是非常简单的一道构造题。

具体的构造方法是：从i点到$i+1$点连一条0权边，一条$2^{i-1}$权边。这样就可以看做是一个n-1位二进制数。然后无非就是要满足最大的一个刚好为L-1。这个操作有点类似数位DP：先凑到一个没达到L的最大2的整次幂，然后从高到低依次考虑每一位，设当前位为i,用权值为$2^{i-1}$的倍数的边，加上之前凑的最大边权，连向N，直到达到L。（感觉我自己都看不太明白，可以参考一下代码）

#include<cstdio>
#include<cstring>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
typedef long long ll;
int n,l;
int cnt;
struct node{int u,v,val;    node () {}node (int u1,int v1,int val1):u(u1),v(v1),val(val1) {}
}pr[70];
int main(){SF("%d",&l);l--;int sum=1;int tot=0;for(tot=0;sum-1<=l&&tot<=19;tot++)sum*=2;sum/=2;for(int i=1;i<tot;i++){pr[++cnt]=node(i,i+1,0);pr[++cnt]=node(i,i+1,1<<(i-1));}int pre=0;int tot1=tot;tot--;sum/=2;while(pre<l){pre+=sum;for(;sum+pre+sum-1<=l;pre+=sum){pr[++cnt]=node(tot,tot1,sum+pre);}sum/=2;tot--;}PF("%d %d\n",tot1,cnt);for(int i=1;i<=cnt;i++)PF("%d %d %d\n",pr[i].u,pr[i].v,pr[i].val);
}