夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

ZR20秋季普转提day2

2020-09-15 12 min read # 博弈论 # 计数题 # 比赛题 # 构造 # 动态规划

zzzz

孙笑川都干了那些坏事?

A

考虑他的转化问题:随机一个n个点的排列,从左往右删除每次删掉一个点之后我们把他的所有祖先都删除掉

那么答案就是这样一个排列的期望删除次数

不难发现可以变成每个数期望删除次数之和

然后就会发现概率是1/siz1/siz,也就是说我有1/siz1/siz的几率在排列中比我儿子都靠前

对上述求和即可

复杂度O(n)



#include<bits/stdc++.h>
#define ll long long
const int P = 998244353;
const int MAXN = 1e7 + 7;
int ccnt, home[MAXN], nxt[MAXN], to[MAXN], n, siz[MAXN];
ll ans, A[MAXN];

namespace fastIO {
#define BUF_SIZE (1<<24)
	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() {
		char s = nc();
		int x = 0;
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
};
using namespace fastIO;

inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}

inline void dfs(int u) {
	siz[u] = 1;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		dfs(v);
		siz[u] += siz[v];
	}
	ans = (ans + A[siz[u]]) % P;
}

int main() {
	n = read();
	for(int i = 2, x; i <= n; ++i) {
		x = read();
		ct(x, i);
	}
	A[0] = 1;
	A[1] = 1;
	for(int i = 2; i <= n; ++i)		{
		A[i] = (P - (P / i)) * A[P % i] % P;
	}
	dfs(1);
	printf("%lld\n", ans);
	return 0;

}

B

考场上用数据结构写了个很能卡的贪心hhh

但是出题人不一定想的到,数据也很水就过了

正确做法:

n为偶数,随便拿走一个变成奇数的情况

n为奇数,我们按照a排序,然后拿走第一个,

然后剩下的我们两组两组之间拿走b值较大的那个

可以证明我们拿走了最大的那个a就能保证我们剩下一定不会卡

也可以证明因为我们每次都拿了两两较大的b,rank最劣也是倒2,倒4,倒6.....一定大于倒1,倒3....即sum/2sum/2

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e6 + 7;
int n;
ll S1, S2;
struct rec {
	int x, y, id;
	bool operator<(const rec &w)const {
		return x > w.x;
	}
} a[MAXN];

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i].x);
	}
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i].y);
		a[i].id = i;
	}
	sort(a + 1, a + n + 1);
	int i = 0;
	printf("%d\n", n / 2 + 1);
	if(!(n & 1)) {
		printf("%d %d ", a[1].id, a[2].id);
		i = 3;
	} else {
		printf("%d ", a[1].id);
		i = 2;
	}
	for(; i <= n; i += 2) {
		if(a[i].y >= a[i + 1].y) {
			printf("%d ", a[i].id);
		} else {
			printf("%d ", a[i + 1].id);
		}
	}
	puts("");
	return 0;
}

C

二分之后限制二变成了子树内至多有一些点能染色

然后我们按照这个range的性质dp去判断可不可行

细节有一堆

  1. 上界更新的时候注意+1
  2. 不要阴间的重设上界范围
  3. 注意判断siz和down大小范围,all和up的范围

坑死了,因为造不出很强的数据所以过拍不过题调了好久

code:


#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 3e5 + 7;
const int inf = 1e9 + 7;
int n, ccnt, home[MAXN], nxt[MAXN], to[MAXN];
int up[MAXN], down[MAXN], A, B, g[MAXN];
int f[MAXN], flg, siz[MAXN], all,rc[MAXN];
inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}

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)continue;
		dfs1(v, u);
		siz[u] += siz[v];
	}
	if(n - siz[u] < up[u]) {
		flg = 0;
	}
	return ;
}

inline void dfs(int u, int F) {
	bool tflg = 0;
	int tmp = 1;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		dfs(v, u);
		f[u] += f[v];
		tmp += up[v];
	}
	up[u] = min(tmp, up[u]);
	if(f[u] < down[u])
		f[u] = down[u];
	if(f[u] > siz[u])flg = 0;
	if(f[u] > up[u] || f[u] > all)flg = 0;
	return;
}

inline int chk(int x) {
	all = x;
	for(int i = 1; i <= n; ++i) {
		rc[i] = up[i];
		up[i] = x - up[i];
	}
	memset(f, 0, sizeof(f));
	memset(g, 0, sizeof(g));
	flg = 1;
	dfs(1, 0);
	if(x > up[1]) flg=0;
	for(int i = 1; i <= n; ++i) {
		up[i] = rc[i];
	}
	return flg;
}

inline void solve() {
	int l = 0, r = n + 1, ans = -1, mid = 1;
	for(int i = 1; i <= n; ++i) {
		l = max(l, down[i] + up[i]);
	}
	while(l <= r) {
		mid = (l + r) >> 1;
		if(chk(mid)) {
			r = mid - 1;
			ans = mid;
		} else {
			l = mid + 1;
		}
	}
	printf("%lld\n", ans);
	return;
}

signed main() {
	scanf("%lld", &n);
	for(int i = 1, x, y; i < n; ++i) {
		scanf("%lld%lld", &x, &y);
		ct(x, y);
		ct(y, x);
	}
	scanf("%lld", &A);
	for(int i = 1, x, y; i <= A; ++i) {
		scanf("%lld%lld", &x, &y);
		down[x] = max(down[x], y);
	}
	scanf("%lld", &B);
	for(int i = 1, x, y; i <= B; ++i) {
		scanf("%lld%lld", &x, &y);
		up[x] = max(up[x], y);
	}
	flg = 1;
	dfs1(1, 0);
	if(!flg)return puts("-1"), 0;
	solve();
	return 0;
}

/*

3
1 3
1 2
1 4
0
3
2 3
3 2
4 2


*/

D

博弈论+计数dp

非常烦啊

首先预处理两个数组g[0/1][x][i]表示alice/bob在x子树任意总方案(包括染色方案和重儿子选择方案)下保证权值小于等于i的方案数,这个方案可以不均衡

转移:,以alice层为例

g[1][x][i]=g[1][ls][i]∗a[rs]+g[1][rs][i]∗a[ls]g[1][x][i]=g[1][ls][i]*a[rs]+g[1][rs][i]*a[ls]

a数组是任意选择的方案数(不限制权值)

表示我们Alice在转移的时候可以选择左子树走下去也可以选择右子树走下去

但是我们选择什么就是什么,所以另一颗子树随便选择

g[2][x][i]=2∗g[2][ls][i]∗g[2][rs][i]g[2][x][i]=2*g[2][ls][i]*g[2][rs][i]

表示我们bob在转移时,左右子树必须都能够<=i<=i否则一切换可能会导致最后走下去权值变大

然后处理f数组f0/1,i,xf_{0/1,i,x}表示alice/bob从上到下走到点x,权值等于i的均衡方案数

转移的时候(假设我们在转移)我们会发现,如果这个正好是他的层,就直接从上面继承下来就好了

否则我们可能要面临对手切换子树的风险,所以要保证另一颗子树走下去权值不会超过i

也就是乘上g0/1,i,rsg_{0/1,i,rs}

最后到叶子的时候,你会发现我们这个方案乘起来一定包括了整棵树的决策,所以只需要f数组求个和然后对应相乘了

因为我们再alice层只会让bob去计算另一颗子树的选择方案,而在bob层只会让alice算,那么和你的第二维没关系,之和你这条链长啥样有关

复杂度O(nk)O(nk)

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 998244353;
const int MAXN = 5e3 + 7;
int n, K, ans;
int dep[MAXN], fa[MAXN], ls[MAXN], rs[MAXN];
int g[3][MAXN][MAXN], f[3][MAXN][MAXN], a[MAXN];

inline void add(int &x, ll y) {
	x = x + y > P ? (x + y - P) : (x + y);
}

inline void dfs(int u) {
	if(!ls[u] && !rs[u]) {
		for(int i = 1; i <= K; ++i) {
			g[1][u][i] = g[2][u][i] = 1ll * i * K % P;
		}
		a[u] = 1ll * K * K % P;
		return ;
	}
	dep[ls[u]] = dep[u] + 1;
	dep[rs[u]] = dep[u] + 1;
	if(ls[u])dfs(ls[u]);
	if(rs[u])dfs(rs[u]);
	a[u] = 2ll * a[ls[u]] % P * a[rs[u]] % P;
	if(dep[u] & 1) {//奇数,bob
		for(int i = 1; i <= K; ++i) {
			add(g[1][u][i], 1ll * g[1][ls[u]][i] * a[rs[u]] % P + 1ll * g[1][rs[u]][i] * a[ls[u]] % P);
			g[2][u][i] = 2ll * g[2][ls[u]][i] % P * g[2][rs[u]][i] % P;
		}
	} else {
		for(int i = 1; i <= K; ++i) {
			g[1][u][i] = 2ll * g[1][ls[u]][i] % P * g[1][rs[u]][i] % P;
			add(g[2][u][i], 1ll * g[2][ls[u]][i] * a[rs[u]] % P + 1ll * g[2][rs[u]][i] * a[ls[u]] % P);
		}
	}
	return ;
}

inline void dfs2(int u) {
	if(!ls[u] && !rs[u]) {
		int suma = 0, sumb = 0;
		for(int i = 1; i <= K; ++i) {
			add(suma, f[1][u][i]);
			add(sumb, f[2][u][i]);
		}
		add(ans, 1ll * suma * sumb % P);
		return ;
	}
	if(dep[u] & 1) {
		for(int i = 1; i <= K; ++i) {
			f[1][rs[u]][i] = f[1][ls[u]][i] = f[1][u][i];
			f[2][ls[u]][i] = 1ll * f[2][u][i] * g[2][rs[u]][i] % P;
			f[2][rs[u]][i] = 1ll * f[2][u][i] * g[2][ls[u]][i] % P;
		}
	} else {
		for(int i = 1; i <= K; ++i) {
			f[2][rs[u]][i] = f[2][ls[u]][i] = f[2][u][i];
			f[1][ls[u]][i] = 1ll * f[1][u][i] * g[1][rs[u]][i] % P;
			f[1][rs[u]][i] = 1ll * f[1][u][i] * g[1][ls[u]][i] % P;
		}
	}
	if(ls[u])dfs2(ls[u]);
	if(rs[u])dfs2(rs[u]);
}


int main() {
	scanf("%d%d", &n, &K);
	for(int i = 2, x; i <= n; ++i) {
		scanf("%d", &x);
		if(!ls[x])ls[x] = i;
		else rs[x] = i;
	}
	dfs(1);
	for(int i = 1; i <= K; ++i)f[1][1][i] = f[2][1][i] = 1;
	dfs2(1);
	printf("%d\n", ans);
	return 0;
}
Powered by Gridea RSS