2个小时，4道编程题

1. 加减乘幂计算 10分 (AC)

要点

快速幂

python 取余不同于C，负数 % 正数 结果为正数，结果要求为负数，需要处理

2. 循环字符串 30分 (AC)

判断字符串是否为循环串，如果不是，返回字符串本身；如果是，返回长度最小的循环子串。

要点

与 LeetCode 459.重复的子字符串类似，首先用(s+s).find(s, 1) != len(s) 判断是否为循环串，如果结果为False，直接返回字符串本身，如果为True，继续计算最小循环子串：

e = s.find(s[0], 1)

while e != -1:

if s == s[e:]+s[:e]:

break

e = s.find(s[0], e+1)

print(s[:e]) # 肯定能找到e，即e必不为-1

3. 车站选址 30分 (0.3)

已知一些住户的在二维平面上的坐标，及一些车站的候选地址，从中选出车站的最优地址，使得该车站到所有住户的距离之和最小。距离定义为 ∣

x

s

−

x

p

∣

+

∣

y

s

−

y

p

∣

|x_s - x_p| + |y_s - y_p|∣xs​−xp​∣+∣ys​−yp​∣。

python 暴力搜索 30%

尝试两个轴单独考虑：

已知一个轴上有一些点，在轴上找出一点到其余所有点的绝对值距离最小。方法为：将这些点按坐标大小排序，如果总数为奇数，则目标点为排在中间的点；如果为偶数，则处在最中间两个点中间之间的范围内都可以。

实际解题时想成了偶数得位于两个点的中间，一直解答错误。最终提交了暴力搜的。

4. 无根树+状态翻转 30分(0.1)

给定无根树及各个节点的状态(正面或反面)，要求每次操作只能将某个节点及其连接的所有的节点的状态全部翻转，输出是否能够将无根树的所有节点的状态调整为反面(还是正面，记不清)。

不会，随机生成答案，10%。