首页 > 字节跳动4月11日题解
头像
saipubw
编辑于 2021-04-11 21:47
+ 关注

字节跳动4月11日题解

A. 简单模拟即可,没什么好说的。注意可能有空格,因此需要getline而不能直接读入。
B. 开两个bool ar[1005][32]的数组,ar[i]代表字符串前i个字符组成的子串出现了那些字母。在回答查询之前先递推计算好ar,然后查询的时候做一下或运算即可。
C.
二分答案,每次测试答案是否大于等于k。
遍历所有数据,对每一本书,计算其哪些维度<k。然后直接查询这个维度下的最大值即可。一共有2^5=32个维度,先预处理这些维度就可以算出每个维度的最大值。
例如,现在有一本书是[1,3,2,4,5],还有两本书是[1,5,1,5,5]和[3,1,4,2,0],k=3。
对第一本书,第一个维度和第三个维度不满足条件。因此我们查询集合[1,0,1,0,0]的最大值。
集合[1,0,1,0,0],对第二本书是min(1,1)=1,对第三本书是min(3,4)=3,对第一本书是min(1,2)=1,因此集合[1,0,1,0,0]的最大值是3
3>=k。所以3是可能的答案。

不断二分,最后就可以确定答案。

最后需要注意需要存下两本书的位置。第一本书好确定,对第二本书,算出答案以后还要再扫一次。

二分复杂度为O(mnlogw),预处理集合的复杂度为O(m*2^m*n)。其中n为书的数量,w为输入数据的值域,m是维度数量
因此最终复杂度为O(mnlogw+m*2^m*n),本题n=w=1e5,m=5,因此算法可以在规定时间内计算完毕

D.注意到答案很简单,0<=ans<=20。提交20次试验出10组答案.接下来随机输出这十种答案即可。骗30分的概率大约是5.7%。疯狂提交,人品好的话甚至骗40分都有可能

全部评论

(3) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐