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

前言 整体评价 虽然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...

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

前言 整体评价 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 Buff...

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

题解报告 详细的 链接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...

前言 整体评价 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 { publi...

前言 只要坚信自己的道路，就无所谓天气是晴是雨。 整体评价 这场还是蛮难的，对我而言。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[]...

本周周赛的题解报告在博客https://blog.nowcoder.net/n/f3d763032fd74a49b42d0dd8bf62011cA. 线性遍历B. 构建前缀和, 然后min(正向距离，总和-正向距离)C. 构造题，构造, 1,n,2,n-1,3,n-2,..... 最大最小交替出现D. 树形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 Scanne...

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

前言 所有他努力长大成人的日子，不过是为了与她相遇。 整体评价 这场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 s...

题解报告，具体见博客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 除了结论外，欧拉函数，...

前言 一切都是命运的安排。 整体评价 这场整体感觉有点简单，D题感觉不错，E题应该是超纲了。整场还是偏数学，个人还是喜欢Round 4/Round 5. A. 游游的数字圈 简单模拟题 0,6,9对应一个圆圈 8对应2个圆圈 import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(new BufferedInputStr...