P8984 [北大集训 2021] 末日魔法少女计划

, ,

Description

https://www.luogu.com.cn/problem/P8984

Solution

把 $A_{i,j}=1$ 的看成 $(i,j)$ 的有向边，一开始给你一个 $1\to 2\to \dots\to n$ 的链。$(A^k)_{i,j}$ 可以理解为 $\forall i<j,i\to j$ 的最短路 $\le k$。我们需要添加的边尽量小。

  • $k=1$，全部连起来。

  • $k=2$，考虑分治，$[l,mid)$ 向 $mid$ 连一条边，$mid$ 向 $(mid,r]$ 连一条边。能通过 $k=2$ 的点。

  • $k\ge 3$ 的情况，考虑分成 $B+2$ 块的数。有 $B+1$ 个中间点。第 $i$ 个中间点连接第 $i$ 个块和 $i+1$ 个块的每个点。然后对每个块和这 $B+1$ 个点可以归成子问题，递归下去。第 $1$ 个块和最后一个块只连一次边，中间的其他块要连两次。

考虑用 dp 来精细实现这个过程。根据对称性，让两侧大小相等，中间尽量平均，使得边数在不会太劣的情况下减少转移的难度。记 $f_{k,n}$ 表示当前 $n$ 个点加上至少 $f_{k,n}$ 使得最多经过 $k$ 条边所有点可以互相到达。

直接转移是 $O(n^3k)$ 的，考虑根据上面的情况，我们构造中间状态 $g_{k,n}$ 表示 $n$ 个点的中间块最多经过 $k$ 条边使得所有点可以互相到达。

有转移：
$$
f_{k,n}=\min{2\times (f_{k,i}+i-1)+g_{k,n-2i} }
$$

$$
g_{k,n}=\min{f_{k-2,j+1}+w1\times (f_{k,w}+2w-3)+w2\times (f_{k,w+1}+2w+2-3))}
$$

其中 $j$ 表示枚举的中间块的个数，$w=\dfrac{(i-j-1)}{j}$ 表示块的长度，$w1=j-(i-j-1)\bmod j$ 表示中间长度为 $w$ 的块的个数，$w2=j-w1$ 表示长度为 $w+1$ 的块的个数。转移体现了中间均分。

最后记录最优转移点，输出方案。复杂度 $O(n^2k)$。

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 2005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m;
int f[16][maxn],pf[16][maxn];
int g[16][maxn],pg[16][maxn];
int a[maxn][maxn];
int F1(int n,int k) {return f[k][n]+max(0,n-1);}
int F2(int n,int k) {return f[k][n]+max(0,2*n-1);}
void print(void) {
	int i,j,ans=0;
	for (i=1;i<=n;i++) for (j=i+2;j<=n;j++) ans+=a[i][j];
	printf("%d\n",ans);
	for (i=1;i<=n;i++) for (j=i+2;j<=n;j++) if (a[i][j]) printf("%d %d\n",i-1,j-1);
}
void dfs(vector<int> id,int k,int n) ;
void dfs(vector<int> id,int k,int n) {
	int i,j;
	if (n<=k+1) return ;
	if (k==1) {
		for (i=1;i<=n;i++) for (j=i+1;j<=n;j++) a[id[i]][id[j]]=1;
		return ;
	}
	vector<int>Ol,Or;
	if (k==2) {
		int mid=(n+1)/2;
		Ol.assign(mid,0);
		for (i=1;i<mid;i++) a[id[i]][id[mid]]=1,Ol[i]=id[i];
		Or.assign(n-mid+1,0);
		for (i=mid+1;i<=n;i++) a[id[mid]][id[i]]=1,Or[i-mid]=id[i];
		dfs(Ol,k,mid-1);
		dfs(Or,k,n-mid);
		return ;
	}
	int x=pf[k][n];
	Ol.assign(x+1,0);
	for (i=1;i<=x;i++) a[id[i]][id[x+1]]=1,Ol[i]=id[i];
	dfs(Ol,k,x);
	Or.assign(x+1,0);
	for (i=n;i>=n-x+1;i--) a[id[n-x]][id[i]]=1,Or[i-(n-x)]=id[i];
	dfs(Or,k,x);
	n-=2*x;
	int l=x+1,r=n,y;
	y=pg[k][n];
	if (!y) return ;
	int w=(n-y-1)/y,w2=(n-y-1)%y,w1=y-w2;
	vector<int>Q;Q.assign(y+2,0);
	int cnt=0;Q[++cnt]=id[l];
	vector<int>O;O.assign(w+1,0);
	for (j=1;j<=w1;j++) {
		for (i=l+1;i<=w+l;i++) a[id[l]][id[i]]=a[id[i]][id[w+l+1]]=1;a[id[l]][id[w+l+1]]=1;
		for (i=l+1;i<=w+l;i++) O[i-l]=id[i];
		dfs(O,k,w);
		l+=w+1;
		Q[++cnt]=id[l];
	} 
	w++;
	O.push_back(0);
	for (j=1;j<=w2;j++) {
		for (i=l+1;i<=w+l;i++) a[id[l]][id[i]]=a[id[i]][id[w+l+1]]=1;a[id[l]][id[w+l+1]]=1;
		for (i=l+1;i<=w+l;i++) O[i-l]=id[i];
		dfs(O,k,w);
		l+=w+1;
		Q[++cnt]=id[l];
	}
	dfs(Q,k-2,cnt);
}
signed main(void){
	int i,j,k;
	read(n);read(m);n++;
	for (i=2;i<=n;i++) f[1][i]=(i-1)*(i-2)/2;
	for (i=4;i<=n;i++) {
		int mid=(i+1)/2;
		f[2][i]=f[2][mid-1]+f[2][i-mid]+i-3;
	}
	for (k=3;k<=m;k++) {
		for (i=1;i<=n;i++) f[k][i]=g[k][i]=n*20;
		for (i=1;i<k;i++) f[k][i]=0,g[k][i]=0;
		for (i=k;i<=n;i++) {
			for (j=1;j*2<i;j++)	
				if (f[k][i]>2*F1(j,k)+g[k][i-2*j]) pf[k][i]=j,f[k][i]=2*F1(j,k)+g[k][i-2*j];
			for (j=1;j<i;j++) {
				int w=(i-j-1)/j,w2=(i-j-1)%j,w1=j-w2;
				int tmp=f[k-2][j+1]+w1*F2(w,k)+w2*F2(w+1,k);
				if (g[k][i]>tmp) g[k][i]=tmp,pg[k][i]=j;
			} 
		}
	} 
	for (i=1;i<=n;i++) a[i][i]=a[i][i+1]=1;
	vector<int>O;O.assign(n+1,0);
	for (i=1;i<=n;i++) O[i]=i;
	dfs(O,m,n);
	print();
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i