ARC102D（构造）

构造一个图，使得\(n \le 20,m\le 60\)，边从小的点连向大的点，并且从1到n的所有路径，长度与\([0, l-1]\)构成双射。

用二进制的思想……代码很鬼畜

#include <cstdio>

using namespace std;

const int maxn=25;

int l, n, src, dst, m;

int main(){

	scanf("%d", &l); --l;

	for (int i=l+1; i; i>>=1) ++n;

	m=n*2-2;

	for (int i=21; i>=0; --i) if ((l-(1<<n-1)+1)&(1<<i)) ++m;

	printf("%d %d\n", n, m);

	src=n; dst=1; int t=1;

	for (int i=1; i<n; ++i, t*=2){

		printf("%d %d %d\n", i, i+1, t);

		printf("%d %d %d\n", i, i+1, 0); }

	int nowe=(1<<(n-1)); l=l-nowe;

	while (l>=0){

		for (t=21; t>=0; --t) if (l-(1<<t)>=-1) break;

		printf("%d %d %d\n", t+1, src, nowe);

		nowe+=(1<<t); l-=(1<<t);

	}

	return 0;

}

巴特西

ARC102D（构造）

ARC102D（构造）

最新文章

热门文章