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

ICPC2022沈阳 游记(VP)

省流

中期艰难挂机,最后勉强四题仅有铜中。

10.21

内含剧透,请vp后再来。

不是题解!!!!!!!

赛前

点外卖没给一次性筷子,飞奔到食堂获取圣遗物然后 \(4min22s\) 速通结块了的兰州拉面。但还是迟到了。

赛时

开始看题的时候,队友已经吃了两发罚时 \(8min\) 通过签到了,此时正在做 C,我就去简单看看榜上其他的题目。
看了一下当时有人通过的题目,感觉都没什么头绪,于是看他们似乎卡住的 C。C 题给了一个长度为 \(n \leq 5000\) 的序列和一个 \(d\),要求选择一个区间 \((l,r)\),使 \(r - l \leq d\)。然后把所有小于 \(l\) 的数变成 \(l\),大于 \(r\) 的数变成 \(r\),求变化后最大的 \(\sum_{i}^{n-1}\mathrm{abs}(a[i]-a[i-1])\)。简和我说他们已经发现了区间长度肯定取到 \(d\),然后我获得一个直觉,只有序列中的点需要作为区间上的点,因为每次区间包括不同的数都只会在遇到一个值时才会变。我讲了只后他们觉得很对,叶神直接上机开码。途中我说了一声保险起见要加一个加减一处的判断,不过叶神应该是自己有正确的想法,没听,结果挂了,超时。我们怀疑是 python 的锅,于是让他 c++ 重新写,结果 wa on \(5\)。我说你试一下加上加减一,结果交上去 wa on \(1\),我看了一眼发现是遍历时多遍历一个超出了范围,改了之后 wa on \(12\)。于是我上机把他的 \(ans\) 赋初始值,然后增加了加减 \(d\) 的情况,终于过了。
然后我看 L,我简单看了一下关键词发现大概率是模拟,但数据范围不像。结果一直在思考怎么搞,最后发现一个条件没看到,看到后就是模拟。于是转述给叶神,叶神上机开码。
然后我去和简一起看 F,是一道构造题。给一个 \(n * m\)\(01\) 矩阵,对于其中的某个子矩阵,如果全部数都相同则为纯矩阵,否则为混矩阵。要求构造一个矩阵使所有子矩阵中纯矩阵与混矩阵数量相等。我来的时候简告诉我算出总矩阵个数是 \(\frac{n \times (n + 1) \times m \times (m+1)}{4}\)。然后我想到单独考虑每一列,如果第二列和第一列完全相反,那么第二列就不会影响第一列的纯矩阵的个数。这样就可以在确定每一列应该有的纯矩阵个数之后构造出一整个矩阵。然后简指出每列如果这样要考虑除以 \(m\) 后多出来的 \(m+1\),于是他想到只要每一列和第一列相同就行了,最后就会多一层 \(m + 1\)。至于不可能构造的情况就是当一开始总矩阵个数是奇数的时候。
然后叶的 L 挂了,我找了一会发现是他数组越界了,修改后 TLE。此时简上机码很快过了 F,我优化常数,没过 CF 的,但交到 QOJ 上通过了,此时剩半个小时,A 题显然很麻烦,我们就结束了。

赛后

L TLE 的原因我认为是叶神实现 dfs 的时候每次都传入了完整的数组,实际上数组是可以存在全局的,这样常数会好很多。而且我们也打算以后都挂 O3 优化交题。
C 题挂掉的原因是叶神只写了 \(l\) 作为 \(a[i]\) 的情况,而我一开始想的是 \(a[i]\) 作为每个 \(l\)\(r\),而我查的时候忘记了,后来乱凑的时候 \(l = a[i] + d\) 就等于了缺少的情况,于是通过了。
这把感觉最主要问题还是我长期挂机,L 题应该更早的给出结论只用暴力 dfs,而我花了太多时间去证明状态的数量,应该大胆去做。这几场沈阳感觉都是要大胆猜测小心求证的场次,感觉风格比较明显。其实我也不是特别擅长这种很数学的场次,希望能有个好结果吧。

2025年9月24日

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

相关文章:

  • 大数据分析基础及应用案例:第四周学习报告——线性回归模型
  • 「LG7446-rfplca」题解
  • 图论刷题记录
  • 「LG6596-How Many of Them」题解
  • 骗我呢
  • 手写体识别
  • 你好,我是肆闲:C语言的学习,成长与分享旅程
  • AGC 合集 1.0
  • 20231302邱之钊密码系统设计实验一第二
  • 深入BERT内核:用数学解密掩码语言模型的工作原理
  • ZR 2025 NOIP 二十连测 Day 6
  • 20251021
  • [论文笔记] Precision-Guided Context Sensitivity for Pointer Analysis
  • 英语_备忘_疑难
  • 数学题刷题记录(数学、数论、组合数学)
  • 朋友圈文案不会写?这个AI指令可能帮得上忙
  • 「JOISC2020-掃除」题解
  • 结对作业
  • CF简单构造小计
  • 深入认识ClassLoader - 一次投产失败的复盘
  • python 包来源镜像
  • CSharp基础复习-1
  • Linux7种文件类型
  • 米理 课程描述/学习计划/Study program
  • 2025年线路调压器厂家推荐榜:10kv线路调压器/单相线路调压器/三相线路调压器/助力电网稳定运行,优选品牌指南
  • Day15
  • 2025 智能/商超照明/灯具/灯光/源头厂家推荐榜:上海富明阳凭分区域光效领跑,生鲜 / 百货场景适配优选
  • 2025 艺考文化课推荐榜:济南震华学校 5 星领跑,全阶段体系适配基础补弱到高分冲刺
  • 2025 广州人力资源/派遣/劳务外包/人事代理/推荐榜:精典人才凭派遣合规 + 全场景适配领跑,企业用工优选
  • 2025 变电站厂家推荐榜最新资讯:撬装变电站/移动车载变电站/预制舱式变电站/移动变电站/预装式变电站/聚焦智能适配与可靠服务,这家企业成优选​