竞赛讨论区 > 【题解】牛客小白月赛22
头像
houzhibin
编辑于 2020-02-24 11:03
+ 关注

【题解】牛客小白月赛22

A - 操作序列

模拟题,因为是个模拟,所以就一模到底,索性将输入也变成字符串模拟了。
有一些细节的地方处理要小心,可以离线下来胡搞,也可以平衡树在线。

我的解法

B - 树上子链

树的直径
树的直径有很多种求法,先将这棵树改成有根树

代表从结点到以其为根的子树中任意一个点的路径最大值

节点的点权,节点的第个儿子的编号
则动态转移方程为

我的解法

C - 交换游戏

Dfs乱搞一下即可,可以将这个字符串看作是一个二进制串,把所有的情况先处理一下,然后对应询问直接输出即可。

我的解法

D - 收集制片

因为最多只有10片纸片,所以大可枚举所有的收集顺序,然后在其中取一个最小值。
状压就更好了。
我的数据造的有问题,我比赛结束后才发现这个问题,输入格式不对,现在已经订正了。

我的解法

E - 方块涂色

可以用总的个数,减去涂色的行数和列数,然后再加上重合的部分。

我的解法

F - 累乘数字

先输出n,然后紧跟着输出2d个0即可。

我的解法

G - 仓库选址

简要题意是找到一个位置,使得其它所有位置上的数乘以两个位置之间的距离的总和最小。
直接暴力枚举每一个位置然后取一个最小值即可。

我的解法

H - 货物种类

每次选择一段区间放入物品,问所有操作完成后物品种类最多的位置是几。
区间操作,只有在最后有一次询问
所以很显然可以用差分进行求解
差分对于每个位置维护一个数组,最后统计更新答案
当然,也可以用某些数据结构来解。

我的解法

I - 工具人

先计算从原点到该点线段的角度,以及从原点开始的一条线相对于该点<=d的角度应在哪个角度间隔(三角形)内。
对所有间隔进行排序创建循环列表,在所有可能的位置分解列表,使其变为线性,然后对每个线性列表用贪心的思想进行求解。
排序时,要注意浮点比较。

我的解法

J - 计算 A + B

没有和大家说清楚前导零的问题,对不起
这个题定位是签到题,简单的字符串模拟一下即可
还要注意一下高精

我的解法

全部评论

(18) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐