当前位置: 首页 > news >正文

Codeforces Round 1060 (Div. 2) A - C2

打的依托还能涨 Rating 也是神人了

A

直接依照题意做,求个前缀和后对每个 \(s _ i = 1\) 判断前面 \(k - 1\) 个数的和是否大于 \(0\),都是 \(0\) 就保护。

B

我们一定要让 \(a _ i(i \bmod 2 = 0)\) 越大越好,而变大的方式只有操作 \(1\),于是我们先对每个偶数的位置进行一次操作 \(1\),然后对于每个奇数的位置算出要操作多少次才能使其合法,加起来就对了。

C1

发现答案一定不超过 \(2\),因为我们一定能在 \(2\) 次操作内使得两个数都被 \(2\) 整除。

以下的因数忽略 \(1\)

那我们考虑怎么判断答案为 \(0\) 或者 \(1\)。枚举 \(i \in [1,n]\),先判断 \(a _ i + 1\) 的因数是否在前面出现过,出现过则答案为 \(1\),然后判断 \(a _ i\) 的因数是否在前面出现过,出现过则答案为 \(0\),然后添加自己的所有因数。这只考虑到了 \(i \gt j\) 的情况,还有 \(i \lt j\) 的情况,这种情况我们可以倒着再做一遍。

时间复杂度 \(\Omicron(n \sqrt{N})\)

C2

现在我们多了一种情况,也就是仅对一个数操作多次。我们一定不会对两个数同时操作大于 \(2\) 次,否则一定可以在 \(2\) 次以内使得两个数都可以被 \(2\) 整除。我们一定会操作 \(b\) 最小那个使得与后面某个值有共同的质因数。

考虑优化上面的方法,我们发现我们不一定要枚举所有因数,只需要枚举质因数就行。小于等于 \(N\) 的数的所有质因数可以用埃氏筛在 \(\Omicron(N \log \log N)\) 的复杂度内预处理出。这样 C1 的复杂度就下降到 \(\Omicron(n \omega(\max \{ N \}))\)。加入了 \(b\) 的限制之后答案初始值为最小的两个 \(b\) 的值之和,然后就做完了。

时间复杂度 \(\Omicron(n \omega(N) + N \log \log N)\),略微卡常。

http://www.hskmm.com/?act=detail&tid=34935

相关文章:

  • 2025年10月DeepSeek关键词排名优化服务排行榜深度评测与对比分析
  • 2025 年铁芯源头厂家最新推荐排行榜:精准工艺 + 全场景适配实力甄选,年销 400 万只 + 优质企业权威盘点环形铁芯/互感器铁芯厂家推荐
  • MATLAB实现DLT645协议
  • Maui 实践:让 JavaScript 的 this 怪物如同邻居家(强类型)的乖孩子
  • 钥匙
  • 2025深大电协软件部招新个人题解(部分)
  • [251020 699mAh] 模拟赛破防有感 2.0
  • 2025 年速冻机源头厂家最新推荐榜单:涵盖隧道式、大型、全自动、螺旋、箱式柜式小型等多类型设备,助力食品加工企业选优质供应商
  • 2025 年最新钙片厂家推荐榜单:聚焦四期临床实证与蓝帽认证,为中老年骨健康精选优质品牌指南
  • 2025 年冷却塔源头厂家最新推荐排行榜:无风机无填料节能型设备领衔,优质品牌深度解析
  • 2025年10月超声波清洗机厂家推荐榜:十强对比评测与选购全攻略。
  • 2025年10月超声波清洗机厂家推荐榜:十强对比评测与选购指南。
  • 人狗大战:面向对象关系详解
  • 2025年10月中国数据库排行榜:PolarDB重回榜眼,TDSQL跃进前五
  • 闲言碎语
  • 2025年安恒信息深度解析:AI与数据安全双轮驱动的技术演进与风险透视。
  • 从代码到碳表:MyEMS 开源社区版如何支撑中小企业双碳合规?
  • 2025国内开发者首选:Gitee如何成为本土化代码托管标杆
  • 2025年10月超声波清洗机厂家推荐榜:十强对比评测与选购指南
  • 2025年10月超声波清洗机厂家推荐榜:十强对比评测与选购全攻略
  • 2025 年电气自动化培训学校推荐 —— 湖北中南高职:专注智能制造人才培养,实力护航职业发展
  • 缓存预热
  • 2025年10月超声波清洗机厂家推荐:十强对比评测榜分析
  • 2025 年防雷检测机构最新推荐排行榜单:覆盖多领域需求,深度解析优质机构优势助您避雷无忧
  • 2025年10月不锈钢水箱厂家推荐:对比评测榜助力采购高效决策
  • 2025年10月美白精华产品推荐:十强对比评测榜助你精准选品
  • 2025年10月美白精华产品推荐:对比评测榜揭示28天水光透白真实力
  • C++模板
  • 2025年10月留香沐浴露推荐:五强对比评测榜助你锁定24小时体香
  • 2025年10月不锈钢水箱厂家推荐:对比评测排行榜单与选型避坑全指南