P6219 题解

发表于
很巧妙的构造题

总体思路

将图分为若干层，$1$ 号节点在第一层，$N$ 号节点在最后一层，除 $1$ 号节点外只有相邻的两层之间有边。

手玩一下前两个Subtask，我们可以推断，当我们在新的一层加入 $M$ 个节点时，我们会把所有 $tns(1,x)$ 的总和乘上 $-(M-1)$。 同时，很显然的可以知道， $tns(1,N)=-\sum_{i=1}^{n-1}tns(1,i)$。如果我们把 $K$ 进行二进制拆分，那么我们只要每次在新的一层加入 $3$ 个节点，我们就能使 $tns(1,x)$ 的总和乘上 $-2$，所有我们一定能用至多 $3+(i-1)\times9$ 个点算出 $K$。如果我们的符号反了，我们只需要在新的一层加入两个节点就可以使总的结果乘上 $-1$。

现在的问题只剩下如何在某一个二进制位加上 $1$ 了。如果这个问题解决了，我们就可以用若干次乘二和加一的操作表示出 $K$ 的二进制拆分，也就是得到答案。如果当前的总和是负的，我们只用在当前层新建一个节点并从 $1$ 号节点向他连边。类似的，如果当前的总和是正的，先将其变为负的，再执行上面的操作。也就是说，我们新开一层，新建 $2$ 个节点，并从上一层的每个节点向他们连边，从而使答案变成负的同时加上 $1$。

该算法能用少于 $16\times log_2(K)$ 的边得到答案。

以上内容由本人翻译自官方题解，并加入了一些自己的理解。

实现细节

  • 从高到低枚举二进制位的时候，要从最高的第二位开始枚举。
  • 正数的 $+1$ 操作是放在新的一层，该层有 $3$ 个节点（变号有两个，加一有一个），该层需要向下一层建边。
  • 用于判断符号的计数器要初始化为 $-1$。

丑陋的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
vector<int> nd[205];//存每一层的结点
void get(int x){//二进制拆分
	x=abs(x);
	while(x){
		num[wei++]=x&1ll;
		x>>=1ll;
	}
}
int id(int x,int y){//该函数没用
	return (x-1)*3+y+1;
}
void add(int x,int y){//记录答案
	ax[++tot]=x,ay[tot]=y;
}
signed main(){
	cin>>k;
	if(k==0){
		printf("3 2\n1 2\n2 3");
		return 0;
	}
	if(k==1){
		printf("1 0");
		return 0;
	}
	get(k);
	if(k<0)k=-k,fh=1;
	nd[wei-1].push_back(++cnt);//第一层一个结点
	pre=wei-1,ce=wei-1;
	for(int i=wei-2;i>=0;i--){
		for(int j=0;j<3;j++){
			++cnt,nd[i].push_back(cnt);//执行乘操作
			for(int k=0;k<nd[pre].size();k++){
				add(nd[pre][k],cnt);
			}
		}
		pre=i;
		if((k>>i)&1ll){//需要加一操作
			if(sum<0){//当前符号是负的
				add(1,++cnt);
				nd[i].push_back(cnt);
				sum--;
			}
			else{//当前符号是正的
				++cnt,ce++,nd[ce].push_back(cnt);
				for(int j=0;j<nd[pre].size();j++){
					add(nd[pre][j],cnt);
				}
				++cnt,nd[ce].push_back(cnt);
				for(int j=0;j<nd[pre].size();j++){
					add(nd[pre][j],cnt);
				}//先变为负的
				add(1,++cnt),nd[ce].push_back(cnt);//再执行加一
				pre=ce;
				sum++;
				sum*=-1;
			}
		}
		sum*=-2;
	}
	//cout<<sum<<endl;
	if((sum>0&&fh)||(sum<0&&!fh)){//需要变号
		++cnt,nd[wei+1].push_back(cnt);
		for(int i=0;i<nd[pre].size();i++)add(nd[pre][i],cnt);
		++cnt,nd[wei+1].push_back(cnt);
		for(int i=0;i<nd[pre].size();i++)add(nd[pre][i],cnt);
		++cnt;
		add(cnt-2,cnt),add(cnt-1,cnt);
	}
	else{
		++cnt;
		for(int i=0;i<nd[pre].size();i++)add(nd[pre][i],cnt);
	}
	cout<<cnt<<' '<<tot<<endl;
	for(int i=1;i<=tot;i++)printf("%lld %lld\n",ax[i],ay[i]);