题解：P13196 [GCJ 2016 #1C] Slides!

· · 题解

随机跳题出来一道构造，那就写篇题解吧。

思路

显然，我们构造的图不存在环，因为有环就是无限种。\ 对于一张有向无环图，其路径数是有限的：

f_k = \sum_{i = 1}^{k - 1} f_i = 2^{k-2}

接下来，我们对前 B - 1 个点构造一张完全 DAG。\ 然后将 M 按二进制展开，每一位对应一个中间节点是否连接到 B。

时间复杂度：O(T \cdot B^2)。

:::success[代码]

#include<bits/stdc++.h>
using namespace std;
long long t,b,m;
string ans[55];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    for(int num=1;num<=t;num++){
        cin >> b >> m;
        long long maxx=(b>=2)?(1LL<<(b-2)):1;
        cout << "Case #" << num << ": ";
        if(m>maxx){//不存在 
            cout << "IMPOSSIBLE" << '\n';
            continue;
        }
        cout << "POSSIBLE" << '\n';
        for(int i=0;i<b;i++) ans[i]="";
        for(int i=0;i<b;i++) for(int j=0;j<b;j++) ans[i]+='0';
        for(int i=0;i<b-1;i++){
            for(int j=i+1;j<b-1;j++) ans[i][j]='1';//构造前 B - 1 个点完全 DAG 
        }
        if(m==maxx){
            for(int i=0;i<b-1;i++){
                ans[i][b-1]='1';
            }
        }else{
            for(int i=1;i<b-1;i++){
                if(m&(1LL<<(i-1))){//二进制展开 
                    ans[i][b-1]='1';
                }
            }
        }
        for(int i=0;i<b;i++) cout << ans[i] << '\n';
    }
    return 0;
}

:::