keduoli - 个人主页动态 - 牛客网

发布(114) 评论刷题收藏

2024-01-13 10:57

已编辑

東京大学 golang

牛客周赛 Round 11 解题报告 | 珂学家 | 线性dp+大剪枝

前言   整体评价 T3和round 9的T3重复了，好意外。T4有点意思，比赛中一度不敢下手，然后试试骗分，发现过了。后来才知道，原来元素两两不等，那基本就退化为了。  A. 小美的外卖订单编号 index 1 / index 0的问题 先减1，再加1 import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(new BufferedInputStream(...

牛客周赛解题报告系列

0 点赞评论收藏

分享

2023-09-09 23:24

東京大学 golang

牛客练习赛115 解题报告弱化版

牛客练习赛115 解题报告 详细的题解链接https://blog.nowcoder.net/n/e725cfc01d7b4f6baa1e328a97a64dc9这场太难了，所以只写了4题A. 构造解分组排序，把最大值放中间，然后按序放置其他组，对于每个组左右侧的方案为 m+1 因此总的方案数除了山峰的组，(组大小+1)的累乘B. 二分贪心模拟/记忆化搜索二分的时候，右侧区间大于等于左侧，因此贪心往右侧寻找。还可以根据数据规模，n=100000，cnt=20，设计状态，用记忆化搜索，如果你没想到贪心的话。C. 差分题把这个式子抽象为 斜率这题的核心是: 最大的斜率一定在相邻的元素中假定 最大的...

0 点赞评论收藏

分享

2023-09-09 18:59

已编辑

東京大学 golang

牛客练习赛115 解题报告 | 珂学家 | 记忆化 + 斜率极值 + dfn序&树状数组

前言   整体评价 比赛刚开始的时候，看到清一色的英语题目，就有种不祥的预感，果然...... 感觉这场练习赛好难，在知识范围内是前四题，但是实际能ac 4题的却很少，是真的难。  A. Mountain sequence 要求构建一个山峰数组，求累计的方案总数 其实这题是构造题，按照要求确定山峰(最大值)后, 然后决策其他的数往那放置。 可以分组(按值)排序，然后从大到小放置。 对于某组(size=m), 则左右侧{(0, m), (1, m - 1), ..., (m, 0)} 总共m+1种方式。 所以这题显然易见，就是除最大数以外的组大小累乘。 import java.io.Buffer...

牛客练习赛解题报告

0 点赞评论收藏

分享

2023-09-05 19:11

已编辑

東京大学 golang

牛客小白月赛77 解题报告 | 珂学家 | 反悔堆 + 字符串hash + 二进制递推

前言   整体评价 虽然E题测试数据有误，导致比赛期间非c++语言输入异常，但是瑕不掩瑜。题目质量还是蛮高的，D题设计卡单Hash，还是很用心的，E题这个反悔堆出的也很精彩，F题的官解做法也让人眼前一亮。  A. 小Why的方阵 由于对称性，可以假定改动的值在左上角 x + a[0][1] = a[1][0] + a[1][1] x + a[1][0] = a[0][1] + a[1][1] 恒成立的条件为 a[0][1] == a[1][0] 因此猜测，只要存在一个对角线元素相等，则必然可以构造解 import java.io.BufferedInputStream; import java...

牛客小白月赛解题报告系列

0 点赞评论收藏

分享

2023-09-04 11:01

東京大学 golang

牛客周赛 Round 10 解题报告

牛客周赛 Round 10 解题报告 在牛客博客上https://blog.nowcoder.net/n/78952ae55788456aabe075d175377afeA. 简单的滑窗它本质是数组切分成块枚举左端点，然后寻找最远的右端点然后把新的左端点挪到上一个右端点+1B. 有趣的DFS题非常容易TLE，最好的方法是分组计数，然后dfs，这样天然去重感觉这题还是卡 去重 的方式了C. 数学题典型的凸函数有两种方式，一种是三分模板，另一个种是求导数导数需要注意：t = (sqrt(xy) - v) / x, 有可能为负， 但是时间是非负数因此最小的时间点 t = max( (sqrt(xy)...

0 点赞评论收藏

分享

2024-01-13 10:57

已编辑

東京大学 golang

牛客周赛 Round 10 解题报告 | 珂学家 | 三分模板 + 计数DFS + 回文中心扩展

前言   整体评价 T2真是一个折磨人的小妖精，写了两版DFS，第二版计数DFS才过。T3是三分模板，感觉也可以求导数。T4的数据规模才n=1000，因此中心扩展的当仁不让。  A. 游游的最长稳定子数组 滑窗经典题 从某个左端点出发，按顺序找到最远的右端点 然后把该右端点变成新的左端点，继续寻找直至结束 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(new BufferedInputStrea...

牛客周赛解题报告系列

0 点赞评论收藏

分享

2023-09-01 23:45

已编辑

東京大学 golang

我可以卑微地吐槽下E吗？最后一组数据诡异读取失败

这题的反悔堆，我的思路是对的。因为我赛后，找朋友帮忙把java代码翻译成c++, 然后就过了。在比赛过程中，提交的时候，反馈是 RE，就是执行错误，可能存在数组越界之类。我反复check代码，觉得不可能犯这种低级错误。然后就用二分代码，加try/catch, 试图确定抛异常的点。因为比赛中是隐藏异常栈信息的。确实能定位到输入哪块出问题， 很诡异，比赛结束也是如此反馈。反正累计re/wa了20次反正测试下来，最后一组数据，n=1000000，但是我这边只读到999999个JAVA的输入方式 Scanner sc = new Scanner(new BufferedInputStream(Syst...

ygy0：非常抱歉，确实有一组简单的测试用例少了一个输入，但不影响答案，现在已经更正。

0 点赞评论收藏

分享

2023-08-27 22:00

東京大学 golang

牛客周赛 Round 9 解题报告 | 平均数猜测

题解报告 详细的 链接https://blog.nowcoder.net/n/069bc5218c4e4e5ca615f1af4a91041cA. 因为取模，所以有个小技巧，对x做个偏移，使得index 0，最后结果在偏移回来就行， (x-1)%m+1B. 枚举就行，枚举x的位置，这样 max(变动后值 - 原先的值), 这个位置就是目标位置C. 枚举起点就行，然后线性遍历模拟，取0/1开头的最小代价，贡献思路可能在这里失效 D. 思维题吧，众数一定是n/n-1个， n-1的时候，如何构造呢？要剔除那个倒霉鬼？剩下的n-1又怎么代价最小？+1/-1，其实暗示了平均数，但是这里需要枚举 avg的...

0 点赞评论收藏

分享

2024-01-13 10:57

已编辑

東京大学 golang

牛客周赛 Round 9 解题报告 | 珂学家 | 平均数定律

前言   整体评价 C题只能模拟，好像直接用贡献法不行，如果要搞个O(n)时间复杂度还是挺难的。D题挺有趣的，名义上的众数，本质还是平均数构造，这题不是n个众数，就是n-1个众数。而n-1个众数，如何最小化代价挺费思量。  A. 小美的外卖订单编号 因为涉及取模，所以最好的方式，是index 0，而不是index 1 所以对x先左偏移1位，取模后，在右偏移回来  形象一点就是：(x-1) % mod + 1  import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public stat...

554454545：B题在样例 2 1 1下貌似有问题

牛客周赛解题报告系列

0 点赞评论收藏

分享

2023-08-26 19:44

已编辑

東京大学 golang

牛客练习赛114 解题报告 | 珂学家 | 贪心场 + 期望 + 线性基

前言  只要坚信自己的道路，就无所谓天气是晴是雨。  整体评价 这场还是蛮难的，对我而言。C题写的有点变扭，到是D和F相对容易些。CDF都是基于贪心的解法，不过赛后看到了其他解法。G题属于高阶知识点，会的人觉得简单，不会的人基本没啥思路。  A. 光速签到 贪心，把大的数放在前面。 因为需要是10的倍数，而且允许前置0，所以只要保证至少一个0，就存在解了。 import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public static void main(String[] args)...

牛客练习赛解题报告

0 点赞评论收藏

分享

2023-08-21 01:18

東京大学 golang

牛客周赛 Round 8 解题报告 | 树形dp

本周周赛的题解报告在博客https://blog.nowcoder.net/n/f3d763032fd74a49b42d0dd8bf62011cA. 线性遍历B. 构建前缀和, 然后min(正向距离，总和-正向距离)C. 构造题，构造, 1,n,2,n-1,3,n-2,..... 最大最小交替出现D. 树形DP， 每个节点都有被选中, 未被选中两种状态，蛮典的

0 点赞评论收藏

分享

2024-01-13 10:56

已编辑

東京大学 golang

牛客周赛 Round 8 解题报告 | 珂学家 | 构造 + 树形DP

前言  人工智能究竟能不能拥有和人一样的“爱”。 看完这本书的我觉得，这种爱，人工智能不应该去渴求拥有。  整体评价 原题场吧，开赛前就直言不讳说是来自美团的笔试题。 整体还是简单，D这个树形DP不错，可能有段时间没写树形DP题。  A. 小美的排列询问 简单题，线性遍历即可。 import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(new Buffered...

牛客周赛解题报告系列

0 点赞评论收藏

分享

2023-08-14 22:37

已编辑

東京大学 golang

牛客周赛 Round 7 解题报告 | 状态机DP

牛客周赛 Round 7 解题报告 | 状态机DP博客链接：https://blog.nowcoder.net/n/d572226708f94daaa03f9fe1bbc7f1c0A. 模拟题，把"you"映射为1,2,4, 其他字符映射为0，这样2x2矩阵的或和为7，就是满足的一个解，这样统计更方便B. 状态机DP，0,1代表以0/1结尾的代价，线性遍历一下就可以处理。其实枚举模拟也很快。C. 数学题，额，先找到上下界，然后从不同方向枚举找最大值和最小值，感觉测试数据有些弱，但确实过了。另一方面，这题最大值容易求，可以二分找最小值，如果推导存在思维难度的话。D. 经典的状...

0 点赞评论收藏

分享

2024-01-13 10:55

已编辑

東京大学 golang

牛客周赛 Round 7 解题报告 | 珂学家 | 状态机DP + 数学场

前言  所有他努力长大成人的日子，不过是为了与她相遇。  整体评价 这场C有点考验智商，太难了，最后用了暴力解，挺虚了的，感觉数据弱了。D到是一眼题，套路满满，反而简单，应该是属于状态计数DP。  A. 游游的you矩阵 就是把字符转换为的幂次，这样方便统计.  y -> 1, o -> 2, u -> 4, 其他字符皆为0  这样2x2的矩阵，如果其按或和为7，则为满足矩阵 常规解法 import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public static ...

牛客周赛解题报告系列

0 点赞评论收藏

分享

2023-08-07 00:27

東京大学 golang

牛客周赛 Round 6 解题报告 | 数学场

题解报告，具体见博客https://blog.nowcoder.net/n/5a1544754d174403b6521b38ff850cd3A. 简单模拟题，签到B. 模拟题，考察阅读理解C. 枚举x变量，反解y，求最小(x,y)对，使得绝对值差最小D. 取模K进行分组，然后贪心即可 $ans = max(ans, groups[i] + left(x) / size[i])$E. 数论题 说真的不会，不过按照大神的解法写了一版java。 知乎上的有理数循环节的讨论：https://www.zhihu.com/question/462266812 除了结论外，欧拉函数，枚举因子，快速幂，以及有...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客企业服务