09-10 21:13 门头沟学院 Java 发布于浙江
关注
小红书后端9.10笔试
第一题：
把数组排序后dp，dp[i]代表从1到i最多可以保留几个数。遍历数组，二分查找左边第一个差值大于d的数，假如二分出来下标为j，直接dp[i] = dp[j] + 1。dp之后扫一遍dp数组取全局最大值，答案就是n减去这个全局最大值。注意如果删掉数量为奇数的话，答案得减一
第二题：
首先对于字符串第一个plog一定是不会被评论的，由此可得只要轮数足够多，所有与第一个plog不同的plog一定会被删除，所以把答案设置为第一个连续的字符的长度。
通过观察可得，可以定义一个变量x，遇到一个不同于第一个plog的plog加一，遇到相同的话，如果x大于0就把x减一，否则就把答案减一。
第三题：
由题可得这是一棵树。如果x>=y，显然可以一个一个节点炸，输出n*x就行。否则我们要让使用操作2的次数尽可能多。要让操作2尽可能多的话，就要通过使用操作一把连通块数量变得尽可能多。这可以用树上dp作。
定义dp[u][0]为对该节点使用操作1，dp[u][1]是不使用，以u为根节点得到的子树内最大连通块的数量。
对每个节点初始化 dp[u][1] = 1， dp[u][0] = 0
转移时通过dfs，对于所有子节点v，有：
dp[u][0] = sum(max(dp[v][0]), dp[v][1]));
dp[u][1] = sum(max(dp[v][0]), dp[v][1] - 1));
使用操作2最大次数就是max(dp[root][1], dp[root][0])，这个次数乘y加上剩余节点数乘x就是答案了
把数组排序后dp，dp[i]代表从1到i最多可以保留几个数。遍历数组，二分查找左边第一个差值大于d的数，假如二分出来下标为j，直接dp[i] = dp[j] + 1。dp之后扫一遍dp数组取全局最大值，答案就是n减去这个全局最大值。注意如果删掉数量为奇数的话，答案得减一
第二题：
首先对于字符串第一个plog一定是不会被评论的，由此可得只要轮数足够多，所有与第一个plog不同的plog一定会被删除，所以把答案设置为第一个连续的字符的长度。
通过观察可得，可以定义一个变量x，遇到一个不同于第一个plog的plog加一，遇到相同的话，如果x大于0就把x减一，否则就把答案减一。
第三题：
由题可得这是一棵树。如果x>=y，显然可以一个一个节点炸，输出n*x就行。否则我们要让使用操作2的次数尽可能多。要让操作2尽可能多的话，就要通过使用操作一把连通块数量变得尽可能多。这可以用树上dp作。
定义dp[u][0]为对该节点使用操作1，dp[u][1]是不使用，以u为根节点得到的子树内最大连通块的数量。
对每个节点初始化 dp[u][1] = 1， dp[u][0] = 0
转移时通过dfs，对于所有子节点v，有：
dp[u][0] = sum(max(dp[v][0]), dp[v][1]));
dp[u][1] = sum(max(dp[v][0]), dp[v][1] - 1));
使用操作2最大次数就是max(dp[root][1], dp[root][0])，这个次数乘y加上剩余节点数乘x就是答案了
全部评论
热爱生活的小山竹希望offer多多
东南大学 Java
第二题可以用递归做吗？我差最后五秒钟没来得及提交，但是已经做出来了
牛客151722204号
中山大学 集成电路IC设计
相关推荐
投递小红书等公司10个岗位
查看13道真题和解析 黑曼巴在线招人：好强好强好强
哈基米好羡慕
哈基米好羡慕 点赞 评论 收藏
分享
09-14 11:53
中南大学 Java 点赞 评论 收藏
分享