饿了么笔试0908
T2
有一个机器人位于 (0,0) ，会根据一串只含 'L','R','U','D' 的指令移动，方向依次为左、右、上、下，对应的坐标变化为 (0,-1),(0,1),(-1,0),(1,0)【这个对应关系很坑】。对每组数据，机器人都会无限次重复指定直到碰到位于 (x,y) 的障碍物。请判断机器人是否会碰到障碍物，并相应地输出 YES 或 NO。
- 输入描述
第一行为一个整数 t 代表数据的组数
之后的每组数据，有两行输入，第一行两个整数 x y 代表障碍物坐标，第二行是指令序列
数据范围：指令序列长度为 n <= 100000，-10^9 <= x,y <= 10^9。
- 例
输入
2
-11 -5
UUL
2 0
LRUD
输出
YES
NO
分析
- 如果机器人在某次碰到障碍物，一定是经历了 m 遍指令 + k 次行动，
0 <= k < (指令长度) - 1 - 记机器人每完成一遍指令会位移 (dx, dy)
- 对于执行一遍指令的过程，把经过的所有点以集合的形式存下来。我们只需要看每个点能否在零次或多次 (dx, dy) 的位移后到达 (x, y) 即可
- 然而按这个思路写的代码只过了 13%，走过路过的大佬帮忙看看我哪里写得有问题orz
代码
dx = {"L": 0, "R": 0, "U": -1, "D": 1}
dy = {"L": -1, "R": 1, "U": 0, "D": 0}
t = int(input())
for i in range(t):
points = {(0, 0)}
x, y = [int(x) for x in input().split()]
x0 = y0 = 0
xt = yt = 0
s = input()
for si in s:
xt += dx[si]
yt += dy[si]
points.add((xt, yt))
# 此时的 xt, yt 就是每个周期的 x 轴位移和 y 轴位移
if dx == 0 and dy == 0:
# 执行一遍指令后回到原点，只要看 points 是否包含 (x, y)
if (x, y) in points:
print("YES")
else:
print("NO")
else: # 每个周期至少 x 和 y 中的一个会变化
for px, py in points:
if dx != 0:
# 每个周期的 x 会变化，用 x 的变化来计算每个点到达障碍物要几步
n = (x - px) // xt
else:
# 每个周期的 y 会变化，用 y 的变化来计算每个点到达障碍物要几步
n = (y - py) // yt
if (n >= 0) and (px + xt * n == x) and (py + yt * n == y):
print("YES")
else:
print("NO")
T3
给出一个长度为 n (n <= 100000) 的字符串，代表一个三进制的数。输出比它大且所有相邻位数的数字都不同的最小的三进制数。
- 例
输入
122
输出
201
分析
有点贪心的味道，我的方法过了 80%+
分了好几类讨论，最后的逻辑：
- 如果 x 长度为 1，直接打表输出
- 从左到右遍历，如果 x 本身有重复，处理第一处重复，后续用"01"循环填充，得到 f(x) 并输出
- 如果 x 本身没有重复，就把 x 的最后两位变成加一的结果（比如 12 变为 20）
- 此时如果 x 还是没有重复，直接输出
- 如果 x 重复了，输出 f(x)
