巅峰赛 22 题解
未出现的人
拿一个 map 把所有出现过的人存起来,然后扫一遍所有人,看哪些不在 map 里即可。
A+B
首先只有能选出 a∈A,b∈B,c∈Ca\in A,b\in B,c\in Ca∈A,b∈B,c∈C 且 (a+b) mod 10=c(a+b)\bmod 10=c(a+b)mod10=c 可能有解。
现在如果没有进位,直接输出,否则发现有可能因为存在进位导致不合法。
考虑在进的那个 111 上加一个数,如果能满足不会再次进位,且这个数在 CCC 里能找到,就有解。否则无解。
GCD
倒着枚举所有答案,假设当前枚举的是 ddd,然后把所有不是 ddd 的倍数的数做操作。
如果发现操作前所有数都是 ddd 的倍数,答案就是 d+1d+1d+1,否则如果做完操作后数组的 gcd 为 ddd,直接输出,否则继续枚举。
礼物
先按照幸福度从小到大排序。
然后为了得到一个物品的幸福度,并花费最少的钱,一定选择一个物品后面最便宜的物品与其配对。
这样的配对数量不超过 nnn 对,然后做一个完全背包即可。
聊天室
首先对于一次询问 [L,R][L,R][L,R],对每个网友的区间 [l,r][l,r][l,r] 分讨。
* l<Ll<Ll<L,此时只关注最大的 rrr。
* l≥Ll\ge Ll≥L 且 l≤R−d+1l\le R-d+1l≤R−d+1,此时只关注最大的区间长度。
* l>R−d+1l> R-d+1l>R−d+1,此时不可能合法。
上述东西开两棵线段树维护即可。
BFS
注意到随机 bfs 的顺序只有一个限制:一个点的子树的点不能出现在这个点之前。
然后假设根是 111,答案就是 n!×∏i=1n1sizin!\times \displaystyle \prod_{i=1}^{n}\dfrac{1}{siz_i}n!×i=1∏n sizi 1 ,其中 sizisiz_isizi 表示 iii 的子树大小。
然后根不固定的话直接换根 dp 就行。具体就是对于 uuu 的儿子 vvv,ansv←ansu×sizv×1n−sizvans_v\leftarrow ans_u\times siz_v\times \dfrac{1}{n-siz_v}ansv ←ansu ×sizv ×n−sizv 1 。
上面的题目没有非常困难的实现,所以不放代码了。