2019.4 余姚中学 被吊打记

作者: wjyyy 分类: 记录篇 发布时间: 2019-04-17 21:53

点击量:149

(不好意思标题有点不恰当别人貌似不屑于吊打我)

Day -1

第一次坐软卧,感觉空间宽敞,设施也比较新。当然是多交钱了的

Day 0

早上 8 点到了余姚站,坐了十几分钟公交车到宾馆。误判了地图的比例尺所以本来在公交站台后面的酒店找了半天。

去的还是比较早的,好在刚有人退房,就住下了。在房间里充电到 9 点下去吃了早饭,顺便走到了学校门口,并沿路踩点了吃饭的地方。

然后基本上就在睡觉了。

下午 xls 过来想拼房,但是被迷迷糊糊的 Dew 拒绝了(成功甩锅。

晚上随便吃了点。本来买了「小猪佩奇注心饼干」打算 4 天吃 10 包的但是貌似第一天就吃了 4 包呢???

FWT 接着看没怎么看进去,看来不能在床上学习。

Day 1

正常操作,8:00-13:00 考试。

现在拿 SYZOJ 当考试评测机已经很普遍了吗?虽然评测速度还是要参考硬件,而且我还是很享受光标在 pdf 上选来选去的那个感觉…吧

开场看 T1,实际上是随机开题。T1 是给定一个无向图,给每条边赋一个方向,求这 $2^m$ 种方案中 DAG 的个数。

想了很有一段时间发现只会 10pts 的 $2^m$ 枚举…在纸上写了 T1 $O(2^m\cdot n)\ 10’$。

枚举+tarjan 应该挺好写。先扔了开 T2。

T2 如果枚举全排列的话是 $O(n!)$,$n=20$ 貌似跑不过去。于是准备 meet-in-middle,但是发现虽然上界很松但是状态数还是 $O(2^n)$ 级别的,信仰它能跑过去。

码码码,发现上面还有一维..好像是 $O(n^2\cdot 2^n)$,$n=22$ 的点就跑不过去了啊

然后又调了很久发现还有一堆锅。

准备打 $s_i=0$ 的部分分,考虑先把 $n\le 20$ 的表打出来,打到 $n=11$ 时发现没什么规律,扔了。然后顺手跑了一波 $n=20$,结果要用 $2 \mathrm s$。大力优化循环+判断卡到了 $0.6\mathrm s$ 就没管了。

到此感觉前两题都是计数 with $1000000007$ 十分毒瘤。

开 T3。怎么又是排列啊…今天两计数两排列好像都没怎么做过题啊..

然后打了个贪心直到对拍…才发现自己的错误。毕竟猜贪心这东西凭运气多一点吧。

但是最低档部分分还是 $n\le 20$,仍然没想到比 $O(n!)$ 更优的做法。而且没绑包,于是交上去就没管了。

摸了会鱼发现电脑上并没有扫雷?而且网很慢。

最后随便检查了一下文件输入输出就差不多了。

估分 $10+30+0\sim 100=40\sim 140$(当然那个波浪线当作左倾的吧 XD

结束之后发现是 $10+20+10=40$。和估分差得不远

T2 莫名 $n=20$ 挂了,结果听别人说才想起来这题是 $500\mathrm{ms}$…

$600\mathrm{ms}$ 扔了是梁静茹给的勇气吗!!!register 啥的还没加呢..

不过还好,没挂多少,T3 送了 $10$ 分,应该是规模小了。

中午吃了什么什么鱼,吨吨吨了三碗汤泡饭。

Dew 告诉我 T3 可以二分图顿时产生了熟悉的愧疚感——见 CF1139E 题解,并表示了 Dinic 优化连边+未知神操作可以艹掉这题orz。

然后去面基?纪中的宋老师增加了一点信心,并对后来的日程也有了一些极其微小的打算。

下午讲题貌似仍然一脸不可做,会了多一点的部分分,感觉还是有收获的,当然题题容斥的话会有点难受。

搬着凳子坐在教室的左上角,T3 正解大概也不是流。

之后是杂题选讲,或许是一些国外题目 USACO/POI/ROI/CF Gym 的搬运。有些题目会有点卡科技,但是还有一些题目思维比较重要然后才卡科技

有一道三进制 mex 的题猜测是多项式,再根据 $k\le 12$ 猜了复杂度 $4^k\cdot k$,大概是 $2\times 10^8$,然后给奶中了 ppt 上给出的复杂度。实际上会有大概 $3^n$ 的“平移进制位”做法,但是都好神啊。

晚上搬了一会题,一开始准备从内网 OJ 导入 GuOJ,但是出了点问题以为需要外网。后来才知道是 GuOJ 临时挂了。

22:35 有场 Div.3,感觉不是很影响睡眠+Unr 就打了。不过因为 Unr 打的也不是很认真,1h 才过掉 5 题。FG 还是有些难度的。

这时看见 ACoder 只写了 G,感觉这个策略不错。毕竟用 1h 时间刷 Div.3 A-E 五道难度不大的题除了对手速的训练以外并没有别的作用,况且 OI 中手速快也并没有特别大的增益。

Unr 场除了玩得开心还要对自己有所提升。

貌似写过的题很容易忘,当然如果考试进入状态或者做写过的题的时候进入状态估计回想起来会容易很多。

Day 2

前一天睡的有一点点晚,不过只困了一会。阳光明媚的春天怎么能犯困呢

吃了买好的面包就差不多过去了。前一天晚上疑似坏了的 OJ 能上了,Dew 重测之后就有了 80,被吊打一倍了2333。

开题发现有 4 道,前面两道题目一样,是因为 Subtask 需要的时限不同而 SYZOJ 目前并没有分包改时限的功能,分别放了 40 和 60 分。

所以还是顺着看 T1。给出 $m$ 棵一模一样的树,每个点有一个不同的颜色,有 $q$ 次操作,每次可以对区间 $[l,r]$ 中的每棵树“缩”一条链变成一个点。

强势缩点的话是 $O(nmq\log n)$ 的,只能过 10 分。抱着之后可能会用到对拍,就当时打了。不过打完是 10:00,耗时有点长。然后就直接点了 T3,忘记写暴力的初心了。

T3 是个类似区间 DP 的东西,用区间 DP,对于 $q$ 个询问,每个可以 $O(n^2)$ 求出解。仍然是 10 分。但是算了一下上界复杂度在 $2.4\times 10^8$,$3\mathrm s$ 的限制可以卡一卡。最终还是花了 $3.9\mathrm s$,不是很稳。

最后看的 T2,一开始感觉每个进制分别维护已经遍历过的和还没遍历的,貌似需要树状数组。后来发现前缀和预处理一下就可以了。但是还是调了很久,甚至把数据写在纸上调试,感觉有些得不偿失(貌似没有失去什么)。还好找到了“忘写乘法”的错误。

并没有想到更优的解法。感觉比前一天打的还要不好。

中午又吃了 KFC,大概放松了那么一点点。

xht37 跟我说 T3 实际上可以 $O(n^2)$ 倒着做所有情况,然后 $O(1)$ 用 $f[u][u]$ 回答所有询问,这样就可以过掉 30 分。

Dew 表示 T2 是个类欧,应该不可改;并在 T1 YY 出了 $O(n\log^3n)$ 的做法然而好像没调出来。

下午听题,T1 是个扫描线+LCT,听上去极其煞笔,应该可改,估计得先复习 LCT。

T2 类欧,套上原根会简单很多,然而不知道式子为什么要那样推。

T3 据说送分题,简单数据结构貌似就可以解决。

下午讲了几个有意思的题,跟着思考了一下,但是讲的时候很容易掉线。希望之后能多听一会,也许可以听懂。

好像有一些题是把状态放到平面上然后找斜率或者位置的性质,感觉可能是一种做题的方向。

还有一些题是对算法的理解。会把一些基础算法的步骤进行一些变形,然后适应到各种题上去。

虽然没有打挂什么题,但是还是很难受。看到自己每个题都只会最低档暴力有种被扼住喉咙的无力感。

打完暴力总是会忘记为什么要打暴力,以为打完暴力这题就结束了。这种心态要尽量调整回来,并相信自己有实力拿到更高等的部分分。

然后是建模。虽然题目描述是这样,并且可以通过一定手段模拟实现拿到一定部分分,但是这对揭开整个题目并没有什么帮助。需要考虑题目中的每个操作的意义是什么,可以转化为哪些已知的模型并用套路解决它。

任重道远。

Day 3

kls 出题。貌似由于前一天 OJ 有很多 Waiting 打算今天线下测评。

开题还是看 T1,感觉流挺可做的。但是最小的包 $V\le 2000,\ E\le 4000,\ \mathrm{maxflow}\le 2000$ 一脸 TLE。

不一会想了个贪心,可以用路径压缩做到 $O(n)$(不是很清楚这里有没有 $\alpha(n)$,但是没看到哪里可以按秩合并)。

然后把之前的流打了出来开始对拍,流还打错了一次。拍上之后造了一组极限数据跑了 $1.65\mathrm s$,有了前天的教训于是开始卡卡卡。

当然到最后发现是卡了读入…各种优化都没用。最后到网上 copy 了一个 fread 快读板子但是不会用..

看了 T2 和 T3,感觉秒了 T2 的 40 分,没写先扔了看 T3。

感觉可以建个图,但是发现边数是 $O(n^2)$ 的。然后想了个贪心没把自己叉掉,$O(nm^2)$ 看上去很可做,带上 $\log m$ 也应该能过。

然后拿着 $n\le 12$ 对拍,偶尔 bf 会被 $n=12,\ m=12$ 卡成狗,但是并没有出现 WA 的情况。就头铁交了上去。

此时期望最大得分 $100+40+100=240$,理论最小得分 $60+40+0=100​$。

拿着 T2 码码码..差不多 10 行写完了,但是不会阶乘以内的对拍并坚信自己的 40 分狗贪心是对的。

这时差不多 10:20,我已经没事干了。←当然这一定是考试爆炸的前兆

拿出了之前关掉流量开关的手机刷刷刷,然而并没有打发很多时间。

中间下发了大样例,发现三个贪心都基本能过。虽然觉得有点奇怪但是继续摸鱼。

然后想起来 T1 需要卡卡,但是没卡成功。一直以为找到了假的 fread 板子..偶尔帮跑得慢的 T3 重新生成数据,然后再玩玩扫雷,时间终于差不多了。

结束之后看到 3 个阿克的,每个题都有一些人 A 掉,感觉今天可能是自信场。最终是 $60+0+25=85​$。

T1 果然是被卡了,应该是读入问题;T2 莫名挂了,甚至挂在第一个点,导致整个包都跳过了。明明过了大样例的…T3 贪心是有问题的,不过听说小数据可以过掉很多。此外如果某个循环倒序枚举是可以过掉更多的包的…

中午吃了大概四碗饭。汤泡饭太好吃了!!!!回房间找到了真的 fread 果然过了。

下午去发现 T1 是一道放过一些 $O(n\log n)$,卡掉很多 $O(n)$ 的玄学题,思路大概差不多。

T2 构造+卷积。那个贪心是错的,可以用排序不等式等一些式子叉掉。而且貌似读题不规范,爆零两行泪了,图不需要连通,森林即可。

T3 我的贪心假了,有个结论被 Dew 整出来了,不过后来他可能哪里写挂了并没有得到很多分数。

杂题选讲感觉很卡科技啊…上来扔一个斯特林反演,给出的思考时间长达 1h,不得不摸鱼。然后剩下的题有一些目前看上去很热门的算法。持续掉线,考虑明天还听不听杂题选讲了。

晚上只吃了一两个大概 $5\mathrm{cm}^3$ 的面包,中午吃多了不是很饿。改了一个多小时昨天 T1,没改出来。貌似 LCT 维护这个东西会很麻烦,可以在明天的自闭时间继续梳理一下。

Day 4

早上大概 7:55 到了机房门口,发现没有开门。于是等到了差不多 8:01,咕咕咕。

开题看 T1,数论题。发现分别是 $n\le 10^6,\ n\le 10^9,\ n\le 10^{18},\ n\le 10^{24}$ 这样很多档部分分。看上去 $n\le 10^6\ O(n\log n+q)$ 一脸可做,但是感觉后面可能稍微想一下也有分,于是随便想了想。

毕竟 $n\le 10^6$ 是个 DAG 上 dp,实际上状态会非常少,大概不超过 $O(\log n)$ 层,于是考虑用 map 存一下状态,因为给出了质因数,所以准备枚举质因数进行转移。

然后好像并不能涉及到所有的约数,然后就由于没过样例被扔了。

T2 是个字符串题。感觉比较签到,然后多搞了一会。每次一交就会发现自己有一些错误然后改改改,最后差不多了才扔掉,不过多组数据还是很虚的。

当然最后看提交记录是 $40\to 60\to 80=80$。

T3 并没有思路,又是一个暴力不会打的题。毕竟只会 $O(n!)$ 给我 $n\le 20$ 并没有什么用┑( ̄Д  ̄)┍。

后来 yy 出来一个贪心,但是不会贪。用了贪心引出的一个结论,好像可以 $O(n\cdot 2^n)$,有 $5$ 分了..

然后期望得分 $20+100+5=125$。

今天貌似投入的时间挺多的,也就是说没有自闭的垃圾时间。不过并没有更多的收获2333

感觉各种前后(3 道题)调整了一会,时间就差不多了。

出分 $0+80+0=80$,每天的分数在递增来着,排名就不一定了。

T1 T 了,好像并没有输出。貌似是 EOF 判错了。T2 fst,估计还是有什么细节。

T3 或许贪心错了或许枚举错了,不过好像是不可做题。但是难得看到 $n\le 5000$,应该是个 $O(n^2)$ 神仙题。

Dew 神神神,A 掉了 T2,然后 T1 据说期望 $O(T\log^2 n)$ 的复杂度卡成了上界 $O(T\sqrt n\log n)$??神神神。并且 T3 整出了看上去很对的结论拿了 $45$。

中午余姚中学的老师把 ZJOI Day2 安排上了。

中午喝养生粥。

下午讲题没有咕咕咕好评。T1 怎么上来「容斥+高维前缀和」好方啊。T2 好像把每个包都讲了不过我瞎打的。T3 有好多神仙做法啊,好像我的结论是个错的,并且有好多神神神弄出了比较优秀的 DP 式子。

lsy(评论 1L) 讲题公开膜 Dew(评论 3L)太暴力了。

然后杂题选讲听懂了一个爆搜,剩下的又卡知识点了。不过有收获就行。(并且良心的 kls 把课件发了下来(是因为讲完了吗2333

晚上吃食堂。感觉食堂阿姨好热情啊[捂脸],吃完了好像小卖部锁门了。下午忘记带杯子了不过撑过来了,晚上还能继续去机房苟一阵子。

然后开始改改改 T2,改了好久一阵子听说有牛客练习赛然后打算签到。结果签到半天签不上,好像是 spj 锅了,一开始以为不算错误次数不罚时,于是大力交了 10+ 发。最后错误改过来了,后来重测直接罚时 5h+???还好没认真打。

最后还是没把 T2 改过来,貌似我的解法需要用个栈存一下。

然后晚上去华润屯早餐了。

明天继续靠签到题苟活吧2333

Day 5

现在是 Day6,由于 intLSY 同学提前阿克没事干想来踩蒟蒻找优越感,于是就更了(就咕了一天怎么就催更了

摁了 6:45 的闹铃之后就睡过了orz,还好买了面包窝在房间吃吃吃。

开题,T1 是个数论方面的构造。想了一会没啥头绪,准备最后再打个暴力(下策

T2 给了一个幻方,但是是在 $\bmod m$ 意义下的。一开始没怎么理解好,后来发现只是一个矩阵,不是幻方。划划划一会没啥发现,又扔了。

开 T3,看到是个随机游走,每个点只能经过两次。看成每条边只能经过两次,那不是最后一定回到根节点了???样例不对啊…

鉴于此时已经 10:00(我也不知道摸了什么鱼就过了两个小时),于是打了看上去比较好写的 T3 暴力。大概调了十来分钟就差不多了。

然后再看 T2,还是画不出来什么有用的信息。这时发现 T1 只有一个输入,可以考虑打表,顺便防止 TLE。而且第二档暴力有 $20$,然后就开始打表,复杂度大概是 $O(k\log^2 k+nk\log^2 n)$($k$ 是枚举上界)。于是 $n\le 30$ 跑了半个小时左右跑出来了,一个有梦想的人会在剩下的 40+min 内跑出 $n\le 50$ 吗???然后脑抽看了 T2……

由于有了 T1 打表防 TLE 的意识,又因为 T2 只有 $n\le 5,m\le 5$,于是我开始打 T2 的表。复杂度好像飙到了 $O(5^{17})$,当然我直接跑了 $n=5,m=5$,这个看上去出题人一定会造的数据如果跑不出来,前面的应该也没用。

等它跑的时候我又去看了看 T1,在 T1 继续真·暴力打表。研究了一下已经打出来的东西,发现总有一段是 $x-1,x-2,\cdots,x-k$,后面几段也满足了这个个规律。然后先把后面的按这个规律顺下来交上去,再慢慢看是否全部符合

大概在 12:35 的时候乱输入 $n$,搞出了 $n=45$,发现输出了 $-1$,这时候就感觉这一段都是 $-1$,然后开始“二分”哪里是第一个输出 $-1$ 的位置。当然个数比较少,所以跟一个一个枚举检验没什么区别。最终找到了 $n=41\to ans=7567741$ 和 $n=42\to ans=-1$。高高兴兴地把 $42\sim 50$ 全部填上了 $-1$。

当然我当时并没有想到 $n>50$ 的情况,不然都输出 $-1$说不定还能对

后来快结束的时候才想到,中间有一段 $10^5$ 数量级一下子就变成了 $7\times 10^6$ 数量级,这个上界可能设小了。但是再大的话预处理就凉了,所以暴力还是写的不优(不然就不是暴力了对吧)。最终抱憾 $20$ pts。

出场听说 Dew 用比较优秀的暴力打出了 $n\le 50$ 的表然后爆零了,好像是他看到自己暴力的 $n=1$ 输出了 $0$,又看到题目中 $x>0$ 的条件,然后改成了输出 $-1$。不过有 spj,输出 $1\sim 9$ 都是对的啊2333。不过貌似他打表找规律 A 掉了 T2,我到现在还没跑出来 $n=5,m=5$(((

下午讲题时间疯狂变长最后才知道是把杂题宣讲给鸽了。

由于 ZJOI Day1 难度是 $2\to 3\to 1$,所以签到题放在了 T2,但是 T3 过掉的人最多…大家都喜欢硬核 DP 吗。。学不来学不来

吐槽 T1 的时候 Dew 指出了那个问题结果 zzt 上去就把 $1\le x$ 改成了 $0\le x$。

T2 有个看上去很严谨的证明,不想看了。但是这种核心代码只有 $4$ 行的题在听了之后不知道怎么再发挥它的价值呢…

期望 DP 这种东西好像看上去最可做了。但是要分 $5+$ 种情况讨论啊,不仅需要码力还需要一点脑子(我没有

然后还是提前讲完了。到机房发现洛谷月赛还有一个多小时可以打,然后先 T1 签到,T2 不是很想想了于是开始推部分分,发现奇数编号的点非常可做于是就都打了。但是获得了 $82$ 分的好成绩,好像是每个点 $5$ 分,$5$ 组数据,然后我没判就还过了几组偶数点。

T4 lxl 题,秒了暴力就看 T3,但是 T3 题面太长劝退了,回去想 T2 也并没有什么进展。最后 10 分钟看懂了 T3,不过只打了初始化部分就结束了。多给我一个小时应该可以多拿一点分甚至rk1?

晚上回去整理了某比赛的 .md 题解,然后感觉对 Typora 有点审美疲劳了,就尝试了一下之前下好的 $\TeX$。弄了一会上瘾了,然后就一直查资料调调调,弄出了一个比较满意/美观的版本,也是游记咕咕咕的原因

考虑游记写个 $\TeX$ 版本的发上来???

Day 6

昨天的面包没吃完,继续塞塞塞。

这场好像是真自闭场,但是分数甚至比前一天高。

有了昨天的经验,骗过一次人的伎俩不会再用第二次了,所以还是开了 T1。并且昨天 zzt 还说了“前面背景放一道题,后面不一定是它的加强版;前面放一道不可做题,后面说不定可做”。

但是好像都不可做啊…一脸三道构造的样子。

T1 怎么又是数学题啊,暴力好像都不可打,给定奇质数 $p,q(q-p=\lambda,2\le \lambda\le 3\times 10^5)$,被这个 $\lambda$ 搞懵了。第一档暴力是 $p\le 10^3$,乘一下是 $10^9$,怎么都跑不过去啊..我的最优复杂度是 $O(n\log n)$ 来着..头铁还是打了个 $O(n\log n)$ 上去。

T2 给了一堆公式,后来才看懂那些 $\sum$ 是把哪些数加起来。当时写上去一个高斯消元,该过的(?)样例都过了。然后手动构造一些特殊排列被当场卡飞了,发现会有负系数,但是题目要求 $0\le p_i\le 1$。

然后就只考虑暴力了,$n\le 5$ 只有 $5!=120$ 个排列,每次随机生成 $m=5\le n$ 个排列,卡时到 $900\mathrm{ms}$,感觉比较稳。打算扩展到 $n\le 10$,发现 $n=8$ 就整不出来了。于是乎收回了远大的理想。

开 T3,虽然不像是构造,但是它没有给 $c_1$ 的初始值,并且 $c_i$ 还是变化的,所以还是需要这方面的构造。

有 $30$ 分是 $k\le 2$,猜了个结论,推了一下应该是对的。在位置 $i$ 的贡献为$\frac{sum1_i+c\times mus1_i}{sum2_i+c\times mus2_i}$,根据数学课上学的“糖水定理”,当 $\frac{sum1_i}{sum2_i}\le \frac {mus1_i}{mus2_i}$ 时,$c$ 应该尽可能大,如果不管其他因素,取 $c=1$;否则,$c$ 尽可能小。

根据这个可以知道 $\{c\}$ 一定是一段连续的 $1$ 和一段连续的 $0$ 拼起来的。

11:00 左右打完了上述暴力,期望得分 $0\sim 10+20+30=50\sim 60$。

当然还有很多基于 T2 的时间优化,但是对于常数的优化并不能对瓶颈在指数的算法构成一些优化。

最后 $0+0+30$,这时候才看到 T2 的输出是要先输出排列个数 $m$ 的,应该是为了方便 spj,但是我好像没怎么仔细看输出格式orz…而且之前貌似没怎么犯过这种错误,只能当教训了。但是一共 $60$ 就挂 $30$ 比例也太高了点..

中午看到牛客有两场比赛,都签了个到。并没有中奖,但是好像知道了 01 背包的 mex 求法。

下午讲题吐槽的人变少了。可能是自闭场无槽可吐???

T1 是据说的送温暖题,不过还要推好一阵子。另外 slides 上的题解部分莫名消失了?不过就算有估计也看不太懂。

T2 是基于 $n$ 维凸包的题,中午考完了给 lbw 口胡,当场秒出 $n$ 维凸包 %%%。当然也许 $5000$ 个式子高斯消元能跑出来 $n\le 10$。讲解用了向量推导,从二维平面上的 $\lambda\vec a+(1-\lambda\vec b)$ 的中点一定在 $\vec a-\vec b$ 所在位置的线段上。剩下高维的不会了。

神仙 T3,防 AK 题?题目给出了一个分式但是并没有想到分数规划,不过知道是分数规划也不一定写得出后面的点。

后来听 sjzez 的神仙吐槽说样例输出 $0.666666668$ 一眼二分2333

及时补锅,++rp

10
说点什么

avatar
4 Comment threads
6 Thread replies
1 Followers
 
Most reacted comment
Hottest comment thread
4 Comment authors
DewwjyyyforeverlastingDL24-liushengyu Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
DL24-liushengyu
游客

%%%%% wjyyy

foreverlasting
游客

%%%%% wjyyy

Dew
游客
Dew

%%%%% wjyyy

DL24-liushengyu
游客

为啥… 不更了? ( 期待

/* */