前言
Kickstart 2020 - Round B
暂时使用Python编程，后续也会用C++再实现一遍。
RoundB 地址https://codingcompetitions.withgoogle.com/kickstart/round/
上一轮解析：https://www.jianshu.com/p/61876e60403d
1. Bick Tour
给定一个列表，包含N个整数，找出其中极值的个数；极值定义为：大于相邻的左侧值和相邻的右侧值（不能是第一个元素/最后一个元素）
题解: 非常基础的做法，遍历就完事儿了
T=int(input())
for t in range(T):
N=int(input())
H=[int(_) for _ in input().split(' ')]
res=0
for i,h in enumerate(H):
if i<1:
continue
if h>H[i-1]:
if i+1<N and h>H[i+1]:
res+=1
print('Case #{}: {}'.format(t+1,res))
2. Bus Routes
题目大意：给定N个车站，D天，给定N个车站的发车间隔[X1,X2,...,XN]，（一个车站发车时间为 Xi,2Xi,3Xi,...，假设可以在同一天可以换乘多辆车）求在D天内完成对N个车站的顺序遍历下最晚出发时间。
题解：出发时间肯定为第一个车站发车间隔的整数倍，可以线性搜索整个答案空间，得到符合条件的最晚出发时间即可，判定符合条件的过程即对N个车站进行一次遍历计算，能否满足D天内完成遍历。
线性搜索肯定会超时，所以可以采用二分查找来提高算法效率： O(N log(D/X1))
T=int(input())
for t in range(T):
N,D=[int(_) for _ in input().split(' ')]
X=[int(_) for _ in input().split(' ')]
factor=X[0]
left=1
right=D//X[0]
def check(x):
days=x
#print('days:',days)
for _ in X:
#print('mode:',_%days)
if _%days==0 or days%_==0:
continue
if days>_:
days=(days//_+1)*_
# print('days>_',days)
else:
days=_
# print('days<_',days)
if days>D:
return False
#print('after days:',days)
#print('check ans:',True)
return True
ans=0
# while right>0:
# if check(right*factor):
# ans=right*factor
# break
# right-=1
while left<=right:
mid=(left+right)//2
#print(mid,left,right)
if check(mid*factor):
left=mid+1
ans=mid*factor
else:
right=mid-1
print('Case #{}: {}'.format(t+1,ans))
3. Robot Path Decoding
题目大意：
一个漫游者降落在一个新的行星上，这个行星可以被认为是一个由109根柱子组成的网格(从西到东从1开始编号)和109行(从北到南从1开始编号)。设(w，h)表示 w 列中的正方形和 h 列。漫游者从正方形开始(1,1)行动。
漫游者可以通过发送一个程序在行星表面移动，这个程序由一串字符组成，代表在四个基本方向上的移动。机器人按顺序执行字符串的每个字符：
N: Move one unit north.
S: Move one unit south.
E: Move one unit east.
W: Move one unit west.
还有一个特殊的指令 x (y) ，其中 x 是介于2和9之间的数字，y 是一个非空的子程序。这表示机器人应该重复子程序 y 总共 x 次：
2(NWE) is equivalent to NWENWE.
3(S2(E)) is equivalent to SEESEESEE.
EEEE4(N)2(SS) is equivalent to EEEENNNNSSSS.
因为这颗行星是一个环面，所以第一列和最后一列相邻，所以从第109列向东移动将移动探测器到第1列，从第109列向南移动将移动探测器到第1列。同样，从第一列向西移动将移动探测器到第109列，从第一列向北移动将移动探测器到第109列。给定一个程序，机器人将执行，确定最后的位置后，机器人完成了所有的运动。
题解：涉及嵌套的情况处理，可以使用队列/栈等数据结构进行处理：两种实现思路：
- 对于嵌套的子指令中的每个字符在遍历时直接计算其重复次数.(重复次数计算的地方导致计算量较大，Testcase2无法通过)
- 迭代计算每个子指令的移动距离，保存上一步的指令位置和当前子指令要重复的次数。 (AC)
from functools import reduce
T=int(input())
D=['N','S','E','W']
direction={'N':-1,'S':1,'E':1,'W':-1}
for t in range(T):
instr=input()
beg_x,beg_y=1,1
inclusive=[]
inclusive_mark=[]
loop=False
loop_dict={}
for i,_ins in enumerate(instr):
if loop:
if _ins=='(':
#inclusive_mark.append('(')
pass
elif _ins==')':
#inclusive_mark.append(')')
inclusive.pop()
if not inclusive:
loop=False
#break
else:
if _ins not in D:
inclusive.append(int(_ins))
continue
loop_dict.setdefault(_ins,0)
loop_dict[_ins]+=reduce(lambda x, y: x * y ,inclusive )
loop_dict[_ins]=loop_dict[_ins]%1e9
continue
# print(_ins)
if _ins not in D:
inclusive.append(int(_ins))
loop=True
else:
loop_dict.setdefault(_ins,0)
loop_dict[_ins]+=1
loop_dict[_ins]=loop_dict[_ins]%1e9
# print(loop_dict)
for key in direction:
loop_dict.setdefault(key,0)
loop_dict[key]=loop_dict[key]*direction[key]
end_x=beg_x+loop_dict['E']+loop_dict['W']
end_y=beg_y+loop_dict['N']+loop_dict['S']
print("Case #{}: {} {}".format(t + 1, int(1 + (end_x-1) % 1e9), int(1 + (end_y-1) %1e9)))
T=int(input())
direction={'N':(0,-1),'S':(0,1),'E':(1,0),'W':(-1,0)}
for t in range(T):
instr=input()
inclusive=1
inclusive_mark=[]
loop=False
loop_dict={}
pos=[1,1]
for i,_ins in enumerate(instr):
if _ins=='(':
continue
if _ins==')':
lastinc,lastpos=inclusive_mark.pop()
#print(lastinc,lastpos)
last=inclusive
inclusive=lastinc
lastpos[0]+=(last*pos[0])
lastpos[1]+=(last*pos[1])
pos[0]=lastpos[0]#%1e9
pos[1]=lastpos[1]#%1e9
elif _ins in direction:
pos[0]+=direction[_ins][0]
pos[1]+=direction[_ins][1]
else:
inclusive_mark.append((inclusive,pos))
inclusive=int(_ins)
pos=[0,0]
print("Case #{}: {} {}".format(t + 1, 1 + (pos[0]-1) % (10 ** 9), 1 + (pos[1]-1) % (10 ** 9)))
END
本人简书所有文章均为原创，欢迎转载，请注明文章出处 。百度和各类采集站皆不可信，搜索请谨慎鉴别。技术类文章一般都有时效性，本人习惯不定期对自己的博文进行修正和更新，因此请访问本人简书主页查看最新信息https://www.jianshu.com/u/40d14973d97c
网友评论