题解 CF1479C Continuous City

一道有趣的构造题。

原有的题解都只讲了构造方法,没有做其它说明,看上去不明不白的,所以搞懂后自己写一篇。讲得比较详细。

情况一

L=1,R=2k1L = 1, R = 2^k-1

因为要构造 [1,2k][1, 2^k] 每个数字各一个,而数据范围中点数又是 3232, 启发我们进行二进制拆分。

另第 ii 个点表示 2i2^iii 走到 i+1i+1 就是这一位取上,不走就是不取上,所以从 ii 号点对所有大于 ii 的点连上一条 2i2^i 的边,这样所有的走法就对应着每一个二进制位取不取,即 00...00100...001111...111111...111, 就是要求的 [1,2k1][1, 2^k-1]。如图。

6f4gUK.png

注意题目中要求点是从 11 开始的。

情况二

L=1,R=2k+tL=1,R = 2^k+t

那么如果不是恰好的 2k12^k-1 怎么办呢? 考虑新开一个节点。

我们原来的图显然有这样一个性质,那就是从开始的节点到每一个节点 ii 满足有长度为 [1,2i1][1,2^i-1] 恰好一条,所以对于 RR 的二进制,从某一位开始截断向后的 00...00000...00011..11111..111 都是有的,举个例子,如果 RR 的二进制是 101000101000, 那么路径就必然包含长度 [100000,100111][100000, 100111] 的,而我们的 22 号节点恰好是满足起始点到它的路径 [001,111][001, 111] 的,所以对于 [100001,100111][100001, 100111], 只需要连一条 22 号点到新来的那个点,长度为 100000100000 的就可以了。

那问题来了,这样一来我们就没有长度为 100000100000101000101000 的这样两条路径了啊!原因是我们第一步中做的 [1,2k1][1, 2^k-1] 的做法没有包含左(00)右(2k2^k)端点,我们需要让其包含一个端点以覆盖所有情况。

改为 [1,2k][1,2^k] 可以采用这样一个方法:把所有节点向后移一个编号,从新的起始点向所有的节点连一条长度为 11 边。

但对于最大的一位,前面没有东西了,这样一连有一条长度为 00 的边,但长度不能为 00, 为了解决这个问题,可以把 RR 减去 11 的加边法做出来,再给每一个边加上一个 11

对于上面那副图,若我们的输入是 1010(即 (1010)2(1010)_2), 那么就是这样子的了(经过加边和上述的修正后,并将节点从 11 开始编号)

(省略了 11 开始的边,不然图太糊了)

6fIOXj.png

情况三

用情况二构造一个 L=1,R=RL+1L = 1, R' = R-L+1 的图,再开一个新节点,加一条原来最后一个节点到他的,长度为 L1L-1 的边就可以了。

代码

需要处理一些节点编号与幂之间关系的细节。

#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);
}