题解：P9101 [PA 2020] Skierowany graf acykliczny

JHR100330 · 2025-09-06 10:32:56 · 题解

由于 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 之间不能连边。

代码

#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;
}