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 浙江

11-20 05:18

门头沟学院 C++

秋招几乎已经结束了，所以干脆把我之前的面试经历全部记录一遍，算是我的矫情吧。华为早在数周前就面完了，但是早在暑假期间就被某位天才少年的招聘的HR无情质问了一波，气得我差点想要怼回去，但“电子竞技，菜就是原罪”，想来招聘时也是如此，于是深深感受到自己菜鸡的本质后，也不期望能够有多高的待遇了。早早就听说过华为的面试，听说优秀者会被加面，而我自己就三轮面试。三轮是同一天面试，连面三场，丝滑入池，虽然很累，但是面试体验不错，面试官人都挺好的。一面：项目拷打，拷打完之后就没时间了，于是出了一道算法题，华为是我共享屏幕，在本地写，有点始料未及。一道简单的排序后遍历的题目，我花了很多时间在文件重定向上。。。...

查看3道真题和解析

点赞评论收藏

分享

11-19 23:49

山东大学 Java

秋招期间，我真是快被问到崩溃了。

每个HR都问我：“你对职业生涯有什么规划？”我该怎么回答呢？我就是个小白，理想薪资3500，单休也行，只要能拿到offer，我什么都愿意尝试。如果我聪明点，能听懂人话，怎么会选这个专业？求求你们别再折磨我了！

牛客创作赏金赛

点赞评论收藏

分享

10-15 09:13

已编辑

天津大学 soc前端设计

简历已复活！！

某体面厂的地狱笑话被我碰到了笑死

7946163461：man，what can i say

点赞评论收藏

分享

11-08 17:36

诺瓦科技_HR

关于网络不实言论的声明函

#诺瓦星云求职进展汇总#

挣K存W养DOG：声明完是不是要调用了

诺瓦星云求职进展汇总

点赞评论收藏

分享

11-15 14:55

苏州大学数据产品

新同事不让我管她叫姐

入职第二天，我同龄的两个同事都叫她姐，她结婚生孩子了，我看那俩同事都叫她姐我就也叫了名字➕姐。然后她下班特意给我发微信说不用叫她姐。那我叫啥呀。。直接叫名字不冒犯吗。职级也是平级的。

牛客96541183号：叫老师😃

点赞评论收藏

分享

3 2 评论

全站热榜

正在热议

# 晒一晒我的offer #

9716130次浏览 104886人参与

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

39521次浏览 286人参与

# 北方华创开奖 #

21623次浏览 245人参与

# 地方国企笔面经互助 #

2220次浏览 6人参与

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

25056次浏览 233人参与

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

37111次浏览 65人参与

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

14467次浏览 205人参与

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

12034次浏览 58人参与

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

2429次浏览 32人参与

# 我的工作日记 #

20663次浏览 269人参与

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

14644次浏览 120人参与

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

57400次浏览 419人参与

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

24110次浏览 117人参与

# 公司情报交流地 #

31275次浏览 221人参与

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

7572次浏览 47人参与

# 实习，投递多份简历没人回复怎么办 #

2384813次浏览 34218人参与

# 00后45度躺现状 #

36553次浏览 305人参与

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

23390次浏览 121人参与

# 秋招OC许愿 #

224834次浏览 1857人参与

# 得物求职进展汇总 #

62946次浏览 664人参与

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

1513637次浏览 16943人参与

牛客网
牛客企业服务