五一假期，和lch一起打了Google CodeJam 2015 Round1的第二场。由于我第一场已经晋级，第二场看不到题目了，所以就借lch的账号读了读题。
这次的题目比较坑，全部是贪心题。第一题如果细节没有考虑清楚就会WA，第三题又是那种第一感觉就没思路的题目，不过lch最终还是第一题过了大数据，二三题过了小数据，以50分300多名的成绩进入Round2了。
A.Counter Culture
题目大意：
对一个数$i$，有两种操作：
- 将$i$加$1$
- 将$i$反转
问把$14变成$n$最少的步数是多少。
通过手动模拟，可以发现规律。
如果我们要达到的数是一个$k$位数，那么我们首先应该把$14变成一个$k$位数，之后再变到$n$。
而为了快速的增加位数，一个明显最优的策略就是将当前数的最后一位变成$9$，然后通过反转，把$9$放到前面，之后再不停的加$1$。
通过观察：$1 -> 19 -> 91 -> 109 -> 901 -> 1009 -> 9001$
我们发现， $901$ 变成$1009 -> 9001$，并不如变成$1099-> 9901$好。
那么我们可以得出第二个结论：在变到某个数时(位数相同),应该将这个数分成两半，先将当前数的后半段变成目标数的前半段反转之后的数，之后将当前数反转，然后将当前数变到目标数。
至此，总体思路已经有了，先不停地增加位数，直到位数相等，之后根据结论二，求出最终结果。
需要注意的是，如果目标数的最后一位是$0$，由于将位数增加够之后，第一位必然是$1$，因此无法达到末尾是$0$的情况，对这种情况，先将目标数减一正常求出结果，之后再加一。
另外，如果要求的是数前半段是$’1000’$的形式，则不需要反转。
B.Noisy Neighbors
题目大意：给出$r×c$的网格，在网格中选$n$个格子，使得这些格子相邻的边最少。
这也是一道贪心的题目。
首先我们可以发现，对格子进行黑白染色，如果$n \leq \frac{r*c}{2}$，那么通过只选一种颜色的格子，可以做到没有相邻的边。
如果$n > \frac{r*c}{2}$，贪心的策略是，分两种情况，一种是填满黑色的格子，之后选白色的格子填使答案最小，另一种是先填满白色的格子，之后选黑色的格子填使答案最小。
这两种情况中较小的那个即为答案。
当时以为只有优先填黑色格子才是最优的，然而发现按照这样做，样例都不对。于是就以为贪心是错的。没有想到分情况讨论……
C.Hiking Deer
题目大意：有一只鹿绕着一个圆走一圈，它可以在任意时刻改变速度为任意值。在这个圆上还有一些人，给出他们的初始位置(角度)，和走完一圈的时间，这些人会永远在这个圆上走。问这只鹿在走一圈的过程中至少会有几次和人相遇。
这道题真的是一点思路都没有……如果我比赛中遇到的话也是只能写写有两个人的时候的小数据。
后来看官方的analysis，才明白是如何贪心的。
首先，我们可以发现，鹿并没有必要在中途改变速度。
那么我们先考虑一个人的情况。如果鹿跑的足够快，在人到达原点之前就走完了一圈，那么他和人相遇的次数为1，如果它跑的慢了一点，在人第一次到达原点和第二次到达原点之间跑完一圈，那么它就不会与人相遇，如果它再慢一点，在人第二次到达原点和第三次到达原点之间跑完一圈，那么它还是会与人相遇一次，如果再慢，就是两次、三次，以此类推。
基于此，我们可以通过计算所有人到达原点的时间，对这个时间进行排序，之后枚举鹿到达原点的时间，如果鹿是第一次和这个人相遇，则减少一次相遇次数，之后每次相遇都增加一次相遇次数。在这个过程中取最小值即可。
这个算法ans的初始值为n，它的含义是，鹿最开始以极短的时间跑完一圈，超过了所有人。
由于每个人只会有一次减一的操作，之后的全都是加一，因此在$ans$大于$2×n$之后就没有必要继续找了。
排序可以用set，每个人每次只往set里添加他当前到达原点的时间，在把它取出来之后再将这个时间加上这个人跑一圈的时间放入set中。