武汉理工大学2019第二届ACM新生赛 题解

打的第一场新生赛,还是挺兴奋的。前排吐槽,题面真的不说人话,看中文比英文都费劲。除了这点,题目出得还不错?给个好评(

A.wyh族谱

看半天没看懂题意,最开始我还迷惑为啥不能是一条链,后来才明白是最小平衡树。
推荐这篇:算法笔记:平衡二叉树(AVL)最小结点数与斐波那契数列的关系
总之结论就是f(n) = f(n-1) + f(n-2) + 1。或者说是fibonacci数列第n+2项-1。因为n<=1e18,所以用矩阵DP。
啥是bm算法啊

B.找素数

数据范围这么小,果断暴力dfs

C.最佳性价比

水水水,签到题

D.wqy改造

官方题解说的是:“利用线代知识和常识可以发现这个式子是收敛的”,我盯着自己手里的高数书出神,说好的新生赛呢,难道你校新生都学了线代吗(
结论题,把每个值都加上a/9就ok了

E.摸鱼plus

暂时不会做,占坑
官方题解竟然都是打表找规律诶(逃

F.wyh病毒

bfs即可,也可以并查集
其实我最开始想到的是并查集,但是突然找不到板子了就胡写了一个bfs QAQ

谁能教教我怎么给变量起名啊

G.lru算法

这题题面是这几道里最清晰的,但是我瞎了没看到“最长时间未命中”……
模拟一下就ok了

H.hyy刷题

真的看不懂题,哪怕给个样例解释也好啊= =
需要特殊处理一下最后一天的情况,具体看代码吧

I.摸鱼

打表发现规律:10010 10010 10010 ……
因此可以耍赖了23333333
正解不会,OI省一选手真的不会博弈论啊555(明天我就学SG函数qwq

J.wfy回家

应该好做,但是我没来得及写,某摸鱼题几乎用了一个小时,导致最后啥都写不了= =
我的思路是:求圆心与线段是否相交(点到直线距离和R比较+垂足位置判断),如果有就-割线长度再+弧长
补完就把代码放上

K.lxh打CF

模拟题,因为懒得敲函数就复制粘贴了= =代码略丑。


反思一下:
排名rank8,和rank5题数相同,但是罚时多了6h。
怪自己交题的时候不检查,竟然还犯CE的错,心态真的挺关键吧……
卡题(摸鱼)的时候明显已经消极怠工,那个时候还剩一个小时,要是能静下心好好做一下J题,应该就能10题了。
下次写题解要是没有1A就把原因一并写上吧,还是要多学习一个

最后膜一下我校的ACMer
《武汉理工大学2019第二届ACM新生赛 题解》

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注