巅峰赛#22 全题解

奶龙

2025-06-24 12:52:53

发布于：河南

2阅读

0回复

0点赞

巅峰赛 22 题解

拿一个 map 把所有出现过的人存起来，然后扫一遍所有人，看哪些不在 map 里即可。

首先只有能选出 $a\in A,b\in B,c\in C$ 且 $(a+b)\bmod 10=c$ 可能有解。

现在如果没有进位，直接输出，否则发现有可能因为存在进位导致不合法。

考虑在进的那个 $1$ 上加一个数，如果能满足不会再次进位，且这个数在 $C$ 里能找到，就有解。否则无解。

倒着枚举所有答案，假设当前枚举的是 $d$ ，然后把所有不是 $d$ 的倍数的数做操作。

如果发现操作前所有数都是 $d$ 的倍数，答案就是 $d+1$ ，否则如果做完操作后数组的 gcd 为 $d$ ，直接输出，否则继续枚举。

先按照幸福度从小到大排序。

然后为了得到一个物品的幸福度，并花费最少的钱，一定选择一个物品后面最便宜的物品与其配对。

这样的配对数量不超过 $n$ 对，然后做一个完全背包即可。

首先对于一次询问 $[L,R]$ ，对每个网友的区间 $[l,r]$ 分讨。

上述东西开两棵线段树维护即可。

注意到随机 bfs 的顺序只有一个限制：一个点的子树的点不能出现在这个点之前。

然后假设根是 $1$ ，答案就是 $n!\times \displaystyle \prod_{i=1}^{n}\dfrac{1}{siz_i}$ ，其中 $siz_i$ 表示 $i$ 的子树大小。

然后根不固定的话直接换根 dp 就行。具体就是对于 $u$ 的儿子 $v$ ， $ans_v\leftarrow ans_u\times siz_v\times \dfrac{1}{n-siz_v}$ 。

上面的题目没有非常困难的实现，所以不放代码了。

有帮助，赞一个

去预览

0/2000

这里空空如也