PKUSC2019①记
command_block
2019-05-26 22:10:26
# Day -?
详见[GDSOI2019划船记](https://www.luogu.org/blog/command-block/gdsoi2019-hua-chuan-ji)
攒了好大的一波$RP$.
省选前的一个月集训也提高了一些水平,感觉比$THUWC$的时候高了一些。
# Day [-12,-10]
“你们联赛考得好的可以去试试”
报了PKUSC和THUSC,没有门票虚的一批。
好像在Day -10,区里来了一个$NHOI$模拟赛,由于区赛都是上善若水,于是立了$AK$的flag。
一开题发现前四题模拟,$30min$码完了,$T5$简单状压,$T6$没能一眼看出来,貌似是$DP$
咕咕咕的出题人没写空间范围,于是T5$O(n2^n)$的空间只开了$n<=17$,被卡掉15分。
$T6$发现是二分+$DP$,依稀记得在小学的时候桂一题库里见过,怕不是原题?
由于赶着去午读于是提前离场了。
事后发现T2模拟写挂,只有5分,T5有35分,T3挂剩15分,于是$205/300$被吊锤。
看到低一届的小学同学得了$275$,%%%
又攒了一波$RP$.
# Day -8
停课一个月后回来月考,刺激!
得知THU咕了,PKU过了。
那就去碰碰运气吧!
# Day -3
于$NF$颤抖着迎接期中考的成绩。
数学竟成为三科最差,咕咕咕……
得知飞机票太贵要坐高铁去帝都,于是提早了一天回家。
随便看了几眼题目,口胡了某道数论求和题就睡觉了。
# Day -2
抖擞精神看前几年的题。
懵逼的我在百练上找不到往年题?只好上luogu+Loj看了看2018的题目,DAY1会两道,自我感觉良好。
看了黄学长以及众位大佬的的游记才知道$DAY1=\{\text{普及数学,普及状压,毒瘤斗地主}\}$,自闭了……
还要考数学?~~回想起数学成绩~~
还要面试?英语自我介绍?
(~~反正也熬不到面试那一关~~)
口胡了一道期望题就睡觉了……
# Day -1
起了个大早(相对早而已)赶高铁。
8个小时的高铁大部分用来睡觉。
广州->长沙的路上:看着大佬的blog学习了EGF,豁然贯通啊!
长沙->武汉的路上:$\large{Z^{Z^Z}}$
武汉->郑州的路上:午饭呢?12:30午饭卖光了?只好吃了开水泡馄饨……
郑州->石家庄:看了付公主的背包一题,若有所思……
石家庄->北京:发呆+看风景。
等了半个小时Taxi才到酒店。
根据酒店老板的指点找到了一条“食宝街”,吃了面。
晚上做了一道EGF+付公主的背包,看了看多项式。
# Day 0
上午又做了一道多项式,通了试炼场费用流。
下午前去报道。
dfs松弛成功:$dis[n]=25min$;
排队$10min$,同学们从报道处一个一个出来,人均间隔超过$1min$?
前面的大佬:请准备英文自我介绍……
懵逼的进去了,发现只用签个名。
获得纸牌,没白来一趟。
通知书上写着:请在5.27交回胸牌。(~~mmp~~)
看了看日程,竟然没有数学题和面试?
前往试机,第一道是去年的普及数学,第二道smg?看题面好像是冬令营的,没有一点思路……
静坐了30min,打了NTT试了试,就回去了。
dfs反向松弛成功:$dis[n]=20min$;
晚上还是吃面,吃得太多了,一杯冷饮下肚,肚子痛了一晚上……
复习了一下,又开始写一道群论题,没调出来。
$00:00$起来吐了一回才睡安稳了……
# Day 1
没有什么比赛的感觉???
$7:40$起来,吃了早饭出门。
dfs松弛成功:$dis[n]=18min$;
$8:50$同学齐了,遇到前辈大佬oql。
教授~~哗哗哗~~了一阵之后$9:50$就把我们放了出来……
我们去未名湖转了一圈,风景不错,要是能集齐四季就好啦!
去农园吃中午饭,真香!!!100元饭卡好评!!!
吃完饭之后感到有点困于是靠墙坐着休息了会……
12:30到达考场所在大楼,跟着一堆人进了某个门,结果被几个老师告知里面在考托福,被赶了出来……
从另一个门进去,绕了几圈之后又来到托福考场,又被赶了出来……
按照报道的路线走,终于找到了机房,感觉难度直逼纪念碑谷TAT.
机房已经开了?允许试机???
于是找好座位15min打了个快读+NTT。
$13:00$开考,看T1:
九老师和村民???看不懂,先跳掉。
T2:九老师和乒乓球概率???看不懂,先跳掉。
T3:xor?数据结构题?貌似可做!
大赞题面:如果我们出6道数数题,那么对数数一窍不通的选手的能力值为0。
好像是建$01Trie$然后可以交换左右子树,YY了一阵后发现是01背包,$O(n^2)$只有暴力分,咕咕咕。
想了2h,尝试过线段树,OGF多项式Ln+Exp(~~付公主的遗毒~~),均一无所获,心态巨崩。
T1题面改了,仍然没看懂……
可行性背包似乎能$Trie$上$dfs+bitset$乱搞,不过似乎是$O(\dfrac{n^2logn}{64}+q)$的,还是会$T$.
终于惊觉只有$Trie$上同时有左右儿子的节点才需要操作,否则直接传引用就好了……
$O(\dfrac{n^2}{64}+q)$,一发$93$!
发现没考虑能力值重复的状况,改了$10min$终于$AC$
回头看$T1$,手玩了一下发现修改反过来好做一些,把块内都排序后求逆序对就好了(类似动态逆序对,每次合并两块)。
线段树合并+树状数组逆序对$30min$码完调完,一发$AC$!
此时还有$1h10min$,看了$30min$看出$T2$的$O(n^2m4^n)$做法,不过位运算功底实在太差,又没时间打暴力,遂弃疗。
隔壁同学$AK$,突然提前离场了,%%%
$DAY1:100+0+100=200$
人均水平不知道……
还是吃面。
晚上发现昨天的群论题$Burnside$忘记除以置换总数了,而且漏了一堆边界情况,调了调终于$AC$了。
# Day 2
dfs松弛成功:$dis[n]=15min$;
图灵奖得主的全英文讲座,自闭了……
不过听到“高位球体容立方体”和“随机向量极大概率垂直”那里懂了一点,是由于看过某毒瘤量子物理书导致的吧……
前去农园吃饭,趴桌子睡了一会。
长了个记性,$12:30$赶到机房。
同样是打了NTT+快读,怎么可能两天都不考多项式呢(flag)?
开题,数数题模数都是$998244353$,可是没一道是多项式……
T1:树上染色,相邻的节点不能染相同的颜色,外加若干限制。
当场降智看了$1.5h$没看出来,以为能启发式合并特殊颜色码了$30min$结果发现做法假了……
打个$22pts$暴力走人。
T2:构造题?在高维空间内构造一棵曼哈顿距离树?
YY了$30min$,发现两点之间最短路必然在树上,于是每个维度只能有正负两个延伸。
又发现维数=(叶节点+1)/2。
写了个dfs鼠目寸光贪心构造不过样例,换成bfs,交上去$49pts$(菊花和完全二叉树)
(中间经过了$30min$调试)
后来一看$n<=100$,根据结论可以检测解的正确性,构造一次才$O(n^2)$,嘿嘿嘿……
于是枚举bfs的起点,WA了,还是49。
随机了几个数据把自己hack了,维度基本只差1维,觉得很懵逼。
于是给每个点随机一个权值,不断随机排列,然后跑带权bfs(Dij?),不找到解就不停下来。
全$T$了TAT.
后来发现bfs貌似没锅,不过子节点的扩展顺序会影响答案。
于是把边表按照随机优先级排序,交一发,过了!excitied!
此时只剩下$1h10min$,看$T3$什么线弦图?
出题人:大家平时想必做过不少关于“线图”和“弦图”的题目吧!
蒟蒻表示没做过,弃掉T3。
看了看T1发现就是个sb线段树合并,但是时间只剩$40min$,打一条链的部分分吧……
码完了拿着两个一模一样的暴力拍了$10min$一脸懵逼,佩服自己。
终于还是没能写出来……
$DAY2:22+100+0=122$
晚上没有吃面。
然后就回来写游记了。
祝自己$DAY3$好运鸭!
# Day 3
一晚上都没睡踏实,听说初三有大佬$AK$,害怕自己再次打铁……
$7:30$起来直奔北大,在$7:55$找到了双创中心报告厅。
来了个信科副主任(忘了)总结了一下几天的日程,并且介绍了一下情况,活跃了现场气氛。
然后九老师讲题:
D1T1:跟出题人的解法相同。
D1T2:考场口胡除了出题人没有卡的次优解,正解轮廓线???Orz!
D1T3:跟出题人的解法相同,成都七中大佬当场口胡根号做法,Tql!
D2T1:真的是线段树合并啊!不过细节好多……还是自己太菜了。
D2T2:出题人讲了个严谨的证明做法,随机选手偷笑~
D2T3:smg?仙人掌,分治FFT?听说有初三一小时$AC$的,%%%
最后开始发奖:
发完了两沓奖状没念到自己,心慌……
站在一旁的教授又拿出两沓,眼见着奖状堆越来越薄,心想自己怕不是又打铁了。
突然被叫到了名字,上去一看天哪是①!
回来的路上听说有六年级签②,初一签①的,貌似江苏初中四个①?Tql。
这几天真是$rp$暴涨,乱搞题(D1T3,D2T2)都做出来了,运气真好啊。
那么,$NHOI$见!