10.14 ~ 10.20

LBTL / 2024-10-16 / 原文

10.14

上午模拟赛。

但是这场模拟赛原先的题目叫“CSP-S 模拟（难）”
然后“题目不按照难度排序”
而且还直接给了 T4 的初步结论
有一种不祥的预感 🤔

正序开题。
为啥把四道题的题面放在四个 PDF 里啊？

T1 推了会出了结论，鉴定为签到。
然后我还没打完隔壁 HDK 已经写完 T2 开始看 T1 了 😦
不管不管

写完了把小样例全过了，想着测一下大样例，然后
OI 赛制不给大样例的出题人就是若智
又花了半天写了个暴力对拍
然后还没开拍就死一发 😅

突然被告知 T4 是原题，高一那边做过；
所以给我们补了 T5，让我们先写完别的再做 T4；
~~没事，等我打到那再说~~

挂着拍去看 T2
T2 题还没读完就给我 T1 拍出错了
改完之后接着写 T2
写完回头一看又拍出错了 😇

不是我犯天条了这么整？
干脆先不写 T2，改完上一个错就看着它拍；
然后就稳定的每 200 发错一个
没这拍我得死这题上 😅

终于把 T1 弄完了，此时大概 1h。
HDK 写 T2 写那么快，T2 一定是签到吧！

把之前的贪心思路写完了，小样例全过了；
T2 给了大样例，挺好。
把大样例拉下来一测，比答案优秀好多啊 😥

开调。
手造了若干组 Hack 并进行若干调试以后过了所有的手造样例；
再试一次！
比答案劣好多啊 😥

你不过 T2 你过啥题啊
你不过题你打锤子啊

不行我不能再写不出来签了！
写写写；
大样例咋还过不了啊……
……woc 怎么这就只剩 1h 了，不能再拖了啊！

交上 T2，慌乱地去看 T3。
这什么构式题面，什么叫

对于任何一个点，如果属于土地内部或是边界，则不会有积水，否则如果一个点的左右都存在相同高度的属于土地的点，这个点就会产生积水。

你 tm 说啥呢一个点不属于土地内部还不属于边界那它还能在哪
你庄园排水这么好呢
海绵城市十八 😇

然后发现其实是这样

byd 他非要把一个很简单的东西说的这么复杂吗

感觉是个 DP，然后推了半天没推出来状态设计；
你怎么知道我只会打搜

看 T5。
艹咋又是计数啊，感觉很可以 DP，但是不会。
你怎么知道我还是只会打搜

还剩 0.5h。干啥呢？
把 T4 写了吧；
算了一下样例之后
“我好像找到规律了！”
然后写了个又不像 DP 又不像记搜又不像数学的东西上去；
答案咋这大啊 😦

发现这个做法会有一堆重复计算的状态我还不会去重；
嗯？你怎么知道______________

rk1。
不是我打成这个史样了还能在这个位置？
~~虽然我打了 T4 给我加了 10 Pts 吧但他又没说不让我打~~

T1 签到是情理之中的；
T2 不知道为啥我直接贪的做法拿了 32 Pts；
T3 暴力挂了 4 Pts 😅
T4……T4。其实不应该打的。我谢罪。
T5 倒是没挂，但是感觉 30 甚至 50 真的很可做啊。

下午讲题，给我一种每题都很不可改的错觉（
恼了我现在咋啥都不会就会暴力 😡

晚上把本来要讲的数学专题改成搜索专题了
然而我们都没咋做所以先不讲让我们先做，等之后看回放；
这下可以合情合理地打搜了 🥰

感觉 meet in the middle 你要是告诉我是我肯定会；
但是随便来一道题看见 $n \le 40$ 我还真不一定想得出来 🤔
~~万一又是什么 $O(n^6)$ 的超级 DP 呢~~

10.15

上午模拟赛。

所以能不能不要再给电脑限速了
下个下发文件花十分钟我还做个集贸啊 😅

开题。T1 是……
被喵喵叫回去整改内务了 😥
通报的是“整个宿舍床下都很乱”
但是回去之后感觉挺干净的
怎么会是呢 🤔

T1 感觉像最小生成树，胡了一个感觉不太对的做法把所有样例都跑过了，然后还过拍了（
然后就扔着没管。

T2 想了半天没啥好思路，写了一个 set 维护前驱后继每次插入之后动态更新的东西；
感觉不仅正确性没有保证时间复杂度也不对
但是它跑过小样例了诶

测测大的！
……我答案咋全是 1 和 0 😦
（爆改 1h 代码）
好耶，这下大样例过了！
然后把小样例搞下来想做个 Hack 数据，发现没啥必要；
因为我的代码过不了小样例了 😅

又调了 0.5h 之后得到了一个能过大小样例的代码；
但我已经不想考虑它的正确性了
~~能骗多少是多少吧~~

开 T3。一眼了一个 $O(n^2)$ 的做法，然后写完发现是 $O(n^3)$；
来都来了测下大样例吧；
然后在我的神奇写法 + 关闭同步流的共同作用下
那个答案不是一个一个出
而是一次出一堆然后等半天
就好像
你既便秘又窜稀的感觉 😅

看它跑的时候把 $O(n^2 \log n)$ 的做法想出来了
还挺好打，话说为啥给这个这么多分 🤔

看了一眼 T4 发现只会打搜
然后把搜打完之后发现可以记忆化
这样就是 $O(n^4)$ 能拿 24Pts 了 🥰

剩下的就一点不会了。

绑包了。
增加一条：OI 赛制绑包的出题人也都是若智

T1 是签。

T2 因为绑包了所以一分没得。
Fun Fact：原来的代码有 47Pts，然后自己想了个 Hack，改掉自己的 Hack 之后分数增加了 -47Pts 🙃

T3 $n^2 \log n$ 的 70Pts 是大众分，打出这部分的人比过 T1 的还多；
所以还是想问为啥给 70Pts 的大众分啊

T4 看题解莫名感觉挺可做……？

下午有体育课；
出去打羽毛球，然后好像要举行篮球比赛，所以不让自己打球，统一看比赛；
~~我能受得了这气~~
于是拿着拍回到了教学楼前面打
不过说回来那块挺适合打球的
下次体育课考虑一下 🤔

改题。
看了半天题解发现自己还是一点不会
关键是
虽然是同一个部分分，但我跟题解想的完全不一样

T4：

题解的 $O(n^4)$ 做法：
设 $f_{i,j}$ 为考虑到第 $j$ 个人，$i \sim j$ 为一个队伍的方案数；
设 $g_{i,j}$ 表示从后向前考虑到第 $i$ 个人，$i \sim j$ 为一个队伍的方案数；
这样对于任意一个 $i$，都可以用左右两边的 $f$ 和 $g$ 算出方案数；
复杂度 $O(n^4)$。

我的 $O(n^4)$ 做法：
先进行一遍记搜算出总方案数 $tot$，对于每个 $i$ 做一遍记搜算出在不选 $i$ 的情况下的方案数，两者作差即可；
复杂度 $O(n^4)$