7.26

A

并查集维护,时间复杂度我写的貌似不大对,先鸽一鸽

B

敦爷:\(w\)是这个区间的最大值当且仅当他是这个区间内最大的

我们发现结合昨天课件内的并查集

发现我们每次不断合并的本质是把所有\(<=w\)的边连上

我们将这条边连接的两个连通块连到一起时,连个联通块的大小就是贡献

我们把边权按照大小排序

一条条的加进去

那么总的贡献就是\(w*size(a) *size(b)\)

当然,这只是一次合并的总的贡献

这时候我们发现单个元素的贡献是可以顺便维护的

即使对于\(a\)中联通块的元素

每个贡献都有\(w*size(b)\)

\(b\)同理

这只是一条链的情况

我们考虑树上该怎么做

点权转成边权

同理每次考虑合并每个链连通的两个联通块

我们要按秩合并,不要路径压缩

每个并查集的根节点都要维护两个东西

首先是当前子树的\(tag\)

因为上面说的这个连通块内的每个元素都是有贡献的

我们在根节点上打上\(tag\)后面下放一遍记好了

我们想一下

\(a\),\(b\)两个联通块合并我们假设\(a\)的\(size\)比较小一些

那个应该是

\(tag_a += w*size_b\)

\(tag_b+=w*size_a\)

但是我们发现,我们把\(a\)并到\(b\)上之后

原本在\(b\)上的\(tag\)对\(a\)是没有效果的,我们下放的时候却会计算到里面

所以我们要让这一部分的贡献减去

\(tag_a -=tag_b\)

#include<cstdio>

#include<iostream>

#include<queue>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<vector>

#define LL long long

using namespace std;

const int N = 4e5 + 311;

int n,m,tot;

LL ans[N];

int fa[N],size[N];

LL w[N];

vector <int> G[N];

struct edge{

	int from;

	int to;

	LL data;

}e[N << 1];

inline int getf(int x){

	return x == fa[x] ? x : getf(fa[x]);

}

inline bool cmp(edge x,edge y){

	return x.data < y.data;

}

inline int read(){

	int v = 0,c = 1;char ch = getchar();

	while(!isdigit(ch)){

		if(ch == '-') c = -1;

		ch = getchar();

	}

	while(isdigit(ch)){

		v = v * 10 + ch - 48;

		ch = getchar();

	}

	return v * c;

}

inline void dfs(int x,int f){

	ans[x] += ans[f];

	for(int i = 0;i < (int)G[x].size();++i){

		int y = G[x][i];

		if(y == f) continue;

		dfs(y,x);

	}

}

int main(){

	n = read();

	for(int i = 2;i <= n;++i){

		int x = read();

		e[++tot] = (edge){i,x,0};

	}

	for(int i = 1;i <= n;++i) w[i] = read();

	for(int i = 1;i <= n + 13;++i) fa[i] = i,size[i] = 1;

	for(int i = 1;i <= tot;++i) e[i].data = max(w[e[i].from],w[e[i].to]);

//	for(int i = 1;i <= tot;++i){

//		printf("%d %d %lld\n",e[i].from,e[i].to,e[i].data);

//	}

	sort(e + 1,e + tot + 1,cmp);

	for(int i = 1;i <= tot;++i){

		int x = getf(e[i].from),y = getf(e[i].to);

		if(size[x] > size[y]) swap(x,y);

		if(x == y) continue;

	//	printf("%d %d %lld %lld\n",x,y,ans[x],ans[y]);

		G[y].push_back(x);

		ans[y] += e[i].data * size[x];

		ans[x] += e[i].data * size[y];

		ans[x] -= ans[y];

		size[y] += size[x];

		fa[x] = y;

	}

	dfs(getf(1),0);

	for(int i = 1;i <= n;++i) printf("%lld ",ans[i] + w[i]);

	return 0;

}

C

问你删除循序的题目

一定要先考虑那个数最后被删掉

我们枚举那个数最后被删掉

如果一个数最后被删掉

那么这个数两边的数永远也不会相邻

我们发现如果我们已经处理出来了

左边的方案数\(A\),右边的方案数\(B\)

那么答案就是\(C_{A + B}^A\)

我们考虑暴力DP

我们设\(f_{l,r,lx,rx}\)表示区间\([l,r]\),且满足左端点不等于\(l_x\),右端点不等于\(r_x\)时的答案

转移我们就枚举区间分裂位置\(k\)

\(f_{l,r,lx,rx} = \sum _{i = l}^rC_{r - l}^{k - l}*f_{l,k - 1,lx,a_{k}} * f_{k + 1,r,a_k,r_x}\)

注意要乘一下组合数

因为这里对与两种不同的合法方案

将他们合并顺序不同可能会影响答案

而合并的总的可能循序就是一共\(r - l\)个位置,有\(k - l\)个位置在操作左边

这样就得到了一个\(n^5\)的做法

之后我们发现这个做法有点蠢

因为对于一个确定\([l,r ]\),\(lx,rx\)一定是确定的

因为你想一下我们DP过程,是钦定一个位置最后选

那么这时候就被卡住了

分裂后的区间的限制

也就是说\([l,r]\)的限制一定是我们强制了\(a_{l -1}\)和\(a_{r + 1}\)得到的

之后发现\(r_x\)和\(l_x\)这一维是固定的,不需要枚举

那么,DP方程就可以简化为

\(f_{l,r} = \sum_{k = l}^rC_{r -l}^{k - 1}*f_{l,k - 1}*_{k + 1,r}\)

\(k\)就是我们要枚举的子区间最后一个删除的位置

很明显转移要有\(a_{k}!=a_{l - 1}\)和\(a_{k}!= a_{r + 1}\)

另外,为了防止\(f_{l,k - 1}\)中\(l > k - 1\)的情况导致漏掉答案

初始化时\(f_{i + 1,i} = 1\)

也是必要的

#include<iostream>

#include<cctype>

#include<queue>

#include<algorithm>

#include<cstring>

#include<vector>

#include<cstdio>

#include<stack>

#define LL long long

const int N = 505;

const LL mod = 998244353;

using namespace std;

LL f[N][N];

LL fac[N],inv[N];

int n;

int a[N];

inline int read(){

	int v = 0,c = 1;char ch = getchar();

	while(!isdigit(ch)){

		if(ch == '-') c = -1;

		ch = getchar();

	}

	while(isdigit(ch)){

		v = v * 10 + ch - 48;

		ch = getchar();

	}

	return v * c;

}

inline LL quick(LL a,LL b){

	LL res = 1;

	while(b){

		if(b & 1) res = res * a % mod;

		b >>= 1;

		a = a * a % mod;

	}

	return res;

}

inline LL C(int x,int y){

	return fac[x] * inv[y] % mod * inv[x - y] % mod;

}

inline LL mo(LL x){

	if(x >= mod) x -= mod;

	return x;

}

int main(){

	scanf("%d",&n);

	fac[0] = inv[0] = fac[1] = inv[1] = 1;

	for(int i = 2;i <= n;++i){

		fac[i] = fac[i - 1] * i % mod;

		inv[i] = quick(fac[i],mod - 2);

	}

	for(int i = 1;i <= n;++i) a[i] = read();

	for(int i = 1;i < n;++i)

	if(a[i] == a[i + 1]){

		printf("0\n");

		return 0;

	}

	for(int i = 1;i <= n;++i) f[i][i] = f[i][i - 1] = 1;

	f[n + 1][n] = 1;

	a[0] = a[n + 1] = -1;

	for(int len = 2;len <= n;++len){

		for(int l = 1;l + len - 1 <= n;++l){

			int r = l + len - 1;

			for(int k = l;k <= r;++k){

				if(a[k] != a[l - 1] && a[k] != a[r + 1])

				f[l][r] = mo(f[l][r] + C(r - l,k - l) * f[l][k - 1] % mod * f[k + 1][r]) % mod;

			}

		}

	}

	printf("%lld\n",f[1][n]);

	return 0;

}

巴特西

ZR7.26

7.26

A

B

C

最新文章

热门文章