Logic
向着梦想进发
Logic's Blog

【退役记】2021NOIP-code

这是一篇迟到的 blog,谨以此献给我短暂而美好的 OI 生涯

T1 报数

水但是很可惜
只能说真的很可惜, 考场里我想到了这种做法
但我不知道为什么脑抽以为这个是 $O(n^2)$ 的算法 (其实是 $O(nlogn)$)
然后我果断放弃这种做法......

T2 数列

很可惜, 考场里不知道在想什么
把位数和贡献用参数传入优化就能拿 20pts
再加记忆化就能拿 50pts

正解是4维dp

DFS

记忆化搜索或二维DP

状态表示:

  • $f _ {u,s}$ 表示取 $u$ 个数且形成的数为 $s$
  • 属性 每种方案的权值和

依据最后一个选择划分可得

$$
f _ {u, s} = \sum _ {i = 0} ^ {i \le m} {f _ {u - 1, s - 2 ^ i} \times v[i]}
$$

四维DP

状态表示

  • $f_{i,j,k,p}$ 表示确定了 $S$ 的前 $i-1$ 位,确定了 $a$ 数组中 $j$ 个元素,且 $S$ 的前 $i-1$ 位一共有 $k$ 个 $1$ ,向 $i$ 位进位为 $p$
  • 属性 每种方案的权值和
  • 因为进位是从低到高所以从低位到高位枚举满足 $dp$ 的无后效性

考虑用 $f_{i,j,k,p}$ 转移

  • 设选 $t$ 个 $v[i]$,$t\in [0, n-j]$,相当于对于 $S$ 的第 $i$ 位上贡献了 $t$ 个 $1$
  • 则转移为 $f_{i+1,j+t,k+(t+p\&1), t+p>>1}$,第 $i$ 位即为 $t+p\&1$,向 $i+1$ 进位即为 $t+p>>1$
  • 贡献为 $f_{i,j,k,p} \times v^t[i]\times C_{n-j}^{t}$,即在 $n-j$ 个位置中任选 $t$ 个位置

复杂度 $O(n^3mk)$

起点
$$
f_{0,0,0,0}=1
$$

目标
$$
res=\sum_{k\in[0,K],p\in[0,n>>1]}^{k+popcnt(p)\le K}{f[m+1][n][k][p]}
$$

  • 准确的说 $f_{i,j,k,p}$ 表示的 $S=S_{0..i-1}+(p<<i-1)$,$S_{0..i-1}$ 表示 $S$ 的前 $i-1$ 位,即对应 $k$
  • 如果要确定一个方案则 $i=m+1,j=n,\forall k\in[0,K],\forall p\in[0,n>>1]$
  • 合法性则要满足 $popcnt(S)\le K$,即 $k+popcnt(p)\le K$

T3 方差

这题没得说,我只会暴力

主要思路是:

  • 题目中的操作就是交换差分
  • 猜想差分数组是单峰时方差最小 (看了一圈题解,很少有能严谨证明的,大多都只是猜想, 我自己也证不出来)
  • 考虑 dp
    • 将差分数组排序
    • 再考虑将每一个数放在首还是尾

正解

参考了这篇题解
我尝试推过这个公式, 确实是对的, 推导也比较巧妙, 可以推推看, 但还是不能解释为什么是单峰的

BFS

模拟退火

模拟退火直接72pts了...... 还tm要什么自行车

考虑到单峰性质,可以先随机构造一个单峰的差分数组再退火,可以拿到84pts
这个退火算法当真有些意思

https://cdn.jsdelivr.net/gh/LogicShao/PicBed/img/sanb.png

T4 棋局

神仙题
考场里题面都搞不明白


总结

关于往事

当时真是 至暗时刻 (如果可以这么说的话)
文化课的成绩已经排到 200 名开外了, 化学简直稀烂 (没赋过 90+)
技术也不是很理想。照这样的趋势考个大学都费劲
NOIP 也没有发挥好 (前天晚上稍微晚了一点睡, 大概是 11:30, 进考场不知道为什么就是打不起精神...)

因为 T1 莫名其妙的失误搞崩后(其实有想到,但是。。。。总之最后写了一个 50pts)
T2, T4 都什么都没做出来
(旁边那个后进考场的老哥——这是所谓 NOIP “体验名额”——15分钟就敲好了第一题,还小声说了一句"就这")
(再加上这个老哥敲键盘声音巨响,给我搞得人心惶惶)
T3在考场里自测大样例从 2.2s 调到 1.1s 调了快2h也没有到 1s-
又想到 lry 说 Linux 的 time 会把 cpu 跑满真实测试还会慢一点
当时还有 2h 但是整个人都傻了,去看 T1 有没有做法时已经被思维定势了怎么都想不出来
写 T2 发现写的暴力跑了 1.5s
再看 T4, 发现题目逆天, 可以拿暴力分但很已经几乎不可能了

总之出考场时掂量以下只有 50-60pts 的分数。。。。
当时真的是一句话都说不出来

然后就是不顺心的事情又来到
首先是我在动车上睡觉稍微睡的有多久,醒来就快到了,才想到之前跟家长说 9pm 到黄岩是多么离谱
于是 7pm 时只留我一人在寒冷的火车站等了好久。。。。
第二天我想应当及时止损,于是想早一点到校
结果那天没睡好,到学校又发现没带饭卡只好在学校旁边吃一点,又被我妈数落一翻
还漏看了一条 fc 的消息

再加上 2021scp-s2 前 fc 一句 Logic 你没有机会了 给我心态炸裂
再加上 2021scp-s2 前在面馆里吃到蚊子

只能说非常的累,非常的累
该文 就是在这种情况下写出来的

那段时间是自修室全勤,导致白天精神也不是很好,经常在上课时睡着。。。

关于算法学习

其实当时也没掌握怎么学习算法 或许对于一个零基础开始学习七八个月算法的人来说要求太高?
大多数题目都只会模拟而不知正解,AcWing 上刷了那么多题其实大部分都是对着 y总 的板子抄
很少自己完全想明白,但这也有一部分环境因素的影响罢 虽然我觉得如果一切都归结于环境那么不就什么事都做不成了吗

不过至少有一点是可以肯定的——那就是对算法的热爱

如果让我扪心自问的话,那段时间我一定是全力以赴了


现在想来当时确实是有些幼稚——一个刚刚生长的小苗窥到了一片天地
沉淀了这么久,只觉得当时太过浮躁太过激动了

关于算法学习,灵神 的这期视频或许对你有所帮助

他的这个项目也非常不错

关于退役

其实在我打完 2021csp-s2 时我就想过退役了
就和 lry 一样我一开始也不是为了拿奖来的,只是因为喜欢而已

而当 NOIP 结束,在权衡利弊下,为最终还是放弃了 OI

  • 2022NOIP 结束只剩1个多月准备首考
  • 老师家长的催促
  • 个人能力的不足等等

总之我还是非常感谢这段让我成长的时光的

关于自卑与成长

或许曾经的我很讨厌这些东西,因为他们会触及到我最脆弱的地方
当现在我多少想明白了一些关于自卑的东西

曾经的我或许不会承认,但现在的我不得不说我真的很自卑
在阅读了《被讨厌的勇气》一书后,我邂逅了阿德勒心理学——一门关于人如何获得幸福的心理学或者可以称之为哲学

书中说到自卑情结是每个人都存在的
因为人是少有的心灵成长快于肉体成长的动物
那么自然会产生想做而做不到的事情
自卑由此而来。

书中的学问关乎我的整个人生,而我只是稍作阅读并加以实践

我说不清楚这几年来我的成长,但总之是在前进的

大概这些事情还要我将来细细去想

最后

在暴风雨来临的前夜(无论是 2022 反常的气候,还是我波折的命运),我于繁忙的学业中匆匆写下此文,或许有未能意尽之处,
或许有诸人不认可之处,或许只是胡言乱语,几乎连话都说不清。

至少我还是迈出了脚步,总不至于无路可走。

沉舟侧畔千帆过,病树前头万木春。就用这句话结束这篇博客,继续我的生活罢。

赞赏
本文作者: Logic
本文链接: https://i.needwe.top/2021noip-code/
本文采用 CC BY-NC-SA 4.0 Unported 协议进行许可

发表回复

textsms
account_circle
email

Logic's Blog

【退役记】2021NOIP-code
这是一篇迟到的 blog,谨以此献给我短暂而美好的 OI 生涯
扫描二维码继续阅读
2022-09-14