CF 976D Degree Set

传送门

题目大意

  给你一个长度为 n n $n$ 的正整数序列 d1,d2,⋯,dn$d_1,d_2,\cdots ,d_n$$d_1, d_2, \cdots, d_n$ （ d1<d2<⋯<dn d 1 < d 2 < ⋯ < d n $d_1 < d_2 < \cdots < d_n$ ）。要求你构造一个满足以下条件的无向图：

1. 有恰好 dn+1 d n + 1 $d_n + 1$ 个点；
2. 没有自环；
3. 没有重边；
4. 总边数不超过 106 10 6 $10^6$ ；
5. 它的度数集合等于 d d $d$ 。

  点从 1$1$$1$ 标号至 dn+1 d n + 1 $d_n + 1$ 。

  图的度数序列是一个长度与图的点数相同的数组 a a $a$ ，其中 ai$a_i$$a_i$ 是第 i i $i$ 个顶点的度数（与其相邻的顶点数）。

  图的度数集合是度数序列排序后去重的结果。

  保证有解，要求输出符合条件的图。

思路

  唉，我太弱了，这么傻逼的构造题，硬是做了两节课都没做出来，还是看了题解才做出来的，唉，太弱啦！

  显然至少有一个点是连接了其它所有点的，那至多有多少个点连接了其它所有点呢？显然是 d1$d_1$$d_1$ 个点。这样，就不存在度数为 d1 d 1 $d_1$ 和 dn d n $d_n$ 的点了，并且 d2∼n−1 d 2 ∼ n − 1 $d_{2 \sim n - 1}$ 的所有值都要减去 d1 d 1 $d_1$。我们强制让还有度数的点的数量为 dn−1+1 d n − 1 + 1 $d_{n - 1} + 1$，构造方法为：令度数为 d1 d 1 $d_1$ 的点的个数为 dn−dn−1 d n − d n − 1 $d_n - d_{n - 1}$（显然至少为 1 1 $1$），将度数为 dn$d_n$$d_n$ 的点连向其它所有点，那么点数将会减少 d1+(dn−dn−1) d 1 + ( d n − d n − 1 ) $d_1 + (d_n - d_{n - 1})$。这时，以前度数为 dn−1 d n − 1 $d_{n - 1}$ 的点度数变成了 dn−1−d1 d n − 1 − d 1 $d_{n - 1} - d_1$，因为有 dn−1−d1+1=dn+1−(d1+(dn−dn−1)) d n − 1 − d 1 + 1 = d n + 1 − ( d 1 + ( d n − d n − 1 ) ) $d_{n - 1} - d_1 + 1 = d_n + 1 - (d_1 + (d_n - d_{n - 1}))$，所以原问题变成了一个子问题，递归求解即可。

参考代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
}

const int maxn = 1005;
const int maxm = 305;
int n, m;
int a[maxn];

std::vector<std::pair<int, int> > G;

void run()
{
    m = readIn();
    for (int i = 1; i <= m; i++)
        a[i] = readIn();
    n = a[m] + 1;
    int l = 1;
    int start = 1;
    int accum = 0;
    int r = m;
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= a[i]; j++)
        {
            for (int k = start + 1; k <= accum + a[r] + 1; k++)
            {
                G.push_back(std::make_pair(start, k));
            }
            start++;
        }
        r--;

        accum += a[i];
        for (int j = i + 1; j <= m; j++)
            a[j] -= a[i];
    }

    printOut(G.size());
    for (int i = 0; i < G.size(); i++)
    {
        putchar('\n');
        printOut(G[i].first);
        putchar(' ');
        printOut(G[i].second);
    }
}

int main()
{
    run();
    return 0;
}

总结

  最关键的是如何想到度数为 d1 d 1 $d_1$ 的点数为多少。这里为了构造，很显然我们要往子问题那里去靠。如果满足子问题结构，设度数为 d1 d 1 $d_1$ 的点数为 k k $k$，那么有：

  显然有 k=dn−dn−1 k = d n − d n − 1 $k = d_n - d_{n - 1}$，相当于是我们先用度数为 dn+1 d n + 1 $d_{n + 1}$ 的把所有度数为 d1 d 1 $d_1$ 的消掉，并且把自己的度数变成 dn−1 d n − 1 $d_{n - 1}$。

  需要注意的是，我们是令点数为 dn−1+1 d n − 1 + 1 $d_{n - 1} + 1$，但是度数都减去了 d1 d 1 $d_1$，递归求解时 dn−1 d n − 1 $d_{n - 1}$ 发生了改变。