Codeforces Good Bye 2018中的E是一道阅读理解题,题面中的给出了到wiki的链接,但比赛时我怎么有心情读一大段英文wiki…
这道题的背景知识叫可简单图化问题(Graph Realization),指给定一个有限序列 $D=(d_1,d_2,\cdots,d_n)$ ,是否存在一个无自环的无向图G,使得G中顶点的度数构成的序列为$D$。

RMK (2019-06-24):原来这是离散数学的作业题…

Havel-Hakimi Algorithm

定理:令$D=(d_1,\cdots,d_n)$,其中$d_1\geq d_2 \geq\cdots\geq d_n$,$D$是可简单图化的当且仅当$D’=(d_2-1,d_3-1,\cdots,d_{d_1+1}-1,d_{d_1+2},\cdots,d_n)$非负且是可简单化的。

Proof

$\Leftarrow)$ 这个定理的充分性是显然的。
设$d_i$对应的节点是$v_i$,对n归纳,当我们得到了$D’$对应的图$G’$,将$v_1$与$G’$中的$v_2,\cdots,v_{d_1+1}$连边,就构造出了$G$

$\Rightarrow)$ 要证明这个条件的必要性,考虑若已有一个图$G$,能否构造出$G’$。
记$S=\{u|(u, v_1)\in G\},\ T=\{v_j|2\leq j\leq d_1+1\}$

  1. 如果$S=T$,那么删去$v_1$及$v_1$和$S$间的边,就得到了$G’$
  2. 否则,存在$v_p\in T,\ v_q\not\in T$,使得$v_p\not\in S,\ v_q\in S$
    因为$d_p\geq d_q$,所以又存在一个不同的点$z$,使得$v_p$和$z$相邻,$v_q$和$z$不相邻,那么我们删去$(v_p,z)$和$(v_1,v_q)$,添加$(v_1,v_p)$和$v_q,z$,这样保持$v_q$的度数不变,并把$v_p$加到$S$中。
    重复2的过程,因为$|S|=|T|=d_1$,总会使得$S=T$,这是我们就回到了情况1。

Implementation - poj 1659

这是一道水题,给定一个序列,问是否可以简单图化,如果能的话输出任一方案。
Havel算法的实现就是,迭代$d_i$,$d_{i+1},…,d_{i+d_1}$都减去1,如果过程中出现负数就无解,最后$d_n=0$就有解,否则无解。复杂度$O(N^2logN)$,方案按照充分性的证明构造即可。

poj1659.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define foreach(i, x) for(auto i = x.begin(); i != x.end(); i++)
#define forg(i) for(int i = head[u]; i; i = g[i].nxt)
#define INF (ll)0x3f3f3f3f
#define EPS 1e-8
#define X first
#define Y second
#define mkp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define lbound lower_bound
#define ubound upper_bound
#define rnd(x) (rand()%(x)+1)
#define squ(x) ((x)*(x))
#define disp0(A){foreach(i,A)cout<<A[i]<<" ";cout<endl;}
#define disp(A, l, r) {rep(_i,l,r)cout<<A[_i]<<" ";cout<<endl;}
#define disp2(A, l, r, b, e){ \
rep(_i,l,r){rep(_j,b,e)cout<<A[_i][_j]<<"\t";cout<<endl;} \
cout<<endl; \
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, int> Pli;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
template<class T> inline T lowbit(T x) {return x&(-x);}
template<class T> T gcd(T a, T b) {return b?gcd(b,a%b):a;}
template<class T> inline T Pow(T a, T b, T p)
{T ret=1;for(;b;b>>=1,a=a*a%p)if(b&1)(ret*=a)%=p;return ret;}
template<class T> inline void read(T &ret)
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
ret = x*f;
}

const int N = 15;
int n, g[N][N]; P a[N];
int main()
{
freopen("std.in", "r", stdin);
//freopen("std.out", "w", stdout);
int T; read(T);
while(T--)
{
read(n); rep(i, 1, n) read(a[i].X), a[i].Y = i;
rep(i, 1, n) rep(j, 1, n) g[i][j] = 0;
bool flg = 1;
rep(i, 1, n)
{
sort(a+i, a+n+1, greater<P>());
if(a[n].X<0 || i+a[i].X>n) { flg = 0; break; }
if(a[i].X == 0) continue;
rep(j, i+1, i+a[i].X)
{
g[a[i].Y][a[j].Y] = g[a[j].Y][a[i].Y] = 1;
a[j].X--;
}
}

if(flg)
{
printf("YES\n");
rep(i, 1, n)
{
rep(j, 1, n) printf("%d ", g[i][j]);
printf("\n");
}
}
else printf("NO\n");
printf("\n");
}
}

Erdős–Gallai theorem

另一个定理给出了可简单图化的不等式条件,给定序列$D=(d_1,d_2,\cdots,d_n)$,其中$d_1\geq d_2 \geq\cdots\geq d_n$,$D$可简单图化当且仅当
$$\sum_{i=1}^{k}d_i\leq k(k-1)+\sum_{i=k+1}^n min(d_i,k)$$
对任意$1\leq k\leq n$成立

Explanation

这个定理的必要性是显然的,式子左边是$S=\{d_1,d_2,...,d_k\}$的度数和,右边第一项是$S$中连边的最大贡献,第二项是$S$与$G\setminus S$间连边的最大贡献。

充分性的证明有很多种,也要复杂的多,其中一种构造的证法见:A short constructive proof of the Erdős–Gallai characterization of graphic lists

Implementation - cf 1091E

这就是楔子中提到的阅读理解题,题意为:
给定$(d_1,d_2,d_3,…,d_n)$,求所有可能的$d_{n+1}$,使得$(d_1,d_2,\cdots,d_{n+1})$可简单图化。
$1\leq n\leq 500000$

My solution

RMK:下面的$n$均$+1$,就是说给定$d_1,d_2,\cdots,d_{n-1}$,要确定的是$d_n$

首先由握手定理可以确定$d_n$的奇偶性。
考虑Erdős–Gallai定理,先将序列降序排列,对于给定$d_n$,记$d_j\leq d_n\leq d_{j+1}$

  1. 当$k\geq j+1$时,$d_n$在式子的左边,分离变量得式$(1)$
    $$d_n\leq k(k-1)+\sum_{i=k}^{n-1} min(d_i,k)-\sum_{i=1}^{k-1}d_i$$
  2. 当$1\leq k \leq j$时,$d_n$在式子的右边,变形后
    $$0\leq k(k-1)+\sum_{i=k+1}^{n-1} min(d_i,k)-\sum_{i=1}^{k}d_i+min(d_n,k)$$
    • 当$k\leq d_n$时,变成式$(2)$
      $$0\leq k(k-1)+\sum_{i=k+1}^{n-1} min(d_i,k)-\sum_{i=1}^{k}d_i+k$$
    • 当$k>d_n$时,分离变量得到式$(3)$
      $$-d_n\leq k(k-1)+\sum_{i=k+1}^{n-1} min(d_i,k)-\sum_{i=1}^{k}d_i$$

注意到不等式$(1)(2)(3)$右边的部分都只与$k$有关,可以通过二分+前后缀和预处理出来,并建st表。然后枚举$d_n$,分$[1,min(d_n,j)],\ [max(1,d_n),j],\ [j+1,n]$三个区间判断$(2)(3)(1)$即可。

注意st表空间可能比较吃紧,还有$d_n=0$最好特判一下。

E.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define foreach(i, x) for(auto i = x.begin(); i != x.end(); i++)
#define forg(i) for(int i = head[u]; i; i = g[i].nxt)
#define INF (ll)0x3f3f3f3f
#define EPS 1e-8
#define X first
#define Y second
#define mkp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define lbound lower_bound
#define ubound upper_bound
#define rnd(x) (rand()%(x)+1)
#define squ(x) ((x)*(x))
#define disp0(A){foreach(i,A)cout<<A[i]<<" ";cout<endl;}
#define disp(A, l, r) {rep(_i,l,r)cout<<A[_i]<<" ";cout<<endl;}
#define disp2(A, l, r, b, e){ \
rep(_i,l,r){rep(_j,b,e)cout<<A[_i][_j]<<"\t";cout<<endl;} \
cout<<endl; \
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, int> Pli;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
template<class T> inline T lowbit(T x) {return x&(-x);}
template<class T> T gcd(T a, T b) {return b?gcd(b,a%b):a;}
template<class T> inline T Pow(T a, T b, T p)
{T ret=1;for(;b;b>>=1,a=a*a%p)if(b&1)(ret*=a)%=p;return ret;}
template<class T> inline void read(T &ret)
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
ret = x*f;
}

const int N = 5e5+10;
ll n, pref[N], suff[N]; int d[N];
void init(ll st[][20])
{
int lgn = ceil(log2(n));
rep(j, 1, lgn) rep(i, 1, n)
{
st[i][j] = st[i][j-1]; int k = i+(1<<(j-1));
if(k <= n) st[i][j] = min(st[i][j], st[k][j-1]);
}
}
ll query(ll st[][20], int l, int r)
{
if(l > r) return INF;
int len = r-l+1, t = log2(len);
return min(st[l][t], st[r-(1<<t)+1][t]);
}

ll st[3][N][20]; int ans[N], cnt = 0;
int main()
{
// freopen("std.in", "r", stdin);
// freopen("std.out", "w", stdout);
read(n); n++;
rep(i, 1, n-1) read(d[i]);
sort(d+1, d+n, greater<int>());
pref[0] = suff[n] = 0;
rep(i, 1, n-1) pref[i] = pref[i-1] + (ll)d[i];
per(k, n-1, 1) suff[k] = suff[k+1] + (ll)d[k];
for(ll k = 1; k <= n; k++)
{
ll j = lbound(d+1, d+n, k, greater<int>()) - d;
ll s1 = (max(j, k+1)-(k+1))*k + suff[max(j, k+1)];
ll s2 = (max(j, k)-k)*k + suff[max(j, k)];
st[0][k][0] = k*(k-1) + s1 - pref[k] + k;
st[1][k][0] = k*(k-1) + s1 - pref[k];
st[2][k][0] = k*(k-1) + s2 - pref[k-1];
}

rep(i, 0, 2) init(st[i]);
int j = 0;
per(dn, n-1, 1)
{
while(j < n-1 && d[j+1] >= dn) j++;
if((dn+pref[n-1])%2) continue;
if(query(st[0], 1, min(dn, j)) < 0) continue;
if(query(st[1], max(1, dn), j) < -dn) continue;
if(query(st[2], j+1, n) < dn) continue;

// cout << dn << " j=" << j << endl;
// printf("[%d, %d] %d\n", 1, min(dn, j), query(st[0], 1, min(dn, j)));
// printf("[%d, %d] %d\n", max(1, dn), j, query(st[1], dn, j));
// printf("[%d, %d] %d\n", j+1, n, query(st[2], j+1, n));
ans[++cnt] = dn;
}
if(query(st[1], 1, n-1) >= 0) ans[++cnt] = 0;
if(!cnt) printf("-1"); else per(i, cnt, 1)printf("%d ", ans[i]);
}

Standard solution

这种几个大式子的case work实现起来是很繁琐的,debug也无比困难。于是通过手玩样例,参考题解,严格论证我们发现,可行的$d_n$一定是连续的一段区间(当然还要奇偶性相同)
这样我们就可以二分了,$O(N)$内判断Erdős–Gallai不等式要容易很多。怎么二分一个区间?只要先在$[1,n]$内找出左端点$l$,再在$[l,n]$内二分右端点即可。
其他细节见Editorial,这里贴一下std

std.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define MAXN 500000

int N;
int A[MAXN];
long long sum;

#define TOO_SMALL -1
#define OK 0
#define TOO_BIG 1

int is_score(int value) {
vector<int> C(N+1,0);
for (int i = 0; i < N; ++i) ++C[A[i]];
++C[value];

int less = 0;
long long left = 0, right = 0;
for (int k = 0, i = 0; k <= N; k++) {
int val = (i == k && (i == N || A[i] < value)) ? value : A[i++];
left += val;
--C[val];
right -= min(val, k);
less += C[k];
right += N-k-less;
if (left > right + (long long)(k+1)*k) {
return (i == k) ? TOO_BIG : TOO_SMALL;
}
}
return OK;
}

int main(int,char**) {
ios_base::sync_with_stdio(false);

scanf("%d", &N);
sum = 0;
for (int i = 0; i < N; i++) {
scanf("%d", A + i);
sum += A[i];
}

sort(A,A+N,greater<int>());
int parity = sum & 1;
int lo = 0, hi = (N - parity) / 2, lores = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (is_score(2*mid + parity) == TOO_SMALL) {
lo = mid + 1;
} else {
lores = mid;
hi = mid - 1;
}
}

lo = lores;
hi = (N - parity) / 2;
int hires = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (is_score(2*mid + parity) == TOO_BIG) {
hi = mid - 1;
} else {
hires = mid;
lo = mid + 1;
}
}

if (lores == -1 || hires == -1) printf("-1\n");
else {
for (int i = lores; i <= hires; ++i) printf("%d ", 2*i+parity);
printf("\n");
}
}