题解 CF1479C Continuous City
一道有趣的构造题。
原有的题解都只讲了构造方法,没有做其它说明,看上去不明不白的,所以搞懂后自己写一篇。讲得比较详细。
情况一
时
因为要构造 每个数字各一个,而数据范围中点数又是 , 启发我们进行二进制拆分。
另第 个点表示 , 走到 就是这一位取上,不走就是不取上,所以从 号点对所有大于 的点连上一条 的边,这样所有的走法就对应着每一个二进制位取不取,即 到 , 就是要求的 。如图。
注意题目中要求点是从 开始的。
情况二
那么如果不是恰好的 怎么办呢? 考虑新开一个节点。
我们原来的图显然有这样一个性质,那就是从开始的节点到每一个节点 满足有长度为 恰好一条,所以对于 的二进制,从某一位开始截断向后的 到 都是有的,举个例子,如果 的二进制是 , 那么路径就必然包含长度 的,而我们的 号节点恰好是满足起始点到它的路径 的,所以对于 , 只需要连一条 号点到新来的那个点,长度为 的就可以了。
那问题来了,这样一来我们就没有长度为 和 的这样两条路径了啊!原因是我们第一步中做的 的做法没有包含左()右()端点,我们需要让其包含一个端点以覆盖所有情况。
改为 可以采用这样一个方法:把所有节点向后移一个编号,从新的起始点向所有的节点连一条长度为 边。
但对于最大的一位,前面没有东西了,这样一连有一条长度为 的边,但长度不能为 , 为了解决这个问题,可以把 减去 的加边法做出来,再给每一个边加上一个 。
对于上面那副图,若我们的输入是 (即 ), 那么就是这样子的了(经过加边和上述的修正后,并将节点从 开始编号)
(省略了 开始的边,不然图太糊了)
情况三
用情况二构造一个 的图,再开一个新节点,加一条原来最后一个节点到他的,长度为 的边就可以了。
代码
需要处理一些节点编号与幂之间关系的细节。
#include <cstdio>
#include <vector>
int L, R;
struct twt { int u, v, c; };
std::vector<twt> edge;
void add(int u, int v, int c) { edge.push_back((twt){u, v, c}); }
int solve(int L, int R) {
if(L > 1) { // 情况三
int n = solve(1, R-L+1);
add(n, n+1, L-1);
return n+1;
}
if((R & -R) == R) { // ex情况一
int k = 0, R_ = R;
while(R_) R_ /= 2, k++;
k--;
add(1, 2, 1);
for(int i = 3; i <= k+2; i++) {
add(1, i, 1);
for(int j = 2; j < i; j++) add(j, i, (1 << (j-2)));
}
return k+2;
}
int n = 0; // 情况二
while(1 << (n+1) <= R-1) n++;
solve(1, 1 << n);
add(1, n+3, 1);
for(int i = 0; i <= n; i++)
if((R-1) >> i & 1)
add(i+2, n+3, 1 + ((R - 1) >> (i + 1) << (i + 1)));
return n+3;
}
int main() {
scanf("%d%d", &L, &R);
puts("YES");
int n = solve(L, R);
printf("%d %d\n", n, (signed)edge.size());
for(int i = 0; i < (signed)edge.size(); i++) printf("%d %d %d\n", edge[i].u, edge[i].v, edge[i].c);
}