题解：P9101 [PA 2020] Skierowany graf acykliczny

由于

k

可能很大，而最多只能有

100

个点，考虑用二进制拼凑

k

。

按照如下方法构造：

此时到达

2

的方案数为

1

，到达

4

的方案数为

2

，到达

6

的方案数为

4

，以此类推，到达

i(i \equiv 0( \bmod \ 2))

的方案数为

2^{\frac{i}{2} -1}

。

此时偶数点均仅有一个出度，令终点始终为

100

，若

k

含

2^{\frac{i}{2} -1}

就从

i

连一条边到

100

即可。注意，

99

和

100

之间不能连边。

代码

CPP

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 100050;

int k;

int main() {
	cin >> k;
	cout << 100 << endl;
	for(int i = 1; i <= 98; i ++){
		if(i & 1) cout << i + 1 << " " << i + 2 << endl;
		else if((k & -k) == (1 << (i / 2 - 1))){
			k ^= (k & -k);
			cout << i + 1 << " " << 100 << endl;
		}
		else cout << i + 1 << " " << -1 << endl;
	}
	puts("-1 -1\n-1 -1");
    return 0;
}

题解：P9101 [PA 2020] Skierowany graf acykliczny

文章操作

代码

相关推荐

评论

题解：P9101 [PA 2020] Skierowany graf acykliczny