ACM-ICPC 2018 徐州赛区网络预赛 口胡

军训放了半天假,跑来机房补题,感觉最近的题太多了,敲不完,口胡一下。

A. Hard to prepare 开始往容斥原理的方面想了想,搞了半天感觉太复杂放弃了。后来想想应该是递推,但是1和n-1一样的情况没想清楚,后来查了一下发现递归处理成n-2的情况就好了~

https://nanti.jisuanke.com/t/31453

B. BE, GE or NE 开始的时候在考虑贪心策略,然后觉得太复杂放弃了。后来想想这个[-100,100]的区间肯定有很大的作用,发现数据并不强大,可以反向递推出每一层,的必胜的数字,然后一直推上去,如果a,b都不能必胜,那么就在中间了。

https://nanti.jisuanke.com/t/31454

C. Cacti Lottery仔细想了想,就是先枚举出他知道的位置的数字,然后对于每个这种情况暴力求出期望的最大值,然后累加答案即可。感觉时间很吃紧,如果最开始给个空棋盘会TLE?

https://nanti.jisuanke.com/t/31455

D. Easy Math一看就是我不会的数论,果断直接查题解。又要莫比乌斯,杜教筛,一大堆数论,题解也不看了。果断弃疗

https://nanti.jisuanke.com/t/31456

E. End Fantasy VIX 开始感觉很可做,感觉拓扑然后dp就行。后来发现没有想象的那么简单。网上之自由一篇题解,是矩阵做法,没太看懂,但却是让我回忆起,矩阵和图论确实有一定的关联性,以后面对数据规模很大,转移又比较方正的图论题,可以考虑下矩阵,虽然没做出来,但是还有有所收获。

https://nanti.jisuanke.com/t/31457

F. Features Track mp映射一下就好了,很简单

https://nanti.jisuanke.com/t/31458开始想了想,觉得正着用线段树处理就可以,但是后来发现有些痕迹没法保存。于是试一下反着来行不行。因为不存在包含的情况,所以每一次都会对结果产生贡献。对于x轴和y轴我们分开处理,从后到前,如果当前的x轴线段的y大于该段的最大值,就产生贡献,这样子我们用 线段树处理即可。

https://nanti.jisuanke.com/t/31459

H. Ryuji doesn’t want to study维护一个前缀和,线段树区间处理就好了,不要再犯老毛病,要用的数组里面的数据没跟着线段树修改。

https://nanti.jisuanke.com/t/31460

I. Characters with Hash签到题,不解释。

https://nanti.jisuanke.com/t/31461

J. Maze Designer感觉这道题很棒,查了题解才懂。把每个墙都看成一个边,那么最大生成树即可,然后对于询问求LCA。简直太巧妙了!

https://nanti.jisuanke.com/t/31462

K.Morgana Net又是数学题,果断弃疗….

https://nanti.jisuanke.com/t/31463

 

 

 

发表评论