10月总结

1002

总览

• T1 在考试时想出来了正解，但是因为调和级数的时间复杂度证明而放弃了（$\operatorname{f}(i)=\sum_{i=1}^{n}\dfrac{1}{i}$ 其实就约等于 $O(\ln{n})$）。

• T2 也是在考试时想出来了正解，但没证明出正确性。

• T3 有点正解思路，但不多，硬控我1h30min。

• T4 读了题，但仅限于读懂了题。

出题人并没有想在第一天毒瘤大家的意思。

出题人认为的题目难度排序大概1≪2≈4<3。

总体来看，本场比赛的100+难度会略高于CSP-S，略低于
NOIP，但是并没有大家想象地那样难度恐怖。

——by 出题人

T1

和正解思路几乎一样。但是考场上花了两个多小时终于思考出了正解但却因为调和级数的证明误当作了 $O(n)$ ，而放弃了正解而使用了一种时间复杂度为 $O(n^n) \sim O(n \times \log(n))$ 的神奇代码获得了 50pts 的嚎成绩。

T2

一上来就想到了正解思路，赛后复盘可能是因为我做过（虽然我自己都不记得我做过）。但是我看 T3 好像更可做+正确性没证，所以先去磕 T3 去了。

T3

全场唯一真坑，看似简单小模拟+容斥，实际细节剧多，情况剧难想，硬控我 T1 50pts + T2 100pts 由此我得到一个非常重要的教训：$\large{\texttt{一定不要因为一道题看起来简单就去做，一定一定要先做有把握的题。}}$

T4

没啥好说的，题目读懂了，暴力都打不出来，只能说一点正解思路都摸不着。看了正解也无话可说，一点也碰不到。

1003

T1

我会暴力！使用 dfs 枚举所有路径依次求值。时间复杂度 $O( (^{n+m−2}_{n−1}) )$，期望得分 30，实际得分 0，死因： freopen("grid2.in","r",stdin)。

考场上思考到了 DP，但是感觉不会转移，赛后看了一下 std，感觉考场上推得出来，但是先去做 T4 了。

T2

我会枚举！枚举四个点依次判断是否是正交矩形，时间复杂度 $O(n^4)$，期望得分 16。

我会优化！枚举左上角和右下角，判断剩下两个点是否存在即可，时间复杂度 $O(n^2)$，期望得分 32。

考虑 $x_i \le 2$ 的情况，即只有两行。那么我们只需要选择两列 $(x,y)$，满足这两列在第一行和第二行都有点。求出第一行和第二行都有点的列数 $m$，输出 $(^{m}_{2})$ 即可。期望得分 40。

考虑 $x_i \le 500$ 的情况，我们可以直接枚举每两行，用上方的方法计算贡献。使用 bitset 求交时间复杂度为 $O(x^{2}_{i}\dfrac{n}{w})$。期望得分 64，实际得分 0，理论得分 92，死因：//define ONLINE。

好消息：这道题出题人数据水了。

坏消息：这道题我又没加 freopen。

正解倒是想得通，但是考场上肯定不能推出来，有这时间不如去打 T1。

教训放最后。

T3

我会枚举！枚举杯子之间的转移关系并模拟，时间复杂度$O(n \times (n−1)^n)$，期望得分16。

我会失之交臂！如果你推了下一个做法中的任意性质，可以写一个优一点的爆搜，期望得分 24。

实际得分 16，性质推出来了，但是解法伪了（这也是我考试时唯一得分的题）。

正解是在 DP 的基础上优化，我在考试的时候想到了 DP，但是因为我太蒻了，所以时间复杂度相较于暴搜没区别，就没写，而且最后的线段树优化我写了也不一定调得出来，有这时间不如写 T1。

T4

推导出了子问题：

有 $n$ 种球，第 $i$ 种球有 $a_i$ 个，每种球是相同的。对于 $m = 1 \sim \sum a_i$求出将这些球放入 $m$ 个不同的盒子中，且每个盒子非空的方案数。

我会 DP！暴力 DP $f_{i,j}$ 为前 $x$ 种球放 $y$ 个盒子的方案数。时间复杂度视实现可能为 $O(D^3)\sim O(D^4)$，结合算法3期望得分 65，实际得分 5，原因：写挂了。

这题没啥说的，二项式定理没学。

总结

$\large{\texttt{一定要检查freopen！！！！！！！！！！！}}$

1004

T1

语文题，一眼秒了，和正解基本没区别。

T2

最亏的一集，先是推式子推出来个大概，然后两个下标搞反了，于是看样例不过就以为贪心思路错了，最后草草打了个暴力交了上去，还把 freopen 打错了，一分没拿。

$\color{red}{\large{\texttt{一定要检查freopen！！！！！！！！！！！}}}$

$\color{red}{\large{\texttt{一定不要因为样例不过就怀疑思路，万一是你写挂了呢。}}}$

T3

题解看不懂，知识点超纲。

T4

考场上就看出了线段树+下传操作做法，但是写挂了，但是造数据的人没卡掉我，但是交到原数据上挂了，总而言之，谁能想到一遍过了大样例还能挂啊。

总览

分数：240pts/160pts

这次考得还行（？），但是还有很大进步空间和很多需要总结的地方，希望下次不要再挂分了。

1005

T1

一时间脑瘫了，竟然推了 1.5h 的式子，最后才发现特殊性质，缝缝补补我的代码也是终于 100pts 了。

exp. 100pts/100pts real.

T2

没时间做了，随眼看了一下，就打了个 $O(nm\log m)$ 的全源最短路上去，也是奔着部分分去的。

exp. 70pts/70pts real.

T3

简单题，其实我已经离正解非常接近了，其实就是要用倍增，但是要用时间换空间，我没换，因为我怕我的大常数写法过不去，所以只能不换。最后不知道为什么全 WA 了，重构一下就 A 了。

exp. 70pts/0pts real.

T4

一眼丁真，鉴定为**数据结构题。思路好想，代码好写，好评。《n=10的大样例》，差评。

exp. 100pts/100pts real.

1013

T1

考试时先把 T1 的暴力打出来就去开其他题了，而看完 T3 后感觉比 本题更有可做性，就先去做 T3 了，但是决策性错误，按理来说应该先做 T1 的。

教训：$\color{red}{\large{\texttt{T1、T2 几乎永远比 T3、T4 可做}}}$

T2

不会，但是在考场上想到了二分图最大匹配（？），很明显这个思路是错误的，但是我当时想赶紧骗分，骗完了赶紧先把所有题给开了，就写了个没有正确性的骗分上去，最后也是成功拿到了 0pts。

T3

思路接近正解，但终归有本质区别。再次重申：T1、T2 永远比 T3、T4 可做，千万以后别舍弃 T1 去做 T3 了，不值得啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊。

T4

不会，骗分都不会。考后发现可以用四项式定理骗分，但是还是有可能推错，有这个时间 T1 早做出来了。

总结

为什么我要先做 T3 啊！

以后一定要先磕 T1、T2，不要看着 T3、T4 可做就跑，分数倍率都一样，不如花更少的时间拿更多的分。

1015

T1

简单贪心，不过 SPJ 和数据好像水了，输出 I AK IOI 都能过。

T2

双向搜索，但是我没想到怎么做，所以只打了暴力，暴力还写挂了，得益于这场比赛的《超大大样例》，我没发现问题，痛失 40pts。以后看到全部分数据范围是部分分的两倍的时候就要考虑双向搜索了，搜索还是不过关。

T3

本身考场上没思路，得分也符合预期，看题解总结了一条我认为对我今后的做题思路应该有重大影响的结论：正解基本都是由部分分改进得来的，观察了最近几天的题，发现确实如此。

T4

又是不看题的一天。它题面里有两个模数，把模 p 的值累加再模 $10^9 + 7$。

以为只有一直模 p 的我：啊？！

最后算出来的答案一直与正确答案模 p 同余，痛失 100pts，我的解法还比 std 更加复杂。

总结

读题！对拍！不要拿到半路就开跑！沉下心来！

总结（前 4 场）

这次出的最大的锅就是 $\color{red}{\large{\texttt{freopen}}}$，前四场比赛我起码因为这个**错误丢了 250pts，还有就是我感觉我离 NOIP 难度的很多题的正解思路都很接近，但是就是不敢去写/写挂了。最后再提一句。

$\color{red}{\large{\texttt{一定要检查freopen！！！！！！！！！！！}}}$

241019 & 250419

时隔刚好 $6$ 个月整，我们又再次考了同一套题，我的总分由原来的 $2+80+0+12=94$ 变为了 $92+80+68+14=254$，涨了 $254-94=160$ 分。

T1

$$2pts \to 92pts$$

观摩了一下第一次考试写的代码，真就一坨。除了知道一个二分答案以外什么都没有了，而且检查的逻辑也有很大的问题，但是起码知道 $l=-1,r=n$，而这一次我直接 $l=0,r=n$，成功挂掉 $8pts$。

防爆零题目，你甚至可以看到 if (edge[i].c <= mid && edge[i + 1].c > mid) 拿 $2pts$。

T2

$$0 \to 68pts$$

打的暴力。基本没有变化，唯一的区别就是现在会了 LCT，想了一下用 LCT 维护似乎可做，于是就想着 LCT 太麻烦了，就打了个暴力走人，实际上可以使用线段树维护，并不需要 LCT 这种高级数据结构。我好像在学习新算法以后就想着新算法了，但是一些用简单算法可以做的题目就被复杂化了，就反而会让得分降低。

T3

$$12pts \to 14pts$$

都是贪心，没什么本质区别，但是世界上应该用 DP 的。

题解需要用的性质我都推出来了，唯一的区别就只是我观察臆想出的单调性，虽然我也不知道我是怎么想出来的，但是确实我脑子一抽就搞了个所谓的性质。

以后一定要证明！！！

T4

$$80pts \to 80pts$$

结果一成不变，但是我这次在考场上想出了完整思路，而且没写出来。

还好我先写了一个暴力。