10-12 22:56 已编辑 浙江工业大学 golang 发布于浙江
关注
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即可
#笔试##拼多多#
全部评论
艾莉Alliy
吉林大学 C++
fft还是太吓人了，t4有更简单的解法的：每个人能坐的位置构成一个环，预处理出所有环的大小和每个环的权值前缀和，再枚举每个人，计算它能完成多少个完整的“环”，然后再利用前缀和计算不满一环的部分。复杂度O(n+m)
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
