【题解】牛客小白月赛22
A - 操作序列
模拟题,因为是个模拟,所以就一模到底,索性将输入也变成字符串模拟了。
有一些细节的地方处理要小心,可以离线下来胡搞,也可以平衡树在线。
B - 树上子链
树的直径
树的直径有很多种求法,先将这棵树改成有根树
让代表从结点到以其为根的子树中任意一个点的路径最大值
为节点的点权,为节点的第个儿子的编号
则动态转移方程为
C - 交换游戏
Dfs乱搞一下即可,可以将这个字符串看作是一个二进制串,把所有的情况先处理一下,然后对应询问直接输出即可。
D - 收集制片
因为最多只有10片纸片,所以大可枚举所有的收集顺序,然后在其中取一个最小值。
状压就更好了。
我的数据造的有问题,我比赛结束后才发现这个问题,输入格式不对,现在已经订正了。
E - 方块涂色
可以用总的个数,减去涂色的行数和列数,然后再加上重合的部分。
F - 累乘数字
先输出n,然后紧跟着输出2d个0即可。
G - 仓库选址
简要题意是找到一个位置,使得其它所有位置上的数乘以两个位置之间的距离的总和最小。
直接暴力枚举每一个位置然后取一个最小值即可。
H - 货物种类
每次选择一段区间放入物品,问所有操作完成后物品种类最多的位置是几。
区间操作,只有在最后有一次询问
所以很显然可以用差分进行求解
差分对于每个位置维护一个数组,最后统计更新答案
当然,也可以用某些数据结构来解。
I - 工具人
先计算从原点到该点线段的角度,以及从原点开始的一条线相对于该点<=d的角度应在哪个角度间隔(三角形)内。
对所有间隔进行排序创建循环列表,在所有可能的位置分解列表,使其变为线性,然后对每个线性列表用贪心的思想进行求解。
排序时,要注意浮点比较。
J - 计算 A + B
没有和大家说清楚前导零的问题,对不起
这个题定位是签到题,简单的字符串模拟一下即可
还要注意一下高精