楼主: 匿名
跳转到指定楼层
上一主题 下一主题
收起左侧

亚麻 2023 NG OA1 新鲜面经

 
🔗
Lewis111998 2022-8-12 07:52:58 | 只看该作者
全局:
这个是我的写法 用因数法写的 跑了几个testcase过了

本帖子中包含更多资源

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-HXVIP  2022-8-12 10:20:23
1~N的所有的数的正约数可在O(Nlog(N))的时间求得。

1~N中1的倍数有 N / 1 个
1~N中2的倍数有 N / 2 个
...
1~N中m的倍数有 N / m 个
...
1~N中N的倍数有 1 个

则总共是 N + N / 2 + N / 3 + ... + N / N  ~ Nlog(N)个
回复

使用道具 举报

🔗
Alan0314 2022-8-12 14:49:38 | 只看该作者
全局:
ginowan 发表于 2022-8-11 16:21
不用visited无法保证每个元素只被访问一次。你这样写似乎主循环里对每个i都进行了DFS,似乎是没有必要的 ...

这其实也是n^2的复杂度吧,假设全部是质数,那么你对n个元素都进行dfs,并且每个元素的dfs里进行一次for循环遍历
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-QKFXL  2022-8-13 10:35:06
Lewis111998 发表于 2022-8-11 16:52
这个是我的写法 用因数法写的 跑了几个testcase过了

[1,4,2] 应该返回-1?因为说了0<=a<b<c <=n-1,需要是按顺序放箱子
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-QKFXL  2022-8-13 10:37:32
Alan0314 发表于 2022-8-11 23:49
这其实也是n^2的复杂度吧,假设全部是质数,那么你对n个元素都进行dfs,并且每个元素的dfs里进行一次for ...

我也觉得是N^2,因为每个dfs里都有一个for循环来做division.
回复

使用道具 举报

🔗
Mortal 2022-8-13 13:33:49 | 只看该作者
全局:
Alan0314 发表于 2022-8-11 23:49
这其实也是n^2的复杂度吧,假设全部是质数,那么你对n个元素都进行dfs,并且每个元素的dfs里进行一次for ...

不过10^5以内只有不到10^4个质数, 所以不会到n^2 ref: https://primes.utm.edu/howmany.html
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-RCLFK  2022-8-15 07:52:56
好难一题
回复

使用道具 举报

🔗
reffocm 2022-8-20 05:06:08 | 只看该作者
全局:
第一题的operations是什么变量类型呀
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表