Continuous City
Description:
Some time ago Homer lived in a beautiful city. There were n blocks numbered from (1) to (n) and (m) directed roads between them. Each road had a positive length, and each road went from the block with the smaller index to the block with the larger index. For every two (different) blocks, there was at most one road between them.
Homer discovered that for some two numbers (L) and (R) the city was ((L, R)-continuous).
The city is said to be ((L, R)-continuous), if
- all paths from block (1) to block (n) are of length between (L) and (R) (inclusive); and
- for every (L leq d leq R), there is exactly one path from block (1) to block (n) whose length is (d).
A path from block (u) to block (v) is a sequence (u = x_0 o x_1 o x_2 o dots o x_k = v), where there is a road from block (x_{i-1}) to block (x_{i}) for every (1 leq i leq k). The length of a path is the sum of lengths over all roads in the path. Two paths (x_0 o x_1 o dots o x_k) and (y_0 o y_1 o dots o y_l) are different, if (k eq l) or (x_i eq y_i) for some (0 leq i leq min{k, l}).
After moving to another city, Homer only remembers the two special numbers (L) and (R) but forgets the numbers (n) and (m) of blocks and roads, respectively, and how blocks are connected by roads. However, he believes the number of blocks should be no larger than (32) (because the city was small).
As the best friend of Homer, please tell him whether it is possible to find a ((L, R)-continuous) city or not.
中文题面：
给你两个数 (L,R)，构造一张DAG满足从 (1) 到 (n) 的所有路径恰有 (R-L+1) 条 , 且路径长度值域恰好为 ([L,R]) 。构造的DAG的点数不超过(32)，DAG的边只能从小编号连向大编号.
Input:
The single line contains two integers (L) and (R) ((1 leq L leq R leq 10^6)).
Output:
If it is impossible to find a ((L, R)-continuous) city within (32) blocks, print "NO" in a single line.
Otherwise, print "YES" in the first line followed by a description of a ((L, R)-continuous) city.
The second line should contain two integers (n) ((2 leq n leq 32)) and (m) ((1 leq m leq frac {n(n-1)} 2)), where (n) denotes the number of blocks and (m) denotes the number of roads.
Then (m) lines follow. The i-th of the (m) lines should contain three integers (a_i, b_i) ((1 leq a_i < b_i leq n)) and (c_i) ((1 leq c_i leq 10^6)) indicating that there is a directed road from block (a_i) to block (b_i) of length (c_i).
It is required that for every two blocks, there should be no more than (1) road connecting them. That is, for every (1 leq i < j leq m), either (a_i eq a_j) or (b_i eq b_j).
Sample Input 1:
1 1
Sample Output 1:
YES
2 1
1 2 1
Sample Input 2:
4 6
Sample Output 2:
YES
5 6
1 2 3
1 3 4
1 4 5
2 5 1
3 5 1
4 5 1
Note:
In the first example there is only one path from block (1) to block (n = 2), and its length is (1).
In the second example there are three paths from block (1) to block (n = 5), which are (1 o 2 o 5) of length (4), (1 o 3 o 5) of length (5) and (1 o 4 o 5) of length (6).
Hint:
时间限制： (2s)
空间限制： (512M)
题目分析：
构造题，首先要看数据范围。我们发现 (L,R) 是能达到 (2^{20}) 级别的数，而 (n leq 32) ，因此不难想到二进制拆分。具体怎么做我们需要循序渐进地考虑。
1.如果 (L=1,R=2^k) :
(k=0) ： 直接在 (1) 和 (n=2) 之间连一条边即可。
(k>0) ：我们考虑构造 (k+2) 个点。假设第 (i (2 leq i leq k + 1)) 个点满足 ((1, 2^{i-2})-continuous) , 我们在 (1) 与 (k+2) 之间连一条长度为 (1) 的边，在 (i (2 leq i leq k + 1)) 与 (k+2) 之间连一条长度为 (2^{i-2}) 的边，此时就能满足 (k+2) 是 ((1, 2^{k})-continuous) 。
这种情况消耗的点数为 $ k+2 $ ，即 (log_2R).
2.如果 (L=1)：
先将 (R-1) 二进制拆分使得 (R-1=sum_{i=0}^{k} (p_i imes 2^{i})).
我们延续 (1) 的做法，先使用 $k+2 $ 个点满足第 (i (2 leq i leq k + 2)) 个点满足 ((1, 2^{i-2})-continuous)，
接下来的做法非常重要——
我们要构造第 (k+3) 个点满足 ((1, R)-continuous).
我们先在 (1) 与 $ k+3 $ 之间连一条长度为 (1) 的边，然后对于 $forall 2 leq i leq k+2 $ ，如果 (p_i=1) ，在 (i) 和 (k+3) 间连一条长度为 (sum_{j=i-1}^k (p_j imes 2^j)) 的边。
此时满足题意，消耗的点数为 (k+3) .
3.如果(L>1):
先在 (1) 和 (2) 之间连一条长度为 (L-1) 的边，剩下的部分同做法 (2) .
此时消耗的点数为 (k+4)
综上，(maxn = 23).
PS:我的做法需要特判 (L=R).
代码如下(马蜂很丑，不喜勿喷)——
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m,p[maxn],a[maxn],b[maxn],c[maxn];
inline int read(){
int ret=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-f;ch=getchar();}
while(isdigit(ch)) ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar();return ret*f;
}
int main(){
puts("YES");int L=read(),R=read();
if(L==R) cout<<2<<' '<<1<<'
'<<1<<' '<<2<<' '<<L<<'
',exit(0);
if(L==1){
int x=log2(R-1),sum=1;n=x+3;for(register int i=0;i<=x;i++) if((1<<i)&(R-1)) p[i]=1;
for(register int i=0;i<=x;i++) a[++m]=1,b[m]=i+2,c[m]=1;
for(register int i=0;i<x;i++) for(register int j=i+1;j<=x;j++) a[++m]=i+2,b[m]=j+2,c[m]=(1<<i);
a[++m]=1,b[m]=n,c[m]=1;for(register int i=x;i>=0;i--) if(p[i]==1) a[++m]=i+2,b[m]=n,c[m]=sum,sum+=(1<<i);
cout<<n<<' '<<m<<'
';for(register int i=1;i<=m;i++) cout<<a[i]<<' '<<b[i]<<' '<<c[i]<<'
';
}
else{
a[++m]=1,b[m]=2,c[m]=L-1;int x=log2(R-L),sum=1;n=x+4;
for(register int i=0;i<=x;i++) if((1<<i)&(R-L)) p[i+1]=1;
for(register int i=1;i<=x+1;i++) a[++m]=2,b[m]=i+2,c[m]=1;
for(register int i=1;i<=x;i++) for(register int j=i+1;j<=x+1;j++) a[++m]=i+2,b[m]=j+2,c[m]=(1<<(i-1));
a[++m]=2,b[m]=n,c[m]=1;for(register int i=x+1;i;i--) if(p[i]==1) a[++m]=i+2,b[m]=n,c[m]=sum,sum+=(1<<(i-1));
cout<<n<<' '<<m<<'
';for(register int i=1;i<=m;i++) cout<<a[i]<<' '<<b[i]<<' '<<c[i]<<'
';
}
return 0;
}