2017年中国大学生扫大街竞赛打铁记（CCPC秦皇岛）
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-------------------------------------------
凉了凉了
-------------------------------------------
题意&题解：
A：
题意就是说一个圆桌m个座位，有一些位置上有人，共有n个，有p个时间，每个事件是第a[i]个人在时间b[i]发出了一个申请，然后你是一个机器人，在不断地顺时针绕圈圈，每秒钟走一格，每遇到一个人就处理他发出的所有申请，一个申请会贡献的愤怒值是从他发出到被处理的时间差，请你确定初始位置，使得愤怒值最小。
首先假设第i个人的座位是t[i]
假设初始位置是s
考虑第i个事件，显然他贡献的愤怒值是(t[a[i]] - ((s+b[i])mod m)) mod m = (t[a[i]] - b[i] - s) mod m = ((t[a[i]] - b[i]) mod m) - s) mod m
于是设c[i] = t[a[i]] - b[i]
于是愤怒值就是r = Sigma(i)(c[i] - s)mod m
现在我们先假设一开始的位置在m，即s = 0，初始的r就等于c[i]之和
当我们把s调整到s'时，愤怒值的减量就是p*s'-Sigma(i)[c[i]<s']*m
显然，我们一定要把某个c[i]减到0，这样是最优的，于是s'的取值只可能在c[i]里面取，因此只需要枚举s'的值，算答案，取最小者即可。
M:
题意就是说有一个半径为R的大圆，然后在这个大圆内随机取一个半径为r的小圆（完全包含），大圆内有一些点，求哪些点被小圆覆盖到的几率是最大的。
我们说一个圆的覆盖区域就是所有能覆盖到他的小圆圆心组成的区域
首先，若R>=2r，那么考虑，所有离圆心距离<=R-2r的点的覆盖区域都是一个圆，是最大的，因此就是他们了，如果没有这样的点，那么显然所有点离圆心越近越优。
若R<2r，那么可能的最大的覆盖区域就是一个半径为R-r的圆，所有离圆心距离<=2r-R的点的覆盖区域都是这个，因此就是他们了，如果没有这样的点，那么就是离圆心越近越优。
----------------------------------------------
比赛记录：
一开始我们就格子看题，我看了M和G之后gmr跟我说了A题题意，我想了想好像可以想，然后就想了想，推了一会儿公式就推出来了，于是就写写写，一开始想错了，WA了一发，但是错误不大，于是改了改就A了。
后来ljz、gmr写了C和E，然后说H是裸的匈牙利，于是叫我写（说是因为我以前超过匈牙利的板子比较有经验），于是我写写写，写出来WA了，然后我们又讨论了一下，又觉得M可以做，于是写写写，写出来又WA了。
于是我们一直在纠结H和M是怎么回事，后来他们终于发现了H的问题，改了半天之后终于A了，然后我发现了M的问题，改了改也A了，然后已经没多少时间了，我们说写一下G，我们想了两种算法，觉得时间不够了就写了比较简单的一种，高精度的模板抄了一半ljz说说不定可以用java写，于是就写写写，写完之后CE了，但是我们不知道怎么编译，于是就没办法了。
----------------------------------------------
比赛总结：
这次感觉主要的问题是写题的正确率太低，这个是我们队一直有的问题，之前都没怎么在意，结果这次罚时爆炸。
然后就是最后G题没写出来有点伤，主要抄模板的时候我们发现三个人都不会盲打，抄写效率极低，然后又不会编译java，所以就gg了。
感觉考试中途（A掉M之前）心态有点崩溃，比较急躁。
----------------------------------------------
评论 (0)
