2021-11-17 11:31 北京师范大学 C++

关注

牛客小白月赛39 D 绝望(线段树)

绝望

https://ac.nowcoder.com/acm/problem/228384

Description

alt

Solution

维护区间修改和区间质数个数，观察发现 $0 \leq x \leq 10$ ，区间操作是每个数字乘上当前下标的 $x$ 次方。

考虑先把原来的判断是否为质数，然后分类讨论：

$x = 0$ ，所有数字乘上 $1$ ，结果不改变
下标为质数，当前 $a_{i} = 1, x = 1$ , 那么乘上后改数字变为质数
剩下的操作都是让区间的数字变成非质数，做区间赋值为 $0$ 即可

使用一颗线段树维护质数个数和值为 $1$ 的个数

如果当前区间里没有 $1$ ，直接打 $t a g$ , 时间复杂度 $O (l o g_{2} n)$ ;
如果当前区间里有 $1$ , 继续往下找，最多会执行 $n$ 次找到叶子节点，这部分的复杂度是 $O (n l o g_{2} n)$ , 剩余的每次复杂度是 $O (l o g_{2} n)$

所以分析得到， $m$ 次操作下复杂度是 $O (n l o g_{2} n + m l o g_{2} n)$ 。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49408617&returnHomeType=1&uid=105308122

一些比赛的题解文章被收录于专栏

一些比赛的题解

全部评论

推荐最新楼层

湖南大学 C++

你真的一直在写题解啊. Hard work will finally pay off!

1 回复分享

发布于 2021-11-19 22:03

お茶の水女子大学 C++

提供一组hack 20 50 8 1 1 4 3 7 2 2 7 2 10 7 9 1 8 7 9 1 1 4 1 3 8 0 1 14 20 0 1 14 16 0 2 7 17 2 18 20 1 3 17 2 2 10 18 2 1 18 2 11 17 2 8 14 2 8 14 1 1 13 1 1 17 18 1 2 6 11 1 6 19 0 2 10 13 2 1 3 2 3 9 2 13 13 2 2 11 2 6 17 1 7 16 1 1 12 19 0 1 1 17 2 1 7 20 1 2 3 12 1 6 19 0 2 8 15 2 17 19 2 4 17 1 5 20 1 1 3 7 1 1 9 10 0 1 11 17 2 1 3 18 0 2 7 18 1 1 7 0 2 1 7 2 5 14 2 3 19 1 9 10 1 2 3 9 2 12 14 1 3 18 0 1 10 19 2 1 13 20 0 2 16 18 2 15 16 1 18 19 0 1 3 17 1

点赞回复分享

发布于 11-18 21:08 浙江

お茶の水女子大学 C++

原因是54行和59行所处的if语句中需要添加一句 t[rt].one = 0;

点赞回复分享

发布于 11-18 21:09 浙江

お茶の水女子大学 C++

答案 4 1 1 6 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

点赞回复分享

发布于 11-19 14:47 浙江

不愿透露姓名的神秘牛友

昨天 17:16

求帮选校招Offer：科大讯飞、金山办公

科大讯飞算法工程师 28.0k*14.0, 百分之三十是绩效，惯例只发0.9

点赞评论收藏

分享

11-19 17:15

华南农业大学运营

在楼梯睡觉被领导抓到

周一上班太困了，眼皮都睁不开，我就想躲在公司楼梯里悄悄睡一会，睡得正香呢，遇到老板出来抽烟，他站在楼梯口，我只能战战兢兢地蹲在那里，结果还是被领导看到了。

职场中你干过哪些“蠢”事

点赞评论收藏

分享

11-14 16:13

已编辑

重庆科技大学测试工程师

Amazarashi66：不进帖子我都知道🐮❤️网什么含金量

点赞评论收藏

分享

10-30 00:33

河北传媒学院算法工程师

这是真的吗？有无tju 的佬证明一下

牛客868257804号：九个中铁八个中建

点赞评论收藏

分享

今天 16:39

已编辑

华中科技大学光通信工程师

秋招就到这儿吧。

秋招真的是一场持久战，每一天都有不同的心情。。。 随着华为的审批保温，差不多整个秋招也就结束了。 BG：双九，保研，本硕都是电子信息类（光电方向），研究方向是光通信这一块。 秋招一共投递了17家公司，我的想法很明确，最后的最后的最后是希望能够做解决方案一类，也就是技术+销售结合的事儿。但这样的岗要求很高，基本很少校招，都是社招或内部研发输出一线这样的模式。所以我投递的岗包括技术岗和非技术岗。 收到面试邀请9家，获得offer（含保温）9家，已拿到8offer，预计9offer。面试通过率100%。所有的面经都在主页了，欢迎各位大佬指正批评。🙇 5月准备华为客经实习开始陆...

zachsun：华科硕士给13级？有点逆天了吧

25届秋招总结

点赞评论收藏

分享

3 2 评论

全站热榜

正在热议

# 25届秋招总结 #

239670次浏览 1958人参与

# 学历or实习经历，哪个更重要 #

40349次浏览 293人参与

# 北方华创开奖 #

22283次浏览 255人参与

# 地方国企笔面经互助 #

2424次浏览 6人参与

# 面试题刺客退退退 #

136455次浏览 2087人参与

# 选完offer后，你后悔学本专业吗 #

9235次浏览 68人参与

# 你最想要的公司福利是？ #

38833次浏览 99人参与

# 应届生被毁约被毁意向了怎么办 #

26285次浏览 236人参与

# 机械应届生薪资要多少才合适？ #

12259次浏览 59人参与

# 查收我的offer竞争力报告 #

15917次浏览 218人参与

# 一觉醒来，我觉醒了超级打工人系统 #

2693次浏览 32人参与

# 没有实习经历，还有机会进大厂吗 #

804403次浏览 13802人参与

# 你觉得第一学历对求职有影响吗？ #

14782次浏览 121人参与

# 我的工作日记 #

20971次浏览 270人参与

# 寒假躺平还是提前实习 #

57864次浏览 425人参与

# 秋招OC许愿 #

225747次浏览 1862人参与

# 秋招被确诊为…… #

53396次浏览 299人参与

# 总结:哪家公司面试体验感最差 #

25243次浏览 125人参与

# 不给转正的实习，你还去吗 #

1515617次浏览 16960人参与

# 公司情报交流地 #

31462次浏览 224人参与

# 机械人，签完三方你在忙什么？ #

23677次浏览 125人参与

牛客网
牛客企业服务