PerfectPan
;

AtCoder Regular Contest 102 D All Your Paths are Different Lengths

September 01, 2018

题目链接https://arc102.contest.atcoder.jp/tasks/arc102_b

题意:给定一个长度 LL,构造一个图,满足编号小的向编号大的连边,权值自己设,允许重边,使得一共有 LL条路,且每条路权值为 [0,L1][0,L-1] 中的一种且不重复,点数不超过 2020,边数不超过 6060

思路:用一个数系去完整的表示 [0,L1][0,L-1] 中每一个数,很容易想到用 22 进制,那我们先找一个最大的 nn,满足 2n1<=L12^n-1<=L-1,然后连边就很容易了,i>i+1i->i+1 连两条边权分别为 002i12^{i-1} 的边,代表选或不选,这样我们就可以表示出 [0,2n1][0,2^{n-1}] 里所有的数,然后考虑不满的部分,意识流一下应该能调出来。。大概就是考虑 10101001010100 这么一个数,那么 10100XX10100XX,即把那一位 11 翻转,则 XXXX 的部分就是选或不选都可以,所以我们把 33nn 连一条权值为 10100001010000 的边即可,以此类推,最后 11nn 连一条 L1L-1 的边即可。

#include <bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
	x=0;int f=0;char ch=getchar();
	while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x=f?-x:x;
}
const int N=20+5;
int L,i,j,m,POW[N];
vector<pair<int,int> >G[N];
int main(){
	read(L);
	int x=1,n=1;
	for (;x<L;x*=2) n++;
	if (x>L) n--;
	for (POW[0]=1,i=1;i<=20;i++) POW[i]=POW[i-1]*2;
	for (int i=1;i<n;i++){
		G[i].PB(MP(i+1,0));
		G[i].PB(MP(i+1,POW[i-1]));
		m+=2;
	}
	if (L>POW[n-1]){
		int tmp=L-1;
		for (i=0;i<n-1;i++){
			if ((L-1)&(1<<i)){
				tmp^=(1<<i);
				G[i+1].PB(MP(n,tmp));
				m++;
			}
		}
		G[1].PB(MP(n,L-1)),m++;
	}
	printf("%d %d\n",n,m);
	for (i=1;i<=n;i++){
		for (j=0;j<(int)G[i].size();j++){
			int v=G[i][j].first,w=G[i][j].second;
			printf("%d %d %d\n",i,v,w);
		}
	}
	return 0;
}

Yiming Pan

Written by Yiming Pan who lives and works in Hangzhou China. Welcome follow me on Github

Cannot load comments. Please check you network.