所以说这场比赛与义务教育有什么关系?
day -1,6.16,Fri
人在机房坐,比赛天上来。
当时洛谷日爆,然后脑抽写了个东西一直打开luogu.com.cn。
然后教练打开了屏幕广播,说了一下比赛的事情,把座位表发给我们。
似乎不用linux评测。
结束广播之后,屏幕就再也没有亮起来。。。(后面重启好了)
day 0,6.17,Sat
jy只有初一去了jz,高中在402断网比赛(当然还有春神),于是初中的去了302。
8G内存!VScode!(虽然我不用)VMware!NOIlinux!
下午Jimmy说应该是用Windows评测。。。
day 1,6.18.Sun
昨晚睡得比较晚,头有些痛。
6点起来,7:50到jz,又睡了一会,8:20进考场,考场在503。
我前两个位置都没人。Verser在我正前方3个位%%%
没断网?全都在敲代码?没有VMware但有Gvim和CodeBlocks?
于是我配好了Dev,测了一下a+b和文操。
发了题面,没有大样例。
开题!
T1
求给定字符串的最长回文子序列长度,$n\leq1000$。
不会有人想manacher吧?
想了一个朴素的 $O(n^2)$ 区间DP,应该能过。
T2
有两个盒子AB,其中黑白球数给定。每次从A拿一个球到B,再从B拿一个球到A。重复 $n$ 次,求A中白球比率的期望。$n,\text{总球数}\leq10^{18}$。
奇奇怪怪,只会 $O(nm)$ dp。
T3
给定一个 $n\times n$ 的方阵,每次操作一个矩形 $(x1,y1)(x2,y2)$,给矩形内的点 $(x,y)$ 加上 $\binom{x-x1}{y-y1}$。求最终矩形每行每列的异或和。$n,Q\leq5000$
题目主人公是骐度空间·莫羯座·十一月的萧彰。。。
T4
给定一颗树。每次操作先选择一个点 $a$ ,断开 $a$ 的邻边,再在 $a$ 与之前相邻的点之间重新连边(任意方式,只要没有环)。求把树调整成给定形态的最少操作次数(点有标号)。$n\leq10^6$。
弃。
看完题大约9点,感觉很懵,先打了T1,过了样例和手造数据。
9点半,出去上了个厕所。
然后强攻T3,发现了一个差分做法,设 $a_{i,j}=ans_{i,j}-ans_{i-1,j-1}-ans_{i-1,j}$,那么操作时只会改动 $O(n)$ 个位置。
用1小时打完,尝试优化T2的DP无果,于是打了60部分分。
T4暴力都不会。。。
然后闲着没事干,打了T1T3的对拍。
于是边检查边对拍边摸鱼了半个小时。
估分100+60+100+0=260
赛后
听说不少人切T3,T1有好多奇怪做法。
路上被-6n打劫了,他说401有VMware!
yjx和我估分一样。
lsx切T2?$O(64\log n)$???
中考、期末考RP++!