EA 练习赛2

P7246 手势密码

有一棵带点权的树。定义一次操作为选择树上的一条简单路径，并将这条简单路径上的所有点点权减去 11。问至少需要多少次操作，使树上所有点的点权恰好变为 $0$ 。

题解非常玄妙,贪心!

对于在u处的匹配

首先加入每条子树能向上伸 $v_i$ 条路径

结论 1

在保证u子树内操作次数不变的前提下,尽可能让u向上提供的帮助多!

这个操作次数不变是什么意思呢?

其实就是指,如果我们向上延伸能够让u满足,就延伸这些数量,不可能两两匹配一车然后不给向上延伸达到u,从u处新开路径

视野是这样的:

1->2

2处理完后,加入固定操作次数是2,那么最好是能向上延伸2条路径,而不是1条

...那么结论2也很显然了

结论 2

在结论一成立的前提下,尽可能让路径跨子树匹配来减少这个答案

就是说

1->2

1->3

1->4

1是根

显然此时最大化1子树内匹配可以最小化答案

也就是说,我们在u不新开的情况下尽可能的新的两两匹配以减少子树内答案!

于是考虑怎么写代码

c=min\lfloor \frac{\sum v_i}{2} \rfloor,\sum v_i-max{v_i}

这个是最大匹配数QAQ

保证贪心结论?

$c'=max(0,min(c,a_u,\sum v_i - a_u))$

你会发现这个 $a_u$ 很不对劲qaq

但是转念一想,我们这个地方啊最多跨过 $a_u$ 条路径

所以也就能解释的出来啦!

节点u能向上帮助次数 $help=a_u-c'$

因为除了匹配外都要重开向上QAQ

对答案的贡献 $ans=max(a_u-\sum v_i + c',0)-c'$

就是匹配的减掉QAQ

总时间复杂度 $O(n)$

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 6e6 + 7;
ll a[MAXN];
int u[MAXN], v[MAXN], n;
int ccnt, home[MAXN], nxt[MAXN], to[MAXN];
inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}
namespace Generate {
	int n, seed;
	static const int mod = 1e9;
	int Rand(int x) {
		seed = (1ll * seed * 0x66CCF + 19260817ll) % x + 1;
		seed = (1ll * seed * 0x77CCF + 20060428ll) % x + 1;
		seed = (1ll * seed * 0x88CCF + 12345678ll) % x + 1;
		seed = (1ll * seed * 0x33CCCCFF + 10086001ll) % x + 1;
		return seed;
	}
	void RS(ll *a, int *u, int *v) { //你需要传入三个参数，分别表示点权，一条边的两个端点
		int cnt = 0;
		for(int i = 1; i <= n; i++)a[i] = Rand(mod);
		for(int i = 2; i <= n; i++) {
			int fa = Rand(i - 1);
			cnt++;
			u[cnt] = fa, v[cnt] = i;
			ct(u[cnt], v[cnt]);
			ct(v[cnt], u[cnt]);
		}
	}
};
ll ans;
ll b[MAXN];
inline void dfs(int u, int F) {
	ll mtp = 0;
	ll tmp = 0;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		dfs(v, u);
		tmp += b[v];
		mtp = max(mtp, b[v]);
	}
	mtp = min(tmp / 2, tmp - mtp);
	b[u] = max(0ll, min(mtp, min(a[u], tmp - a[u])));
	//最优匹配次数
	ans += max(a[u] - tmp + b[u], 0ll) - b[u];
	// printf("nodeU: %d %d %d %d %d\n", u, mtp, tmp, b[u], ans);
	b[u] = max(0ll, a[u] - b[u]);
	// printf("!%d\n", b[u]);
	return ;
}
int main () {
	int op;
	scanf("%d", &op);
	if(op == 1) {
		scanf("%d", &n);
		for(int i = 1; i <= n; ++i) {
			scanf("%lld", &a[i]);
		}
		for(int i = 1; i < n; ++i) {
			scanf("%d%d", &u[i], &v[i]);
			ct(u[i], v[i]);
			ct(v[i], u[i]);
		}
	} else {
		int n;
		scanf("%d %d", &Generate::seed, &n); //输入种子和n
		Generate::n = n; //记得赋值
		Generate::RS(a, u, v); //开始工作
	}
	dfs(1, 0);
	printf("%lld\n", ans);
	return 0;
}

~~抄袭题解真开心!~~

P7273 ix35 的等差数列

做法并不难,枚举公差众数首相即可

但是被一车人叉来叉去(

叉ub

即首相可能是负数....然后你的数组就越界了

叉尾项

某个首相对应的尾项可能大于w

公差上限

....(w-1)/(n-1)要移过去

超了牛逼人的题解!

#include<iostream>
using namespace std;
int n, w, ans;
int a[300005], c[300005], t[300005];
int main() {
	cin >> n >> w;
	if(n == 1) {
		cout << 0;
		return 0;
	}
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	ans = n;
	for(int k = 0; 1 + (n - 1)*k <= w; k++) {
		for(int i = 1; i <= n; i++)
			if(a[i] - k * (i - 1) > 0 && a[i] - k * (i - 1) + (n - 1)*k <= w)
				t[a[i] - k * (i - 1)]++, ans = min(ans, n - t[a[i] - k * (i - 1)]);
		for(int i = 1; i <= n; i++)
			if(a[i] - k * (i - 1) > 0)
				t[a[i] - k * (i - 1)] = 0;
	}
	cout << ans;
	return 0;
}

P7275 计树

这个题很牛逼啊

首先原问题可以变成一个把 $1到n$ 排好序的序列划分成若干段然后用凯莱定理拼起来的答案

差不多就是 $\prod x_i n^{r-2}$ 那个东西

然后我们发现这样玩命计重

先变成生成函数的卷积的形式

$F(x)=\sum_{i=2}^{n} i*n*x^i$

$ans=(\sum_{i=1}^{\infty}F(x)^i)$

这个东西乘上一个容斥系数就能算出真实方案了

马耀华爷爷告诉我们一种很不错的方式容斥

(一不小心就截多了QAQ)

也就是说,我们只看一个真实方案,然后抓住他为什么被算重的原因,也就是他被算重的虚假方案的形式

相当于我们把这个树划分成了不同的几段,然后让这些段按照相同的样子拼起来,然后加起来系数就不太对

所以说我们要把每个虚假方案加权削细一点!也就是加上一个容斥系数,这个容斥系数满足求和等于1

也就是 $(\sum_{i=1}^{\infty} G(i)^i)[x^n]=[n>1]$

又因为所有方案本质相同,所以我们一起算一起削也是一样的!

$F(x)=\sum_{i=2}^{n} G(x)[x^i]*i*n*x^i$

问题是这个容斥系数具体是啥啊QAQ

你会发现这个相当于

$\frac{1}{1-G(x)}-1=\frac{1}{1-x}-1-x$

于是就做完了!

$G(x)=\frac{x^2}{1-x+x^2}$

直接exp这个F即可qwq

P7276 送给好友的礼物

做法并不难qwq但是我就是不会QAQ

乱搞:

dfs拿出来,你会发现这个答案一定是某一个人选择了dfs序上连续的一段

那么我们就可以枚举这个人选的一段,然后另一个人走完另一段即可,然后就能知道这个枚举的答案

然后我们发现这个WA了

于是我们可以打乱儿子节点的顺序重新得到dfs序,来1000遍就过了

正解:

问题转换为第一个人先走,走完一棵树,它用的时间用第二个人去削减

$f_{u,i}$ 表示点u代表的子树,然后用了i秒解决,然后最多削减多少时间

转移考虑合并子树,相当于把u的i秒分配给他所有的子树,也就是一个背包的过程

我们肯定要最大化这个时间吗...所以就么了

如果我们能走遍整棵树,则好像这棵树到他父亲的边也不需要了,所以就额外-2

预处理 $tim[u]$ 表示在以 u 为根的子树上直接遍历所有关键节点所花费的最小时间。

最终答案即为 $max(i,tim[1] - f[1][i])$ 的最小值。

夏晓光(loveJY)的博客

P7246 手势密码

P7273 ix35 的等差数列

P7275 计树

P7276 送给好友的礼物

qbxt省选数学考试