10/12拼多多笔试题解
t1:逆天完了,题意不清,样例极弱,至少浪费一小时。只要起点不被卡住并且连续空位长度>=2即可(端点空位不需要判断)。
t2:枚举t的长度,t=s[1:len(t)]的01翻转
t3:双指针,对于主色,维护posr数组为每个主色向右连续一段的长度,若[l,r]为最短符合条件的区间且r+1为主色,答案加上posr[r+1]-r+1
t4:暴力模拟拿60分跑路
正解(似乎有更简单的方法):
座位有n个,第i个有心情值h[i] 人有m个 玩l轮 val[i]数组为第i人的心情,max(val)的下标
n>=m时可以特判
n<m时,显然有循环节m(因为极端数据n,m可以互质,这里不考虑公约数了),将l规约至小于等于m
这里给出m轮的解法,<m同理,原问题与以下等价(方便起见下标0开始):
val数组长度为m,h数组长度为n,下标都从0开始,一开始pos=0,操作为:将数组h加到pos开始的数组val元素,即val[pos]+=h[0],val[(pos+1)%m]+=h[1]...以此类推,然后pos=(pos+n)%m,进行m次
设c[i]表示有c[i]次pos=i,也就是对于0<=k<m,c[k*n%m]+=1
那么val[i]=\sum_{a+b=i}{c[a]*h[b]},这是一个卷积形式,FFT即可
#笔试##拼多多#
t2:枚举t的长度,t=s[1:len(t)]的01翻转
t3:双指针,对于主色,维护posr数组为每个主色向右连续一段的长度,若[l,r]为最短符合条件的区间且r+1为主色,答案加上posr[r+1]-r+1
t4:暴力模拟拿60分跑路
正解(似乎有更简单的方法):
座位有n个,第i个有心情值h[i] 人有m个 玩l轮 val[i]数组为第i人的心情,max(val)的下标
n>=m时可以特判
n<m时,显然有循环节m(因为极端数据n,m可以互质,这里不考虑公约数了),将l规约至小于等于m
这里给出m轮的解法,<m同理,原问题与以下等价(方便起见下标0开始):
val数组长度为m,h数组长度为n,下标都从0开始,一开始pos=0,操作为:将数组h加到pos开始的数组val元素,即val[pos]+=h[0],val[(pos+1)%m]+=h[1]...以此类推,然后pos=(pos+n)%m,进行m次
设c[i]表示有c[i]次pos=i,也就是对于0<=k<m,c[k*n%m]+=1
那么val[i]=\sum_{a+b=i}{c[a]*h[b]},这是一个卷积形式,FFT即可
#笔试##拼多多#
全部评论
fft还是太吓人了,t4有更简单的解法的:每个人能坐的位置构成一个环,预处理出所有环的大小和每个环的权值前缀和,再枚举每个人,计算它能完成多少个完整的“环”,然后再利用前缀和计算不满一环的部分。复杂度O(n+m)
相关推荐
艾莉Alliy:+1,这场题面确实太💩了,提问功能还是摆设,问什么都只会回答“这是考试,独立作答”。那这提问是摆设吗?这两个题我都按两个不同的题意写了两份代码才成功通过

点赞 评论 收藏
分享
点赞 评论 收藏
分享