Codeforces 388 B Fox and Minimal path

难得写的构造题，比赛的时候没写出来，听薛昊说的时候就理解了。
这种构图方法还是欠缺……

题意：
起点 1，终点 2，构造一个图，使得最短路数量为 k 。

思路：
这种题一般都是二进制分解做，关键就是构造出二进制的图，然后控制路径长度相同即可。这里提供一种构造方法。

点数最多 1e9 每行30个节点足够

AC Code

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

//#define DEBUG

using namespace std;

const int maxn = 110;
const int inf = 0x3f3f3f3f;
int k;
char mat[maxn][maxn];

int main()
{
    for (int i = 1; i <= 100; i++)
        for (int j = 1; j <= 100; j++)
            mat[i][j] = 'N';
    mat[2][11] = mat[11][2] = mat[1][41] = mat[41][1] = mat[1][71] = mat[71][1] = 'Y';
    for (int i = 11; i < 40; i++)
        mat[i][i + 1] = mat[i + 1][i] = 'Y';
    for (int i = 41; i < 70; i++) {
        mat[i][i + 1] = mat[i + 1][i] = 'Y';
        mat[i][i + 30 + 1] = mat[i + 30 + 1][i] = 'Y';
    }
    for (int i = 71; i < 100; i++) {
        mat[i][i + 1] = mat[i + 1][i] = 'Y';
        mat[i][i - 30 + 1] = mat[i - 30 + 1][i] = 'Y';
    }
    scanf("%d", &k);
    int len = log2(k) + 1;
    for (int i = 1; i <= len; i++) {
        if (k % 2)
            mat[40 + i][11 + len - i] = mat[11 + len - i][40 + i] = 'Y';
        k /= 2;
    }
#ifndef DEBUG
    puts("100");
    for (int i = 1; i <= 100; i++) {
        for (int j = 1; j <= 100; j++)
            putchar(mat[i][j]);
        puts("");
    }
#else
    int dis[maxn][maxn], ans = 0;
    for (int i = 1; i <= 100; i++)
        for (int j = 1; j <= 100; j++)
            dis[i][j] = mat[i][j] == 'Y' ? 1 : inf;
    for (int k = 1; k <= 100; k++) {
        for (int i = 1; i <= 100; i++)
            for (int j = 1; j <= 100; j++) {
                dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
            }
    }
    for (int k = 3; k <= 100; k++) {
        if (dis[1][k] + dis[k][2] == len + 2) {
            ans++;
            printf("k--> %d dis[1][k] --> %d dis[k][2] --> %d\n", k, dis[1][k], dis[k][2]);
        }
    }
    //printf("min   ----> %d  ans --->   %d\n", p, ans);
    printf("min --> %d  ans ----> %d \n", dis[1][2], ans);
#endif
    return 0;
}