当前位置: 首页 > news >正文

牛客119232 牛客2025秋季算法编程训练联赛1-提升组 游记

省流

打了大约 \(90min\) 离场,\(4t\),整体题目较水。

10.15

内含剧透,请vp后再来。

不是题解!!!!!!!

赛前

晚上没吃饭,为了吃饭知道不会打的时间特别长。看到题目是寒假的题目其实比较期待,因为感觉寒假赛的质量其实还可以。

赛时

先开 A 题,题目给了一个 \(n * m\) 的矩阵,要求选择三个格点,使围成的三角形面积为 \(1\),问有多少种选法。我一开始不知道怎么回事把面积为一的三角形当成直角边为 \(1\) 的了,分别算了横向长度为 \(1\) 找纵向所有点和纵向长度为 \(1\) 然后去重,但答案肯定不对。
于是我决定直接看 B 题。题目给了一个 \(01\) 串,可以把至多 \(k\) 个字符反转,问最长的同字符串为多长。我一开始想的是二分答案肯定可以做,于是二分长度,然后统计这一段长度的 \(0\)\(1\) 数量,如果较小的那个小于等于 \(k\) 这段长度就可以选到。不过写完后发现其实并不用二分,直接双指针就可以了。不过复杂度仍旧足够,\(18min\) 通过 B 题。
然后我回去看 A 题,但仍旧没有跳出一开始的错误,没什么有用的进展,只好再去看 C。
C 题给了一个字符串,然后可以选择抠出一个连续子串为 \(nico\)\(niconi\)\(niconiconi\),可以分别增加 \(a\)\(b\)\(c\) 点价值。问这个字符串最大价值为多少。注意到要搜索的串很小,所以对于每个位置作为开头去搜是否接下来是这个串,然后 \(dp\) 即可,\(42min\) 通过。
接着回去看 A 题,我终于发现需要的三角形应该是 \(1 * 2\) 的,然后想到可能会出现斜着的根号之类的东西,于是我就路径依赖直接去看了 D。
D 题给了一颗树,树上的点有黑色或白色。问不同的恰好经过一个黑点的路径有多少个。我一眼看出树形 \(DP\) 秒了,只用去存每个节点作为根下面有多少点恰经过一个黑点和没有经过黑点,然后再从上往下 \(DP\) 一次,每次计算这个点作为根节点时,某个子节点下面的点和其他子节点的点连接有多少个,然后再去算每个子节点内部的。写完交了挂了一发,发现是父节点的一个子节点找过别的子节点后,必须要删掉父节点记录的这个子节点的部分,因为否则等下再计算前面的子节点的贡献就重复了。同时也想到了并查集的做法,就是把白色节点缩到一起,但感觉写着比 \(DP\) 麻烦很多就没管。
然后按照最开始的思路写了一下 A 题,直接就过了。因为斜着的三角形的斜边就是直的了,所以去算横着和竖着分别长度为一和二再去重就可以了。
看了 E 题,题目是给了一个初始点和别的很多点,保证点都不在坐标轴上。然后要求在坐标轴上放一个木板,然后初始点到别的点的连线如果被木板截断了就不能达到。要求最多达到 \(k\) 个点,问木板最长多长。我口胡了一下,分别把在初始点 \(x\) 轴和 \(y\) 轴对面的点拿出来,然后把这些点和坐标轴相交的点标出来,然后跑双指针就行了。然后我就去吃饭,比赛结束了。

赛后

回来实现了一下几分钟就一发过了。
题目质量有点低,下周可能不打了。

2025年10月15日

http://www.hskmm.com/?act=detail&tid=31928

相关文章:

  • BroadcastChannel跨页签通信复盘总结
  • 02020510 EF Core高级10-构建动态表达式树、不推荐动态构建表达式树、动态构建IQuerable、动态构建字符串
  • 02020601 Web API01-顶级语句、全局using指令、可空类型、record类型(自动重写ToString、Equals)、init和private属性
  • OI 生涯回忆录
  • libaom 在ubuntu 上用鸿蒙OHOS编译
  • Aexlet-VGG2
  • 《膜拜!适合新手入门的卷积神经网络原理详解教程》读书报告
  • 科学与社会研讨课笔记
  • p66 实训2
  • 公众号排版用什么好?一次技术视角的系统拆解:效率、兼容与智能协同
  • Linux系统下对拍
  • 重新定义网络安全职业:从解决问题的角度出发
  • 新学期每日总结(第9天)
  • 2025“钉耙编程”中国大学生算法设计暑期联赛(5)
  • 斑马日记2025.10.15
  • 数据库查询通信开销降低97%的技术方案
  • 人生的底色
  • 差分操作正确性证明
  • json请求字符串格式化或使用转义字符
  • Rokid Glasses语音交互特性分析和复刻“乐奇” 唤醒词的方案简述
  • C++_设计模式
  • CF2143D2
  • 结果(Results)和结论 (Conclusion)的联系与区别
  • 【训练技巧】PyTorch多卡训练模型DistributedDataParallel和DataParallel设置方法详解及分布式训练命令解释 - 实践
  • 软件工程学习日志2025.10.15
  • newDay11
  • 向下填充(间断性)
  • 20251015
  • java date 初始化指定时分秒及比较日期大小
  • 轻量级ChatGPT克隆版nanochat技术解析