5.4 做题

T1 NEERC2016 Cactus Construction

考虑一棵树怎么做。容易想到,我们保证递归完一棵子树得时候根为 $2$ ,其他内容为 $3$ ,然后当前点 $u$ 设 $1$ ,于是每次就连 $1 \to 2$ 然后把 $2$ 整成 $3$ ,再做下一棵子树即可。这样只需要三种颜色。

考虑仙人掌咋办。还是类似地,我们尝试做完一个环的时候把最上面设置成 $2$ ,这里为了方便,可以类似圆方树把一条边也看成长度为 $2$ 的环。然后考虑类似建立圆方树的过程。如果一个儿子 $v$ 自己为一个环顶(也就是 low[v] == dfn[u]) ,我们来处理这个环。按照弹栈顺序(也就是从深到浅)来做。我们把起始点设置为最深的,为了方便最后连完环上最后一条边把它设置成 $4$ ,然后考虑下一个点,类似树,钦定做完这个子树的时候它的颜色是 $2$ ,子树其他点是 $3$ ,然后把 $2,4$ 连起来,然后把 $2$ 设成 $1$ ,再考虑下一个点的时候就 $2,1$ 连边,然后把 $1$ 变成 $3$ ,把 $2$ 变成 $1$ ,一直这么做即可。最后把 $4,2$ 连起来即可。

可能需要判长度为 $2$ 的环,我的代码多进行了几次无用操作就不需要了,但是操作数略高。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
int A[MAXN];

vi G[MAXN];
vi pr[MAXN];

struct tcurts {
int o , a , c1 , c2;
tcurts( int o , int a , int c1 , int c2 ) : o(o) , a(a) , c1(c1) , c2(c2) {}
};
vector<tcurts> ops;
void J( int a , int b ) {
ops.eb( 0 , a , b , 0 );
}
void R( int a , int c1 , int c2 ) {
ops.eb( 1 , a , c1 , c2 );
}
void C( int a , int c1 , int c2 ) {
ops.eb( 2 , a , c1 , c2 );
}

int dfn[MAXN] , low[MAXN] , clo , dep[MAXN] , idx[MAXN] , stk[MAXN] , top;
void tarjan( int u , int f ) {
dfn[u] = low[u] = ++ clo;
stk[++ top] = u;
R( u , 1 , 2 );
for( int v : G[u] ) {
if( !dfn[v] ) {
tarjan( v , u );
low[u] = min( low[u] , low[v] );
if( low[v] == dfn[u] ) {
int s = stk[top];
R( s , 2 , 4 ) , -- top;
int la = 4 , lu = s;
if( s != v ) {
int k;
do {
k = stk[top --];
J( lu , k );
C( lu , la , 2 );
R( lu , 1 , 3 );
R( lu , 2 , 1 );
la = 1 , lu = k;
} while( k != v );
}
J( u , v );
C( u , 2 , 1 ) , C( u , 2 , 4 );
R( u , 4 , 3 ) , R( u , 1 , 3 );
}
} else low[u] = min( low[u] , dfn[v] );
}
}

void solve() {
cin >> n >> m;
rep( i , 1 , m ) {
int k , u , v;
scanf("%d",&k);
scanf("%d",&u);
rep( i , 2 , k ) scanf("%d",&v) , G[u].pb( v ) , G[v].pb( u ) , u = v;
}
tarjan( 1 , 1 );
cout << ops.size() << endl;
for( auto t : ops ) {
if( t.o == 0 ) {
printf("j %d %d\n",t.a,t.c1);
} else if( t.o == 1 ) {
printf("r %d %d %d\n",t.a,t.c1,t.c2);
} else if( t.o == 2 ) {
printf("c %d %d %d\n",t.a,t.c1,t.c2);
}
}
}

signed main() {
// freopen("cactus.in","r",stdin) , freopen("cactus.out","w",stdout);
// int T;cin >> T;while( T-- ) solve();
solve();
}

HDU5121 Just A Mistake

考虑一个 $dp$ ,设 $dp[u][i]$ 表示 $u$ 子树已经把顺序决定好,钦定 $u$ 最后被加进了独立集,$u$ 为排列中第 $i$ 个位置的方案数。

由于钦定了这个点必须被加入独立集,于是我们考虑对每个点为根进行一次 $dp$ ,最后把所有 $dp$ 加起来就是答案。

转移就是枚举 $v$ 的位置以及 $u$ 的位置,但是发现直接转移还需要枚举一下 $v$ 前面有多少个数在合并后在 $u$ 前面,系数是两个组合数的积。然后需要保证 $u$ 最后在独立集里面,因此必须保证要么 $v$ 没被加进去,要么 $u$ 在 $v$ 前面,这两个条件算起来比较阴间,可以用总方案数量减去 $v$ 在 $u$ 前面的方案数量,即 $v$ 前面合并后在 $u$ 前面的数量必须大于等于 $v$ 的位置。

然后会发现系数只和最后枚举的东西以及 $u$ 的位置有关,于是我们只枚举 $u$ 的位置以及由多少个 $v$ 序列的数被整到了 $u$ 的前面,最后那个系数和 $dp$ 的乘积可以前缀和预处理。

写得比较意识流,建议自己推一下 /kel

最终复杂度 $O(n^3)$ 。代码感觉很阴间,容易写挂。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 236
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
const int P = 1e9 + 7;
typedef long long ll;
int n;
int A[MAXN];

vi G[MAXN];
int wy[MAXN][MAXN] , C[MAXN][MAXN] , J[MAXN];
int tw[MAXN] , siz[MAXN];
void dfs( int u , int f ) {
siz[u] = 1;
wy[u][1] = 1;
for( int v : G[u] ) if( v != f ) {
dfs( v , u );
int sz = siz[u] + siz[v];
rep( i , 1 , siz[u] ) tw[i] = wy[u][i] , wy[u][i] = 0;
rep( i , 1 , siz[u] ) {
int ts = J[siz[v]];
rep( j , 0 , siz[v] ) {
ts = ( ts + P - wy[v][j] ) % P;
wy[u][i + j] = ( wy[u][i + j] + ts * 1ll * C[i - 1 + j][j] % P * C[sz - i - j][siz[v] - j] % P * tw[i] ) % P;
}
}
siz[u] = sz;
}
}

int kase = 0;

void solve() {
cin >> n;
rep( i , 1 , n ) G[i].clear();
rep( i , 2 , n ) {
int u , v;
scanf("%d%d",&u,&v);
G[u].pb( v ) , G[v].pb( u );
}
int res = 0;
rep( i , 1 , n ) {
rep( j , 1 , n ) rep( k , 1 , n ) wy[j][k] = 0;
dfs( i , i );
rep( k , 1 , n ) res = ( res + wy[i][k] ) % P;
// cout << wy[2][1] << endl;
}
++ kase;
printf("Case #%d: %d\n",kase,res);
}

signed main() {
rep( i , 0 , MAXN - 1 ) {
C[i][0] = 1;
if( i ) J[i] = J[i - 1] * 1ll * i % P;
else J[i] = 1;
rep( j , 1 , i ) C[i][j] = ( C[i - 1][j] + C[i - 1][j - 1] ) % P;
}
int T;cin >> T;while( T-- ) solve();
// solve();
}

AUOJ473 简单题

开始以为边分树合并有救,后来发现这题合并的东西或者查询的东西放到边分树就很没救。

对两个图建出 Kruskal 重构树,然后问题变成了求所有点对在两棵树 LCA 权值积的和。

我们可以考虑对第一棵树做一次差分,$c’_u = c_u - c_f$ ,然后对这个树进行树剖。然后在第二棵树上进行 dfs ,再进行线段树合并 + 启发式合并即可。具体来说,我们把每个叶子开个主席树,包括的只有这个叶子加入后一些链会被权值 $+1$ (实际上一棵树的值为所有位置的权值乘上 $c_u$ )。然后每次合并的时候枚举较小的一侧,分别进行链查询即可。

复杂度 $O(n\log^3n)$ 。

本来想写边分合并,写完发现好像不是很能合并,于是无限期咕咕咕了。。

文章作者: yijan
文章链接: https://yijan.co/54-zuo-ti/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog