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

AT_agc023_f [AGC023F] 01 on Tree

这题场上正着想了 3h+,发现需要用大 DS,果断弃疗了。

但是如果反着做会很好做。

首先你考虑到题目要求的限制本质上是什么,一个结点只能选完其所有祖先才能选这个点,但是我们发现这个限制过于强了,我们决定同时选。

同时选就是将每个结点向父亲结点合并,这样子一定是由祖先到叶子依次合并,依然满足条件。

考虑到两个连通块的合并,就是看 \(1\) 的个数和 \(0\) 的个数的比值,具体来说可以考虑 exchange argument,就很简单了。

然后每次选比值最小的合并到父亲结点处。

感觉这种题主要是要换方向,比如正着做换成同时做。

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

相关文章:

  • 智慧医疗的新基建:视频融合平台EasyCVR在医疗场景中的深度应用解析
  • 书虫私藏的免费阅读渠道大公开!
  • 智能工厂革命:Gitee PPM如何重塑企业级软件开发新范式
  • PyTorch图神经网络(三)
  • 2025年9月16日纸质证书 - 宋同学PostgreSQL管理员(中级)认证
  • C# 18天 029 依赖注入
  • ruoyi-vue列表显示关联
  • 自定义网关选择后端的微服务实例实现
  • VUE3切换页面时,页面没有加载
  • 河南农担数字化转型:破局农业金融困境的1037亿样本
  • 力扣55题 跳跃游戏
  • 2025年9月16日纸质证书 - 陈同学PostgreSQL管理员(高级)认证
  • MCP Registry 官方发布:Nacos 原生支持,借助 HiMarket 构建企业级私有 MCP 市场
  • 2025年9月16日纸质证书 - 李同学PostgreSQL管理员(高级)认证
  • 深度解析Playwright MCP:功能、优势与挑战,AI如何提升测试效率与覆盖率
  • C#驱动斑马打印机实现包装自动打印
  • AI 绘画增强版:AI 时代风口项目,助力轻松变现
  • 企业工商年报:企业与个体工商户工商年报专业代办服务详解
  • 使用 Playwright MCP 实现小红书全自动发布的完整流程
  • 美团饿了么霸王餐 CPS 系统:外卖流量变现新选择
  • 百家企业案例征集 | 让测试经验成为行业的共同财富
  • CentOS 7下载教程vmware虚拟机安装centos 7保姆级安装步骤(附安装包) - 教程
  • 数字孪生 + 区块链:MyEMS 引领能源管理技术融合新趋势
  • 实战章节:在Linux上部署各类软件
  • 27届春招备战一轮复习--第六期
  • 27届春招备战一轮复习--第七期
  • 备份一个简易队列写法
  • 【SPIE出版】第四届环境遥感与地理信息技术国际学术会议(ERSGIT 2025)
  • PyTorch和cude版本不兼容导致无法检测到GPU
  • 嵌入式系统arm高级系统调试技能-24./proc/slabinfo 记录解读与内存异常分析