夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

ZR省选十连测Day3

2021-01-17 20 min read # ODT # 树哈希 # 树形DP # 费用流 # 比赛题 # 概率 # 期望

A

做法1:

ODT

我的实现在两次都推平,就能压下去常数啦

注意珂朵莉树先分裂右端点再分裂左端点

//珂朵莉树
//我永远喜欢珂朵莉
#include<bits/stdc++.h>
#define ins insert
#define ll long long
using namespace std;
const int MAXN = 1e6 + 7;
int n, m, q, a[MAXN];
//区间加和单点查询
//树状数组差分
struct bit {
#define lowbit(x) (x&(-x)) 	
	ll tr[MAXN];
	inline void add(int x, ll v) {
		for(; x <= n; x += lowbit(x))tr[x] += v;
	}
	inline void mdf(int l, int r, ll v) {
		add(l, v);
		add(r + 1, -v);
	}
	inline ll qry(int x) {
		ll ret = 0;
		for(; x; x -= lowbit(x))ret += tr[x];
		return ret;
	}
} tr;

namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE], *p1 = buf, *pend = buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
	int _C = -1, _Z;
	char _sr[1 << 21], _z[20];
	inline void Ot() {
		fwrite(_sr, 1, _C + 1, stdout), _C = -1;
	}
	inline void print(ll x, char s) {
		if(_C > BUF_SIZE)Ot();
		while(_z[++_Z] = x % 10 + 48, x /= 10);
		while(_sr[++_C] = _z[_Z], --_Z);
		_sr[++_C] = s;
	}
}
using namespace fastIO;

struct NODE {
	int l, r;
	mutable int v;//指向哪个逼
	NODE(int L = 0, int R = 0, int V = 0): l(L), r(R), v(V) {};
	inline bool operator<(const NODE &x)const {
		return l < x.l;
	}
};
set<NODE> st;

ll b[MAXN];

inline void init() {
	for(int i = 1; i <= n; ++i)
		st.ins(NODE(i, i, a[i]));
	return ;
}

//分为[l,x-1]
//注意是x-1!!
set<NODE>::iterator split(int x) {
	if(x > n)return st.end();
	auto it = --st.upper_bound((NODE) {
		x, 0, 0
	});
	if(it->l == x)return it;
	int l = it->l, r = it->r, v = it->v;
	st.erase(it);
	st.ins(NODE(l, x - 1, v));
	return st.ins(NODE(x, r, v)).first;//返回一个指针QAQ
}

//维护区间推平
void assign(int l, int r, int v) {
	auto itr = split(r + 1), itl = split(l);
	st.erase(itl, itr);
	st.ins(NODE(l, r, v));
}

//更改每个点值QAQ
//先分裂右端点,再分裂左端点QAQ
inline void solve1(int l, int r, int x) {
	auto itr = split(r + 1), itl = split(l);
	for(; itl != itr; ++itl) {
		//查询左端点,区间长度,映射到对应一个位置
		ll a = tr.qry(itl->l);
		ll len = itl->r - itl->l + 1;
		b[itl->v] += len * a;
		tr.mdf(itl->l, itl->r, -a);//区间剪掉这个值!
	}
	assign(l, r, x);//区间推平他们的v
	return ;
}

inline void solve2(int l, int r, int x) {
	split(r + 1);
	split(l);
	//直接分裂/cy
	tr.mdf(l, r, x);//直接区间修改qwq
	return;
}


signed main() {
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);

	n = read();
	m = read();
	q = read();
	for(int i = 1; i <= n; ++i)a[i] = read();
	init();//预处理ODT,树状数组
	for(int i = 1, l, r, x, opt; i <= q; ++i) {
		opt = read();
		l = read();
		r = read();
		x = read();
		if(opt == 1) {//区间推平他们!加到对应的映射数组上!
			solve1(l, r, x);
		} else {
			solve2(l, r, x);//修改的同时不要忘记split
		}
	}
	solve1(1, n, 1);
	for(int i = 1; i <= m; ++i)print(b[i], '\n');
	Ot();
	return 0;
}

做法2:

发现区间覆盖和区间加都可以通过线段树上打标记完成，加标记下传到覆盖标记可以直接贡献答案，然 后将加标记去除。覆盖标记下传到加标记就把加标记继续下传。

阴间

做法ex2:

把操作序列倒过来处理

操作1还是区间加

考虑操作2的变化,相当于每次区间求和,然后清空

直接做即可

B

S为根建立有根树

fu,0/1/2f_{u,0/1/2}表示u为根的子树,然后??的期望是什么

0->除了u被经过一次,子树都没有经过,u的父亲不存在或者已经消失

答案就是fS,0f_{S,0}

1->u子树除去u被经过两次外均未被经过,u父亲不存在或者已经消失

2->u子树除去u被经过一次外都未被经过,u父亲存在,不计入u走向他父亲的那部分的答案

同时维护pup_u表示u无论怎么走不走到他父亲的概率

考虑转移,钦点dud_u是u的儿子数

fu,1f_{u,1}

枚举一个儿子v,然后相当于这一次走到v即可

∑vfv,0∗1du\sum_{v} f_{v,0}*\frac{1}{d_u}

没有其他的....

fu,0f_{u,0}

此时我们要考虑把u走完了来进行转移,设v是第一个走向的孩子

第一种情况是走到u子树后不返回u了,答案是fv,2f_{v,2}

二是前往v之后直接返回u,此时相当于除了概率外没有动,只有其中v的信息发生了改变而已,答案是1(dv+1)(du)(fv,1+∑x!=vfx,0)\frac{1}{(d_v+1)(d_u)}(f_{v,1}+\sum_{x!=v} f_{x,0})

特殊的,如果只有v一颗子树,也适用

三是前往v之后走了若干步又返回了u,此时我们考虑概率应该是1−px−1dx+11-p_x-\frac{1}{d_x+1}

因为我们不仅需要保证从x能走到u,还有保证从x出发没有直接走回u,所以转移概率要减去直接走回去的部分

对于du=1d_u=1,我们贡献是(1−px−1dx+1)au(1-p_x-\frac{1}{d_x+1})a_u

对于du!=1d_u!=1,相当于a从v走回来然后蹦跶(1−px−1dx+1)1du−1∑v!=xfv,0(1-p_x-\frac{1}{d_x+1})\frac{1}{d_u-1}\sum_{v!=x} f_{v,0}

fu,2f_{u,2}

还是v,注意此时系数是1du+1\frac{1}{d_u+1}

第一种情况是走到v就一去不复返了,显然就是fv,2f_{v,2}作为贡献

此时pup_u的转移贡献也就是pvp_v

第二种情况就是走到v然后直接返回

此时注意一个点:我们只计算向子树内走的答案!

1dx+11du+1(fv,1+∑x!=vfx,0)\frac{1}{d_x+1}\frac{1}{d_u+1}(f_{v,1}+\sum_{x!=v}f_{x,0})

pup_u的贡献显然就是du(dx+1)(du+1)\frac{d_u}{(d_x+1)(d_u+1)},就是除掉返回父亲的

三就是走到v,向下走,然后返回

概率和上面一样(1−px−1dx+1)(1-p_x-\frac{1}{d_x+1})

只有一颗子树,贡献直接就是0,因为我们不可能在u子树内停下来

否则此时我们会少一颗子树

(1−px−1dx+1)1du∑v!=xfv,0(1-p_x-\frac{1}{d_x+1})\frac{1}{d_u}\sum_{v!=x}f_{v,0}

对于pup_u的贡献也是一样的系数

(1−px−1dx+1)∗du−1du(1-p_x-\frac{1}{d_x+1})*\frac{d_u-1}{d_u}

最后考虑叶子,此时pu,fu,2p_u,f_{u,2}都是0,因为只能返回,否则是aua_u

这样就做完了,时间复杂度就是O(n)O(n)

注意这个f_{u,2}是带上概率p_u的/ll

#include<bits/stdc++.h>
#define ll long long
const int MAXN = 5e5 + 7;
const int P = 998244353;
using namespace std;
int n, S, a[MAXN], ccnt, d[MAXN];
int nxt[MAXN], to[MAXN], home[MAXN];
inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
	d[x]++;
}
ll p[MAXN], f[MAXN][4], fac[MAXN], ifac[MAXN], inv[MAXN];
inline void add(ll &x, ll y) {
	x += y;
	if(x >= P)x -= P;
}
inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}
inline void init() {
	fac[0] = 1;
	for(int i = 1; i <= n; ++i)fac[i] = fac[i - 1] * i % P;
	ifac[n] = ksm(fac[n], P - 2);
	for(int i = n - 1; i >= 1; --i)ifac[i] = ifac[i + 1] * (i + 1) % P;
	ifac[0] = 1;
	for(int i = 1; i <= n; ++i)inv[i] = ifac[i] * fac[i - 1] % P;
	inv[0] = 1;
	return ;
}
inline void dfs(int u, int F) {
	if(d[u] == 0) {//没有儿子,叶子
		f[u][0] = a[u];
		f[u][1] = a[u];
		p[u] = f[u][2] = 0;
		return ;
	}
	ll tmp = 0;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		dfs(v, u);
		add(f[u][1], f[v][0]);
		add(tmp, f[v][0]);
		add(f[u][0], f[v][2]  % P);
		add(f[u][2], f[v][2] % P);
		add(p[u], p[v]);
	}
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		ll tp = (P + (1 - p[v] - inv[d[v] + 1]) % P) % P;
		add(f[u][0], inv[d[v] + 1] % P * inv[d[u]] % P * ((f[v][1] + tmp - f[v][0] + P) % P) % P);
		if(d[u] == 1)add(f[u][0], tp * a[u] % P);
		else add(f[u][0], tp * inv[d[u] - 1] % P * ((tmp - f[v][0] + P) % P) % P);
		add(p[u], tp * inv[d[u]] % P * (d[u] - 1) % P);
		add(p[u], inv[d[v] + 1] * inv[d[u] + 1] % P * d[u] % P);
		add(f[u][2], inv[d[v] + 1] % P * inv[d[u] + 1] % P * ((f[v][1] + tmp - f[v][0] + P) % P) % P);
		add(f[u][2], tp * inv[d[u]] % P * ((tmp - f[v][0] + P) % P) % P);
	}
	f[u][1] = f[u][1] * inv[d[u]] % P;
	f[u][0] = f[u][0] * inv[d[u]] % P;
	f[u][2] = f[u][2] * inv[d[u] + 1] % P;
	p[u] = p[u] * inv[d[u] + 1] % P;
	// printf("%d %d %lld %lld %lld %lld\n", u, d[u], f[u][0], f[u][1], f[u][2], p[u]);
	return ;
}

int main() {
	scanf("%d%d", &n, &S);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		d[i]--;
	}
	for(int i = 1, x, y; i < n; ++i) {
		scanf("%d%d", &x, &y);
		ct(x, y);
		ct(y, x);
	}
	d[S]++;
	init();
	dfs(S, 0);
	printf("%lld\n", f[S][0]);
	return 0;
}
/*

6 1
1 2 3 4 5 6
1 2
2 3
2 4
3 5
4 6


*/

C

暴力:

ljh推荐的dqa的牛逼暴力方式:

枚举一个点集S,如果S是树上大于等于3个连通块组成,不要

否则就是两个连通块组成,暴力树哈希判断同构

否则就是一个连通块,判断有没有两个重心,如果有,断开重心和重心的边,然后判断两侧子树是否同构即可

最后取最大就是答案

std:

找出点集S,T的最浅的点x,y

如果depx≥depydep_x\geq dep_y

那么我们一定有x的子树都不是y连通块内的点

因此可以把x的子树和其他部分隔开,然后以x,y为根,对于两棵树做树形DP

那么我们第一步就是枚举x,y作根QAQ

fi,jf_{i,j}表示第一棵树中的点i和第二棵树中的点j同构中对应,只保留i,j子树选出的∣S∣|S|最大值是什么

然后考虑转移,相当于我们选择i的一个子树和j的一个子树进行一个匹配,然后最大化最后匹配的权值

可以想到这个是最大权匹配,建图跑费用流即可

注意正是因为我们流不满,所以才会有局部同构的情况!

这个复杂度上界是O(n4∗∑n poly(log))O(n^4*\sum n~poly(log))

完全跑不满,但是可能卡常网络流啊

不过是我想多了/cy

#pragma GCC optimize(2)
#pragma GCC optimize(3)

#include<bits/stdc++.h>
const int MAXN = 200;
using namespace std;

int a[MAXN];
int n, ans, S, T;
int ccnt2, fst[MAXN], flw[MAXN], tt[MAXN], w[MAXN], xtt[MAXN];
inline void cuntu(int x, int y, int f, int ww) {
	ccnt2++;
	xtt[ccnt2] = fst[x];
	fst[x] = ccnt2;
	tt[ccnt2] = y;
	flw[ccnt2] = f;
	w[ccnt2] = ww;
}
inline void ct2(int x, int y, int f, int w) {
	cuntu(x, y, f, w);
	cuntu(y, x, 0, -w);
}
int f[MAXN][MAXN], rc[MAXN], ve[MAXN];
int Dep[MAXN], fa[MAXN];
int q1[MAXN], q2[MAXN];
int t1, t2, maxflw, mincst;
int dis[MAXN], vis[MAXN];
int q[MAXN], siz[MAXN];
inline int spfa(int x, int y) {
	dis[S] = 1e9;
	vis[S] = 0;
	for(int i = 0; i <= t1; ++i)dis[q1[i]] = 1e9, vis[q1[i]] = 0;
	for(int i = 0; i <= t2; ++i)dis[q2[i]] = 1e9, vis[q2[i]] = 0;
	dis[T] = 0;
	vis[T] = 1;
	int hd = 1, tl = 1;
	q[hd] = T;
	while(hd <= tl) {
		int u = q[hd];
		hd++;
		for(int i = fst[u]; i; i = xtt[i]) {
			int v = tt[i];
			if(flw[i ^ 1] && dis[v] > dis[u] - w[i]) {
				dis[v] = dis[u] - w[i];
				if(!vis[v]) {
					vis[v] = 1;
					q[++tl] = v;
				}
			}
		}
		vis[u] = 0;
	}
	return dis[S] < 1e9;
}

inline int dfs3(int u, int flow) {
	if(u == T) {
		vis[T] = 1;
		return flow;
	}
	int usd = 0, a;
	vis[u] = 1;
	for(int i = fst[u]; i; i = xtt[i]) {
		int v = tt[i];
		if(!vis[v] && flw[i] && dis[u] - w[i] == dis[v]) {
			a = dfs3(v, min(flw[i], flow - usd));
			if(a) {
				mincst += a * w[i];
				flw[i] -= a;
				flw[i ^ 1] += a;
				usd += a;
			}
			if(usd == flow)break;//流满了
		}
	}
	return usd;
}

inline int zkw() {
	maxflw = 0;
	mincst = 0;
	while(spfa(S, T)) {
		vis[T] = 1;
		while(vis[T]) {
			vis[S] = 0;
			for(int i = 0; i <= t1; ++i)vis[q1[i]] = 0;
			for(int i = 0; i <= t2; ++i)vis[q2[i]] = 0;
			vis[T] = 0;
			for(int i = 1; i <= t1; ++i)
				maxflw += dfs3(S, 1e9);
		}
	}
	return mincst;
}

inline int solve2() {
	ccnt2 = 1;
	for(int i = 1; i <= t1; ++i)
		ct2(S, q1[i], 1, 0);
	for(int i = 1; i <= t1; ++i)
		for(int j = 1; j <= t2; ++j)
			ct2(q1[i], q2[j], 1, -f[q1[i]][q2[j]]);
	for(int j = 1; j <= t2; ++j)
		ct2(q2[j], T, 1, 0);
	zkw();
	for(int i = 1; i <= t1; ++i)fst[q1[i]] = 0;
	for(int i = 1; i <= t2; ++i)fst[q2[i]] = 0;
	fst[S] = 0;
	fst[T] = 0;
	return mincst;
}
int home[MAXN], nxt[MAXN], to[MAXN], ccnt;
inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}
inline int dfs2(int u, int v) {
	if(f[u][v])return f[u][v];
	if(siz[u] == 1 || siz[v] == 1) {
		f[u][v] = 1;
		return 1;//直接匹配即可,时间复杂度O(1)
	}
	for(int i = home[u]; i; i = nxt[i]) {
		int x = to[i];
		if(x == fa[u] || ve[i])continue;
		for(int j = home[v]; j; j = nxt[j]) {
			int y = to[j];
			if(y == fa[v] || ve[j])continue;
			dfs2(x, y);
		}
	}
	t1 = 0, t2 = 0;
	for(int i = home[u]; i; i = nxt[i]) {
		int x = to[i];
		if(x == fa[u] || ve[i])continue;
		q1[++t1] = x;
	}
	for(int i = home[v]; i; i = nxt[i]) {
		int x = to[i];
		if(x == fa[v] || ve[i])continue;
		q2[++t2] = x;
	}
	f[u][v] = -solve2() + 1;//先搞,然后最后清空即可,取负数
	//最后我自己匹配成功啦!
	return f[u][v];
}
inline void dfs1(int u, int F) {
	siz[u] = 1;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F || ve[i])continue;
		fa[v] = u;
		dfs1(v, u);
		siz[u] += siz[v];
	}
	return;
}
inline void solve(int x, int y) {
	memset(f, 0, sizeof(f));
	fa[x] = 0;
	fa[y] = 0;
	dfs1(x, 0);
	dfs1(y, 0);
	dfs2(x, y);
	ans = max(ans, f[x][y]);
	return ;
}
inline void dfs(int x, int F) {
	for(int i = home[x]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		Dep[v] = Dep[x] + 1;
		rc[v] = i;//qwq!
		dfs(v, x);
	}
	return;
}
int main() {
	n = 1;
	while(scanf("%d", &a[n]) != EOF) {
		a[n]++;
		++n;
	}
	S = n + 2;
	T = n + 3;
	n /= 2;
	ccnt = 1;
	for(int i = 1; i <= n; ++i) {
		ct(a[i], a[i + n]);
		ct(a[i + n], a[i]);
	}
	++n;
	dfs(1, 0); //预处理深度qwq
	for(int i = 2; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
			if(i == j)continue;
			if(Dep[i] >= Dep[j]) {
				ve[rc[i]] = 1;//i向他父亲的那个干掉他!
				ve[rc[i] ^ 1] = 1;
				solve(i, j);
				ve[rc[i]] = 0;
				ve[rc[i] ^ 1] = 0;
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

zkw费用流复习:

这个费用流本质上就是每次增广所有的最短路

所以我们先跑一遍spfa求最短路,注意我们只能在残量网络上走

然后再在最短路上增广跑最大流,dinic即可!!

有个优化就是一直dinic直到所有当前最短路都被干掉为止,再跑新的最短路

Powered by Gridea RSS