牛客国庆集训派对Day4
Solved : A、D、G、H、I、J
unsolve : B、C、E、F
A.深度学习
Solution of A
大胆猜测,答案为n。然后感觉没什么问题,就交了,就过了。 显然,最优情况下是n组各选中一次,故答案为n。
Code of A
1 |
|
D.最小生成树
Solution of D
因为边权为au+av,所以最小生成树即将点权最小的点与其他所有点直接相连得到的树,故答案为(n−2)min(ai)+∑ni=1ai。
Code of D
1 |
|
G.区间权值
Solution of G
将f(l,r)展开,然后化简,得到式子:∑ni=1wi⋅(cn−cn−i−ci−1), 其中ci=∑ij=1bj、bi=∑ij=1aj,即b为a的前缀和,c为a的前缀和的前缀和。
Code of G
1 |
|
H.树链博弈
Solution of H
队友说只要存在树上某层的黑色结点数为单数,便是先手必胜,otherwise。
Code of H
1 |
|
I.连通块计数
Solution of I
包含根结点的方案数为:∏ni=1(ai+1)
不包含根结点的方案数为:∑ni=1ai⋅(ai+1)/2
Code of I
1 |
|
J.寻找复读机
Solution of J
模拟即可,注意不说话的人也可能是复读机。
Code of J
1 |
|