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

2025.10.4训练记录

上午noip模拟

T1

题目关键在于:中奖数字的最后两位必须两两不同。
于是可以把每个后两位的状态看成『一种数』。
依次考虑每种数作为一、二、三等奖对答案造成的贡献。
于是可以 dp,状态为 \(f[i][0/1][0/1][0/1/2/3]\)

看起来很简单但是实际上场上做了一个半小时。
前面想的是贪心,但是一直不知道怎么处理『后两位两两不同』这个性质。
dp 是不太要脑子的。

T2

神秘推式子题。也许没那么神秘。

先考虑暴力的 dp。\(f[i][j][k]\) 表示区间 \([i, j]\),最后的胜者为 \(k\) 的概率。
转移:由于只能将相邻的数合并,所以考虑枚举断点将区间分成两块。
包含 \(k\) 的区间胜者一定是 \(k\),另一半中尝试再枚举胜者 \(p\)
相当于枚举了区间内最后一次战斗是 \({k, p}\) 之间举行的。
复杂度 \(O(n ^ 5)\)
注意到我在考场上没有想到这个转移。
我一直在考虑:第一次战斗后,区间会变成什么样的情况。
然后发现很难用哪个状态去刻画,因为进行几次之后就是一个子序列。
\(f[i][j][k] = \sum f[i][l][p] * f[l + 1][j][k] * calc(k, p) * \frac{1}{j - i} (l < k)\)
\(l \geq k\) 的情况同理。

然后比较好想的一个状态优化是 \(f[i][j][0/1]\) 表示 \([i, j]\) 的最终胜者是 \(i\) / \(j\)
因为你可以在胜者的位置把区间的战斗分成两个部分。
这样子原来的 \(f[i][j][k]\) 就等价于 \(f[i][k][1] * f[k][j][0]\)。转移式子相同。
有人在考场就想到了这个状态,但是因为不会那个暴力的转移并没有什么作用。

剩下的就是奇异优化,考虑交换枚举顺序,将与最内层循环无关的东西提出。
在 dp 过程中处理即可做到 \(O(n^3)\)
这个优化泛用性难道很强吗?

所以之后遇到 dp 优化可以试试看交换循环顺序(?)
之前的计数里面也有类似技巧,好像是一个莫反的题。

T3

一个数据范围的分析,之后巧思枚举判断。
看到题目的时候大概是有一点感觉的,但是后来也没时间想下去。也许是时间分配有问题。
noip 是四个半小时对吧/dk。

T4

一个性质是加入数不会改变前面颜色段的情况。
即:要么前面一个同颜色段长度加一,要么在最后开一个新的颜色段。
第一种情况中,在前面的哪一个颜色段是可以二分的。
所以我们可以得到,每个数在加入序列时,排在这个序列的第几位。
即前 \(i\) 个数中,第 \(i\) 个数在哪个位置。
最后倒过来用数据结构维护位置就可以填完所有的数。

这场确实有点犯唐了,那天早上巨困无比。
归结为借口,因为有些地方想不出来确实感觉不像正常发挥。
掉下 200 分我就能重回 div2,明天明天还有一场 noip 模拟,看我上 200 分。

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

相关文章:

  • st表 + 变形的djs (好题
  • 2025年微信小程序开发:AR/VR与电商的最新案例 - 指南
  • 10.5
  • 在wpf .net 8项目中使用materialDesign 4 以上版本的的注意事项
  • 学习STC51单片机26(芯片为STC89C52RCRC) - 实践
  • 洛谷P14120 题解 - lemon
  • cf41d
  • 33 ACwing 294 Count The Repetitions 题解
  • 电赛电装实习总结
  • 30 ACwing 291 蒙德里安的梦想 题解
  • 21 ACwing 289 环路运输 题解
  • 26 UVA1630 串折叠 Folding 题解
  • 13 ACwing 283 Polygon 题解
  • 12 ACwing 282 石子合并 题解
  • 11 ACwing 281 Coins 题解
  • 某中心科学家荣获多项计算机技术大奖
  • FFT
  • 4 ACwing 274 Mobile Service 题解
  • 3 ACwing 273 Making the Grade 题解
  • 1 ACwing 271 Mr
  • 2 ACwing 272 LCIS 最长公共上升子序列 题解
  • 用 Haxe 实现英文数字验证码识别
  • 出题四
  • 7 2025 07 15 模拟赛题解
  • 使用 OCaml 实现验证码识别
  • 私有云大数据部署:从开发到生产(Docker、K8s、HDFS/Flink on K8s) - 详解
  • 差分约束模板
  • 17 LCA模拟赛1T2 剧院始于演员 题解
  • 3 2025 04 23 模拟赛总结
  • 14 收心赛3 T1 最长不降子序列 题解