清北夏令营前集训日记

Author Avatar
WildRage 5月 16, 2018
  • 在其它设备中阅读本文章

2018-5-16

才发现今天距离我开坑 APIO&&CTSC集训日记 刚好一个月。
上午考试
上来先通读了一边题目, 发现$T2$好像是原题, 然后简单的想了一下$T1$和$T3$,发现没有$T2$好做。
于是先打$T2$。 半个小时打完了$T2$。
之后发现$T3$的$40$分暴力好像还是比较好打。然后先打了一个$O(2^{n}nL)$的, 然后写了一个暴力和他拍打。
完这些之后想了一下$T3$的正解, 发现我并不会把复杂度降到指数以下, 这时已经9点半了。
最后去写$T1$。 可能我的打法比较傻, 暴力打起来并不是很简单,用了一个多小时的时间才把暴力调出来。
然后想到了一个线段树的乱搞做法,然后就开始搞, 结果到最后也没调出来。
没有挂分, 只是$T1$暴力用的时间有点多, 导致没有拿到$T1$的高分暴力。
下午改完题, 看了一下清华校赛的题, 把考场上想做但是没有做出来的题看了一下, 发现正解很简单,还是太弱了。

2018-5-17

今天是ACM
上来先通读了题目。花了不到$20$分钟就看完了题而且对每个题的难度有了一个初步的评估。
$D$题一定是最先做的, 可以看出来这是一道签到题。只要一个简单的$Hash$就能解决。在开场半小时就切出了这道题。
看有人$A$掉了$C$题, 虽然感觉是数据有问题但还是去做了, 开始打, 打到一半发现重测了,这时只有一个人过了, 想了一种新的做法, 开始重新打, 打完这种做法之后感觉过不了, 先没有交。
看了一下其他的题, 看了一圈之后感觉E题和G题稍微有点思路。
然后上了个厕所, 发现C题可以优化到$ O(n\ln(n))$ 先交了一发暴力, 发现真的过不了, 改正解, 交上去发现$WA$了, 又改了改, 还是$WA$, 突然发现要输出 Case #x: 加上就过了。
之后去打$G$, 先有梦想的打了一个网络流, 交上去果然$T$了, 接下来打我心目中的正解, 打到一半发现好像不是那没么好打, 看了一下时间,和我接下来要写的代码量, 果断的弃了这道题。
到考试结束也没想出其他题。

下午发现好像$E$最可改(虽然事实证明这是假的)。 改了一下午还是没过, 卡常啊。。。。。
晚上又优化了一波常数才过, 然后改了 $F$。 还想改 $G$, 不过还没改。

2018-5-18

考试
上来先看了一边题, 然后发现都不怎么会, 看出来$T2$是一道原题,但是原题的数据范围在这道题中只有$30$分。
先打了一个$30$分, 然后看$T1$和$T3$, 想了想, 并没有想出来, 先打了$T3$, $T1$ 两个有梦想的暴力, 然后并没有分。
尝试去想正解, 无果, 看到$T3$ 的数据范围是$10^{7}$, 感觉很慌, 还是没想出正解。
下来发现$T2$的$30$分并没有拿到, 被卡了常数, 卡了好久才过, $T3$是最可做的, 我没看出了他是一颗树。
改题
T3很好改。
T2打出了一个DFS的打法过了。
T1最不可改, 还没有改出来。

2018-5-20

昨天沉迷改题无法自拔。
今天考试
上来先看了一遍题, 发现都没有什么思路。
发现T3是一道提答, 然后先玩了一会儿提答, 把前4个点跑了出来。
然后回头看T1打了一个20分的DP, 然而并不会优化了。
去看T2, 转换为图论, 好像是一个子完全图类似的东西。
然而并不会了。
在回头看T3跑了一下5~8, 又得了一点分。
也就拿到这么多分了。
不过今天的题还是比较好改的。

2018-5-21

今天把PKUWC的题做了一下。
下午考了一个学考, 晚上回来继续做题, 然后背了一会儿政治, 一天就这样过去了。

2018-5-23

这两天没考试, 就没怎么写。
今天做了不少UOJ的题, 虽然都不是什么难题, 但是锻炼一下思维么。
今天终于把旷野大计算过了, 非常开心。

2018-5-24

今天IOI赛制。
上来先看T1, 第一眼以为是四维偏序, 打了个 CDQ+BIT+Seg_Tree , 然后发现样例不对, 再一看题, 发现其实是三维偏序, 把 Seg_Tree 删掉然后测大样例死活不对, 浪费了我好长时间, 最后发现大样例是错的。
然后打了一个$T3$的暴力, 打了一个T2的暴力, 然后打了T3的乱搞, T3骗了不少分。

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本文链接:https://blog.wildrage.xyz/2018/05/16/151/