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

CF Round 942(#1967) 总结

CF Round 942(#1967) 总结

A

\(cnt\)\(\min\{a\}\) 的个数,则答案为 \(cnt\times \min\{a\}+(n-cnt)\times (\min \{a\}+1)\)

于是把 \(K\) 尽量往小的补齐即可。

B1

存在整数 \(p\) 使得 \(a+b=p\times b\times \gcd(a,b)\)。移项得 \(\frac ab+1=p\times \gcd(a,b)\)

\(a\)\(b\) 的倍数,调和级数枚举再 \(O(\log n)\) check 即可,复杂度 \(O(n\log ^2n)\)

B2

\(d=\gcd(a,b),a=a'd,b=b'd\)。将原来的条件两边除以 \(d\),得到 \((a'+b')|(b'd)\),且要满足 \(\gcd(a',b')=1\)

有欧几里得定理,\(\gcd(a'+b',b')=\gcd(a',b')=1\),再由 \((a'+b')|(b'd)\) 所以只能是 \((a'+b')|d\)

那么 \(a'\le d=\frac a a'\le \frac na'\),所以 \(a'^2\le n\)。同样地,\(b'^2\le m\)

那么枚举 \(a',b'\) 计算 \((a'+b')\) 在范围内倍数的个数即可。复杂度 \(O(\sqrt {nm})\)

C

可以把每个点 \(a(0)\) 对其祖先 \(a(k)\) 的贡献拆开来,那么一个点对它的 \(dep\) 级祖先(从 \(1\) 开始)的 \(a(k)\) 贡献 \(a(0)\times \binom {dep+K-1}{K-1}\)

由于叶子始终是 \(a(0)\) 那么自底向上求出每个点的 \(a(0)\) 即可。由于树高是 \(O(\log n)\) 的,所以组合数可以暴力求,更新也可以暴力更新。

复杂度 \(O(n\log ^2n)\)

D

每个位置的修改都是独立的,我们只要使每个位置修改次数的最大值最小,考虑二分答案。然后贪心地,从前往后依次使每个 \(a\) 取到 \(mid\) 步内能取到的最小值,且要使 \(a_i\ge a_{i-1}\)

一种想法是求出 \(mid\) 步路径上的最小值,复杂度是两个 $\log $,难写且过不了。

考虑到 \(a_i\) 是不下降的,我们维护一个头指针 \(x\),每次把 \(x\) 往右移,check \((x,i)\) 是否 \(\le mid\) 即可。

要 check 是否在同一个基环树中并且树上是否是祖孙关系,\(O(m\log m)\) 预处理 LCA 即可。环上距离和书上距离都是容易的。

总复杂度 \(O((n+m)\log m)\)

E1 & E2

假如当前走到 \(b_i=at\),那么当 \(a_{i+1}=at+1\) 时,\(b_{i+1}=at-1\);否则 \(b_{i+1}=at+1\) 一定更优。所以每次往上走有 \(m-1\) 的系数,往下走有 \(1\) 的系数。走到 \(m\)\(-1\) 以后就不用走了。直接 DP 可以做到 \(O(nm)\)

考虑计算不合法的方案数,如果我们第一次走到了 \((i,-1)\),那么后面可以乱填 \(m^{n-i}\) 种,这其实等价于后面继续走,依然是往上走 \(m-1\) 系数,往下走 \(1\) 系数,求和后依然是 \(m^{n-i}\) 种。所以枚举最后走到 \((n,p)\) 计算走到过 \(y=-1\) 时的方案数。

  • \(p\le -1\) 时,一定会经过 \(y=-1\)
  • \(p>-1\) 时,利用类似格路计数的,反射一次转化为 \(p\le -1\) 的情况。

反射容斥。记 \(X\) 为碰到上边界,\(Y\) 为碰到下边界,\(f(S)\) 表示计算 \(S\) 作为实际状态的子序列时的方案数,要计算 \(f(Y)-f(XY)+f(YXY)-f(XYXY)+\cdots\)。计算一个点的方案数时,记向上走了 \(k\) 次,贡献为 \((m-1)^k\binom nk\)

发现反射后的各点其实是 \(p,-p+2m,p-2m-2,-p+4m+2,\dots\)。奇数项是 \(p\) 开头、公差 \(-2m-2\) 的等差数列,偶数项是 \(-p+2m\) 开头、公差 \(2m+2\) 的等差数列。代入到贡献里就是(以奇数项为例):

\[\sum _{k\ge 0} (m-1)^{(n+p-b)/2}\binom {n} {\frac {n+p-b+k(-2m-2)}2} \]

注意这里系数恒为 \((m-1)^{(n+p-b)/2}\),因为我们实际上还是走到 \((n,p)\)。我们可以维护 \(\sum c_i\binom{n}i\) 的系数 \(c_i\),上述贡献就是在 \(c\) 上每 \(m+1\) 间隔加上系数。用类似差分的方式处理,最后扫一遍 \(c\) 即可。复杂度 \(O(n+m)\)

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

相关文章:

  • 2025 热压机厂家权威推荐排行榜:深度解析 TOP3 优质厂家核心竞争力,最新选购指南发布
  • 2025 最新权威推荐!国内车床生产厂家 TOP 排行榜发布,聚焦数控 / 卧式 / 斜床身 / 重型等多类型设备优选这几家
  • .NET开发中3秒判断该用 IEnumerable 还是 IQueryable
  • 2025云南哪家旅行社好?昆明久游精品小团超舒适
  • 2025 年废气处理制造商最新推荐排行榜:权威盘点综合实力与服务能力,甄选行业优质品牌
  • 最想要的答案,一定不在备选项中
  • PaddleLabel百度飞桨Al Studio图像标注平台安装和使用指南(包冲突 using the ‘flask‘ extra、眼底医疗分割材料集演示)
  • 详细介绍:42.传输层协议TCP(上)
  • 2025 年国内电容品牌最新推荐排行榜:固态电容,高压电容,安规电容,CBB电容,超级电容等多品类优质厂商权威盘点,助力企业精准选型
  • 【光照】[PBR][法线分布]GGX实现方法对比
  • 【GitHub每日速递 250929】告别手动查资料!这两个开源项目(17.8k+星)让 AI 帮你做深度研究,报告自动生成
  • 订单模块
  • PS中如何让文字中两行文字实现左对齐且中间部分文字对齐
  • 告别复制粘贴!Chat2File-DeepSeek 让 DeepSeek 对话成果直接变“成品” - 指南
  • 详解 PHP 中的命名空间 Namespace 与 PSR4 自动加载
  • 构建易受攻击的AWS DevOps环境:CloudGoat场景实践
  • 摩尔线程88天过会,过会当天提交注册:看懂这3个关键,才算懂国产GPU的“生存逻辑”
  • 2025最新四面刨厂家权威推荐排行榜:四面刨厂家实力品牌测评,含定制,高速,重型四面刨优选指南
  • Java之泛型使用教程
  • 单调栈优化DP [ROI 2018] Decryption
  • 上海住宅新规调整,背后的野心可大了
  • 魔兽争霸3冰封王座安装包下载
  • vscode tunnel远程隧道访问 正确重启方法
  • PS时文本框图层如何与图片图层水平中心对齐
  • AI两周手搓一个进度管理神器,快来安排你的国庆假期吧
  • MX 练石 2025 NOIP #10
  • 读人形机器人26人类情感
  • 岐金兰AI元人文构想的全面系统研究——声明ai研究
  • Amazon Q Developer扩展安全漏洞分析与修复指南
  • 价值共生的语法革命:从“悬荡悟空”到“元人文构境”