总体思路
将图分为若干层，\(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;
}
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]);
|