当前位置：首页 > news >正文

2020智算之道复赛 C - 有向无环图（思维+二进制拆分）

news 来源：原创 2024/5/17 6:38:13

在这里插入图片描述
首先最重要的一点是要知道图如何去画，以四个点为例，一般也许会画上下左右四个点的图，但是这样的话很难发现规律，实际上因为是有向无环图，那么我们考虑所有节点排成一条链，然后像找任意两点间的连线那样考虑，如下图所示：
在这里插入图片描述
很容易发现以下规律，设 $x$ 为图的点数， $y$ 为路径数：

当 $x = 2$ 时， $y = 1$
当 $x = 3$ 时， $y = 2$
当 $x = 4$ 时， $y = 4$
当 $x = 5$ 时， $y = 8$
…

那么得到，当图有 $x$ 个节点时，路径数为 $2^{x-2}$ 条

如果先拿出 $x$ 个节点，先连成一条链，然后将除一号节点外的所有节点向后面的 $x - i - 1$ 个节点连接，那么路径数为 $2^{x-3}$ 条，然后我们将一号节点依次连向第 $x, x - 1, x - 2, . . ., 3$ 个节点时，增加的路径数分别为 $1, 1, 2, 4, 8, . . .$ ，很容易联想到二进制拆分。

假设需要 $k$ 条路径，先找到大于等于 $k$ 的第一个 $2$ 的次幂 $x$ ，那么显然顶点总数为 $m = x + 2$ ，然后按上述第一个步骤连接。接下来看看余数是否为0，如果为0那么恰好需要一号顶点向 $3, 4, 5 . . ., m$ 相连，否则我们对余数 $r e s$ 二进制拆分，实际上就是看某一位是否为 $1$ ，然后从第 $m - 1$ 个节点开始作为最低位，如果该数二进制位为 $1$ 依次加边，最后输出即可

注意最大可能找到 $1 < < 64$ 恰好爆 $u n s i g n e d l o n g l o n g$ ，那么使用 $_\_int128$

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

vector<pii> ans;

void write(__int128 x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ull k,n;
    cin>>k>>n;
    if(k==1){
        cout<<"2 1\n1 2\n";
        return 0;
    }
    if(k==2){
        cout<<"3 3\n1 2\n2 3\n1 3\n";
        return 0;
    }
    __int128 one=1;
    ull x=0,m;
    while((one<<x)<k) x++;
    //cout<<"x:"; write(x); cout<<endl;
    
    m=x+2;
    ans.push_back({1,2});
    ans.push_back({m-1,m});
    for(int i=2;i<=m-2;i++){
        for(int j=i+1;j<=m;j++)
            ans.push_back({i,j});
    }
    
    ull res,p;
    if((one<<x)==k) res=0;
    else res=(ull)((__int128)k-(one<<(x-1)));
    //cout<<"res:"<<res<<endl;
    
    vector<int> tmp;
    p=res;
    while(res){
        if(res&1) tmp.push_back(1);
        else tmp.push_back(0);
        res>>=1;
    }
    
    //cout<<"binary:"; for(auto i: tmp) cout<<i; cout<<endl;
    if(p){
        for(int i=0,j=m-1;i<tmp.size();i++,j--) if(tmp[i]){
            ans.push_back({1,j});
        }  
    }else{
        for(int i=3;i<=m;i++) ans.push_back({1,i});
    }
   
    cout<<m<<" "<<ans.size()<<"\n";
    for(int i=0;i<ans.size();i++) cout<<ans[i].first<<" "<<ans[i].second<<"\n";
    return 0;
}