09-23 21:24 门头沟学院 Java 发布于山东
关注
9.23 百度笔试
1. 模拟
给一个01串，可以进行两种操作
00->11,10->01
要求最后所有的0在1前面，求最小操作次数
思路：遍历数组，找最前面的1下标，记为l
n->l反序遍历，遇到01变成10，操作次数加1，遇到00变成11,操作一次加一，其他不变
遍历完即可
2. 异或前缀和
给一个数组a1~an，和查询l,r，求al-ar区域的k进制异或和tk,求max(tk)-min(tk)，k取值2-10
思路：维护S(j,k)表示0-j的k进制异或和，则tk = sub(S(r,k)-S(l-1,k),k)，sub表示不进位减法
遍历k即可
3. 二分
给定由CM组成的字符串s{1~n},记s{1~l-1}以及s{r+1~n}的c的个数，和s{l~r}的m的个数的最大值为t(l,r)
求 max{t(l,r)}
思路：维护前缀和 c{0~n}和m{0~n}表示前n个字符里c和m的个数
则 t(l,r) = max{c(n)-c(r)+c(l-1),m(r)-m(l-1)}
注意到, 固定l, c(n)-c(r)+c(l-1)-m(r)+m(l-1)是单调的，也就是r变动一下，要么c的个数变多，要么m的个数变少
利用二分求c(n)-c(r)+c(l-1)-m(r)+m(l-1)=0的r代入即为最小的t(l,r)
遍历l，二分找r，求t(l,r)的最大值即可
#牛客AI配图神器#
#百度笔试##笔试##秋招笔试记录#
给一个01串，可以进行两种操作
00->11,10->01
要求最后所有的0在1前面，求最小操作次数
思路：遍历数组，找最前面的1下标，记为l
n->l反序遍历，遇到01变成10，操作次数加1，遇到00变成11,操作一次加一，其他不变
遍历完即可
2. 异或前缀和
给一个数组a1~an，和查询l,r，求al-ar区域的k进制异或和tk,求max(tk)-min(tk)，k取值2-10
思路：维护S(j,k)表示0-j的k进制异或和，则tk = sub(S(r,k)-S(l-1,k),k)，sub表示不进位减法
遍历k即可
3. 二分
给定由CM组成的字符串s{1~n},记s{1~l-1}以及s{r+1~n}的c的个数，和s{l~r}的m的个数的最大值为t(l,r)
求 max{t(l,r)}
思路：维护前缀和 c{0~n}和m{0~n}表示前n个字符里c和m的个数
则 t(l,r) = max{c(n)-c(r)+c(l-1),m(r)-m(l-1)}
注意到, 固定l, c(n)-c(r)+c(l-1)-m(r)+m(l-1)是单调的，也就是r变动一下，要么c的个数变多，要么m的个数变少
利用二分求c(n)-c(r)+c(l-1)-m(r)+m(l-1)=0的r代入即为最小的t(l,r)
遍历l，二分找r，求t(l,r)的最大值即可
#牛客AI配图神器#
#百度笔试##笔试##秋招笔试记录#
全部评论
相关推荐
ahbt：又疯一个
点赞 评论 收藏
分享
09-23 20:50
门头沟学院 Java 点赞 评论 收藏
分享
投递百度等公司10个岗位 点赞 评论 收藏
分享
内向的柠檬精在研究求...：这不才9月吗，26到明年毕业前能一直找啊
，能拿下提前批，转正的，offer打牌的都是有两把刷子的，为什么非要跟他们比。如果别人是9本硕+金牌+好几段大厂实习呢？如果别人是双非通天代呢？如果别人是速通哥呢？，做好自己就行了，我们做不到他们一样提前杀死比赛，但晚点到终点也没啥关系吧
点赞 评论 收藏
分享