HNOI2020 裂开记
lk啥也不会 退役了
Day0
把十二省联考被我鸽掉没写的一道可做题(d1t2)写完了(
虽然实际上没考字符串
然后开始颓
慌得一批
怕像HNOI2019一样的惨败
晚上出乎意料的没有失眠
Day 1
进考场
看到题,没有c++11,T1连O2都没有/tuu
赶紧写了个快读,就像平时用的那样一次可以连着读入多个数的(这东西报了奇怪warning c++11相关我没看懂 最后删了)
读了遍题,感觉T1T2看上去都能做,但是T1看上去比T2麻烦点,T3看上去暴力都不会打。
然后写了个T1和T2暴力,开始推T2,发现难度在求组合数
先写了个nk求组合数的做法,开始以为要写exlucas,然后发现不会算模数=p^k很大的情况,然后发现每次只要乘一个数除一个数可以直接对模数分解质因数然后算。写完之后拍上了。
然后写T1,n 2e6 3s 没O2真的毒瘤/tuu,编了个线段树上二分,感觉\(\leq\)和\(\geq\)很烦,然后把t=1的+=0.5就变成\(\leq\)和\(\gt\),就可以直接二分了。
当然怕被卡我写的ZKW,极限数据本机还是2s
然后想T3,猜了个线性基性质脑补了很久没想清楚为啥(赛后听说很显然但我没懂),最后写了个对拍测结论,看上去能拍上
好像发现这题是保序回归了可惜我没看论文
然后想了个拆点dinic,没时间写暴力了直接冲。
然后过了样例1,2 (样例三过大)
然后想了一下后面10分,发现不难(
不过我猜到了但不会证\(\sum
(x-a_i)^2\)取最小值的时候\(x=\frac{\sum
a_i}{n}\),又拍了一波
然后写完了,前50和后10分对拍,不会写gen于是偷懒把样例3的bi改成ai,vi随机
然后检查了下就下考了。
期望得分 100+100+60
Day 2
进考场,看到文件名是count,tree,transfer,于是计划先开count
然后看到题后 那 没 事 了
怎么一题都不开O2 真就 卡 常 大 赛??
看了遍题,T3不知道能不能做,T1没仔细看,T2感觉带BIT的2log好做
然后先写了个T2暴力,想了想优化BIT发现可以直接移动指针,因为总共移动量很小,这样就1log了
然后写完了,对拍鸽了,看一眼T1,发现状压dp四个字写脸上了,然后随便想了下就会了,把T2拍上开始写。
然后写完了,极限数据1s(时限2s
然后写了个\(O(m!n)\)的暴力,拍上了,来看T3
先写了个暴力。
感觉容斥然后矩阵树非常显然,然后想了下怎么算一个图每棵生成树边权和。
第一想法也是枚举一条边再求行列式,然后发现可以直接边权(w_ix+1)最后求一次项系数。
发现复杂度有点假,然后加了两个剪枝(x倍数边不连通直接不管,可以让复杂度/=n,还有x所有倍数gcd不等于x的时候不算了直接取gcd倍数的答案)。
然后不知道能不能直接模x^2计算,就先写了个插值(
然后拍上了。
然后想了下模x^2怎么写,然后感觉可以假装辗转相除,然后写了下,然后拍第二组挂了。
然后发现和暴力拍第二组也挂了。
然后发现傻逼错误,改完之后拍上了。
时间12:00左右。
然后开始自闭
感觉无盘可翻
期望得分100+100+100
Day 3
看了下代码,Day2T2 建图写了弱智错误 如果fa=n直接re
fst了 -80 (链的部分分fa[i]=i-1) 退役了
Day 4
出分了,出题人所有数据fa<i, 送了我80分。
感人肺腑。