5月31日华为OD机考 | 二星题真题解析

题目大意

n 个魔法石围成环形,能量可正可负。选一段连续石子(可跨首尾),要求总和能被 k 整除,求最大总和,无满足条件则输出 0。

数据范围:\(n\le 2\times 10^5,k\le 1000\)

核心考点

环形数组 + 前缀和 + 同余定理 + 哈希表 + 滑动窗口

解题难点

  1. 环形可跨首尾,普通线性解法不行
  2. 有负数,模运算容易出错
  3. 数据量大,暴力必超时,需线性复杂度

解题思路

  1. 环形转线性:数组拼接自身变 2n 长度,只取长度不超过 n 的子数组,避免重复选元素。
  2. 同余原理\(pre[j]-pre[i]\) 能被 k 整除 \(\iff pre[j]\%k = pre[i]\%k\)
  3. 负数取模修正mod = (pre % k + k) % k,保证余数在 0~k-1。
  4. 哈希表优化:记录每个余数最早最小前缀和,同余数用当前前缀和减最小值,更新最大答案。

易错点

  1. 没控制子数组长度≤n
  2. 负数未做模修正
  3. 哈希表存最大前缀和而非最小,得不到最优解
  4. 无合法情况未返回 0

备考小结

经典模板题:环形数组翻倍拼接、整除问题用前缀和同余匹配、负数固定模修正公式,记住套路可直接套用考场同类题。

#华为OD##华为od##刷题##程序员##华为od机考#
全部评论

相关推荐

05-29 13:25
门头沟学院 Java
努力勤奋的马洛格已躺...:没有实习就找不到实习
点赞 评论 收藏
分享
一、机位调试(双机位监考!第一机位、第二机位都一样重要)* 第一机位设备调试(打开电脑摄像头,拍摄调试;共享屏幕录制)1、要求:第一机位需要完整拍摄全脸正脸,否则成绩无效,半年内无二次机考机会2、易出现的问题及解决方法:①第一机位摄像头异常——如果不是硬件问题的话一般是有其他软件和牛客客户端有冲突②第一机位没有拍到全脸——考前调试好第一机位,完整拍摄全脸正脸* 第二机位调试(手机或者iPad扫描二维码,开启摄像头,如第二机位摆放不符合要求,则成绩作废,无二次机考机会)1、要求(见p1):露出上半身,且需要完整看到双手、键盘、以及电脑屏幕(手机支架:横屏拍摄、一臂距离、电脑屏幕微微倾斜)2、易出现的问题及解决方法(第二机位出问题不会提醒,所以一般都是第二机位出问题,要特别注意):①第二机位不规范,例如没拍到屏幕、没拍到键盘、没拍到人的半身——考前调试好第二机位,一定要将电脑屏幕、键盘、考生的上半身和双手都要拍进去②第二机位拍摄图片较少(一般是第二机位断连了一段时间,无法过筛)——考试时随时关注第二机位情况,出现问题及时解决③第二机位熄屏——开启常亮④第二机位被其他应用程序打断录像(例如电话)——开启飞行模式⑤第二机位没电——持续充电二、考试注意事项(可以在系统里看到详细考前须知)1.请使用最新版chrome浏览器作答(72 版本以上) ,考试需开启摄像头,请确保电脑带有摄像头。2.考生只能在笔试页面在线编写和调试代码,手机监控、电脑摄像头都要打开,考试过程中不要故意取消监控。3.考试答题时间150分钟。4.考试共3道题,可从任一部分(一星题或二星题)开始作答。进入考试界面后,每进入一题型均有输入输出规范例题供参考,例题学习时间计入考试时间。一二星题目均可随意切换顺序作答,就算有其中一题暂时做不出来也可以先提交,继续完成其他题型,后续回来重新修改答案。5.程序开发:不要紧张,将工具调整为最合适的宽度(当鼠标悬停在下图红框处鼠标变为“*”时直接拖拽左侧的文本框即可,也可点击右上角的全屏,进行全屏编码),保证编码舒适性。(见p2)6.程序调试:当代码完成一部分时,如需调试,请点击自测运行。自测输出框可以拉升,方便查询输出及错误信息,根据输出及错误信息调整代码即可。(见p3)7. 提交作答:程序基本开发完成后记得点击右下角“保存提交”按钮,否则答案不作保存,不限制提交运行次数(以提交中最高得分计分),调试完成点击左下角【提交本题型】按钮(见p4)。所有题型均完成作答后,点击【我要交卷】(见p5)。
点赞 评论 收藏
分享
评论
3
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务