ACM/ICPC 2013 杭州邀请赛复现

1010 Shaolin

题意

少林寺和尚上山需要比武，每个和尚具有id和武力值(k, g)。新和尚在比武时在已经上山的和尚中选择和自己武力值最接近的和尚比武（如果有两个就选择比自己弱的那个），现在给定和尚上山顺序，对于每个和尚计算应该和谁比武。

解答

模拟，考虑到set是自动排序的，因此可以使用两个set分别存正序和逆序，然后分别lower_bound，注意处理只有一个武力值最大/最小的情况。
代码

1009 Building bridges

题意

有一个m行n列的矩阵上有C岛H岛和O海洋。现在要在H和C之间建一个曼哈顿距离最短的桥。要求输出选择的H岛的坐标(x1,y1)和C岛坐标(x2,y2)，在曼哈顿距离相同的情况下依次按照x1, y1, x2, y2从小到大进行排序。

解答

直接爆搜O(n^2*m^2)。
代码

1001 Robot

题意

有一个1..n的环，从点1开始以均等概率逆时针或顺指针走w步，问进行m次操作后，停在[l,r]区间上的概率。

分析

这道题目是概率dp，假设在旋转次m时，落在环上每一点的概率可以由旋转m-1次的概率求得。
比较坑的地方是这题卡常数，我的一个算法用((((1 + x) % n) + n - 1) % n) + 1求wrap，多调用了几次mod就挂了。这也提醒我一般mod使用要注意，在我的笔记本电脑上测试1s能跑5.2e7次，乘法能跑1.6e8次。
代码