传送门题目大意思路参考代码总结
传送门
题目大意
给你一个长度为
n
n
的正整数序列 d1,d2,⋯,dnd1,d2,⋯,dn （
d1<d2<⋯<dn
d
1
<
d
2
<
⋯
<
d
n
）。要求你构造一个满足以下条件的无向图：
有恰好
dn+1
d
n
+
1
个点；没有自环；没有重边；总边数不超过
106
10
6
；它的度数集合等于
d
d
。
点从 11 标号至
dn+1
d
n
+
1
。
图的度数序列是一个长度与图的点数相同的数组
a
a
，其中 aiai 是第
i
i
个顶点的度数（与其相邻的顶点数）。
图的度数集合是度数序列排序后去重的结果。
保证有解，要求输出符合条件的图。
思路
唉，我太弱了，这么傻逼的构造题，硬是做了两节课都没做出来，还是看了题解才做出来的，唉，太弱啦！
显然至少有一个点是连接了其它所有点的，那至多有多少个点连接了其它所有点呢？显然是 d1d1 个点。这样，就不存在度数为
d1
d
1
和
dn
d
n
的点了，并且
d2∼n−1
d
2
∼
n
−
1
的所有值都要减去
d1
d
1
。我们强制让还有度数的点的数量为
dn−1+1
d
n
−
1
+
1
，构造方法为：令度数为
d1
d
1
的点的个数为
dn−dn−1
d
n
−
d
n
−
1
（显然至少为
1
1
），将度数为 dndn 的点连向其它所有点，那么点数将会减少
d1+(dn−dn−1)
d
1
+
(
d
n
−
d
n
−
1
)
。这时，以前度数为
dn−1
d
n
−
1
的点度数变成了
dn−1−d1
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
)
)
，所以原问题变成了一个子问题，递归求解即可。
参考代码
#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
的点数为多少。这里为了构造，很显然我们要往子问题那里去靠。如果满足子问题结构，设度数为
d1
d
1
的点数为
k
k
，那么有：
dn−1−d1 1=dn−d1 1−kdn−1−d1 1=dn−d1 1−k
显然有
k=dn−dn−1
k
=
d
n
−
d
n
−
1
，相当于是我们先用度数为
dn+1
d
n
+
1
的把所有度数为
d1
d
1
的消掉，并且把自己的度数变成
dn−1
d
n
−
1
。
需要注意的是，我们是令点数为
dn−1+1
d
n
−
1
+
1
，但是度数都减去了
d1
d
1
，递归求解时
dn−1
d
n
−
1
发生了改变。
