2017 CCPC秦皇岛赛区比赛总结

朱雀 2022-06-06 04:43 183阅读 0赞

2017 CCPC秦皇岛赛区比赛总结

这场比赛是我入ACM这个大坑以来打的第一场大型比赛，可以说我是从今年7月份的暑假集训才开始正式学ACM的，之前从来没正式的学过什么高难度的算法，一直就是做做水题，在各种OJ上交A+B。我的两个队友flc和wz虽然比我多学半年，但是也就是比我多会做一些简单的背包和dfs这种基础算法什么的，所以说我们三个人真正花心思搞ACM其实只搞了三个多月，这么短的时间里可以获得一个CCPC区域赛的铜牌我们三个人已经是非常满足了。

这场比赛一共有249支队，金银铜的比例依然是10%20%30%，75到150是铜，我们是第120。虽然我们只做了四道题，但是我们四道题都是1A，所以排名在4题的前面，有很大一部分4题的在150之外，所以也可以说我们这次运气比较好吧。

A题：位置减去时间，对m取模，排序，机器人的初始位置一定和其中的一个值相同，然后枚举每个点作为起点，O(1)的转移，不会T。这道题是flc和wz在想，他们前面的都想到了，就是一直没想到O(1)的转移怎么转移，所以就没做出来。

C题：区间DP

E题：暴力，但是wz好像卡实现了，写的时候出了一些小问题，比别人A的慢，可能太紧张了。

G题：贪心，高精度。刚开始学java，对java不是很熟，所以没有用java的大数类。于是对着资料敲C++的大数模板，一开始没想太多，以为只要一个高精度进制转换，把这个数转换成二进制随便乱搞就行了，后来发现还需要高精度的加减乘除，好不容易敲完了模板，写完了乱搞的代码，疯狂WA，仔细想了很久，发现思路完全错了......浪费了一个多小时，虽然最后想出了正确的做法但已经没时间了。因为要使最后的或值尽可能小，所以我们可以找个最低的至少要是1的位，然后从这位开始往低位构造，对于当前位k，如果从k-1位到0位所有的位都选择m个都不能构造出大于当前n所需要贡献的剩余数值，那么我们第k位就必须是1，既然是1了，就要尽可能多的去提供贡献，这样贪心下去就可以得到答案。

L题：签到题，一开始把题意理解错了，28分钟才A，心态爆炸。

M题：思维题，如果一个点以它为圆心，r为半径的圆都在大圆内，那这个点一定是最安全的点，因为所有可以使它安全的小圆都在大圆内。所以说一个点安全的概率的高低就取决于能使它安全的所有小圆有多少是在大圆里面的，这样想这题就很简单了。