【总结】BJOI2019游记

Day -4

市里训练的模拟赛,T1压根没看懂题,就先跳过看T2,T2裸的构造,半个小时就搞出来了,写了个正反鸡爪。T3是个限制条件挺多的DP,暴力写炸了,T1一直就没看懂题,不知道出题人想说啥,表示理解不了。最后就T2A了,获得100分。

 

Day -3

第二次模拟赛,T1题意是一个网格图,让你设定炮塔,炮塔可以选择横着打或竖着打,还有镜子可以反射炮弹,求方案让炮塔覆盖所有空地,且不会互相攻击。好像是个网络流,捣鼓了一会,发现好像不能表示选横着打还是竖着打,暴力只有状压DP有分,还挺难写的,于是跳过。

T2是完全图边权矩阵生成树什么求和,一看就不可做,什么多项式弄来弄去的,可能还得矩阵树一波,不会写,打了40分暴力,收手。

T3是给定一个图,问是否能将边黑白染色,使得黑白边都各自不成环。看完题依然先把暴力打了,发现了一个有趣的性质:只要存在一个导出子图不合法,整个图就不合法。逆命题好像也成立,利用这个性质配合最大权闭合子图写出了拿到95分的错误算法,跟正解仅有一步之差。

总分135,排名还挺高的。

 

Day -2

第三次模拟赛,T1是给定一个n*m矩阵,求左上角走到右下角经过数的积大于给定数的路径条数。拿到题就想到了一条性质,最多只会乘log次,围绕这个性质想了想,感觉值不会太多,就拿vector暴力转移,本地随机数据感觉快的飞起。

T2是统计路径条数,没想到点分治,就把40分的链写了。

T3是很显然的一个DP,加了点剪枝优化到了n方,应该能拿40分。

总分74,T3数据问题只拿到了34分。不过好像大家T2全A了!?有点丢人。。。第三题好像是什么wqs二分,我也不会。

 

Day -1

没有模拟赛 ,拿了十二省联考Day1的题给我们做,把T1异或粽子写了调了就溜了,下午听听讲课后就回家了。

 

Day 1

正式省选第一天,T1是给一个有残缺位的数字串,和一些匹配串,每种匹配串每次匹配都会使当前数乘上匹配串的权值,最后的权值是出现的匹配串的权值的积开总匹配次数次方,输出使最后权值最大的数字串。第一眼就是AC自动机上DP,写了半天突然发现好像转移有点问题,没法维护开n次方,突然想到将权值取对数就变成了求平均数问题,想到自闭也没想出来如何维护平均数,换了暴力DP分交上去了。

T2是什么斐波那契数列和一个神秘数列的组合数区间求和问题,没发现什么性质,加上T1心态有点爆炸,就写了10分就交上去了。

T3是一个网格图,有一些加墙和删墙的操作,询问两点之间扶着墙走的距离,这题暴力就写的我恶心的很,而且就10分,写完了过了样例交上去了。

最后T1暴力获得15分,T2 10分,T3果然暴力写炸了,总分就25分了,感觉凉成尸体了。T1维护平均数只要分数规划二分答案即可,考场上脑袋想炸了也没想到二分答案,想到了这题就做完了不是吗??如果获得110分就勉强活了。。

 

Day 2

T1弱智DP,开场AC,本机跑的飞快。打开T2,光在镜子间无限反射问题,高斯消元法n三次方能搞出50分,写完了发现矩阵挺稀疏的能优化到n方,搞到70分收手了。T3从打开题到考试结束都没有想出任何靠谱多项式算法,都被自己hack了,写了7分问号复杂度暴力交上去了。

嗯,还挺稳。。写了177分就拿到了177分。不过,好像T2也是个弱智题,全场AC的那种,高斯消元矩阵稀疏到甚至能线性复杂度解方程,甚至还有更弱智的做法。T3正确的贪心好像能有47分,人均200+,屈辱退役。。看来还是我太菜了。。只能安心搞文化课了(哭哭。。

 

上一篇:「BJOI2019」


下一篇:LuoguP5322 [BJOI2019]排兵布阵(DP)