比赛链接:
https://codeforces.com/contest/1099
A: Snowball
直接按照题意模拟即可: 47974196
B: Squares and Segments
这题要注意的是不一定真的要正好凑够n个, 而是可以少凑成n+x个的矩阵然后少绘制x个
弱智的zdw读错了题然后WA了一波
代码: 47981321
C: Postcard
裸的贪心题, 长度过多就删除, 长度过少就增加, 不足就是无解
注意 * 标记的字符是可以有0~任意个, 也就是可以删除的
代码: 47987204
D: Sum in the tree
由于题目给的是从当前点到根的和, 所以我们可以把两个节点上的前缀和尽可能放在他们的公共祖先上
我们可以在每个点上先补足前缀缺失的值, 然后贪心地将每个点的值向根移动
当一个点有多个儿子时, 取所有儿子中最小的那个作为该节点的值即可
代码: 48001022
E: Nice table
留坑, 回头补
F: Cookies
不难发现吃饼干和走路是互相独立的, 而且经过的点确定之后, 一定是先吃花费少的饼干更优
所以我们做dfs并用树状数组维护当前经过的路径上的饼干按"每块花费" 的 花费 和 数量 的前缀和
然后减去路途的花费后, 用剩下的时间在树状数组上二分出能吃到的饼干的最多数量即可
这题 $n$ 只有 $10^5$ 且单儿子的点会被直接切断, 所以 $O(nlog^2n)$ 跑的也很快
代码: 48014890
