5.4 做题

T1 NEERC2016 Cactus Construction

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

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

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

#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

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

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

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

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

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

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

#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 权值积的和。

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

复杂度 O(nlog3n)O(n\log^3n)

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

\