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

CF1977E Tensor

题目大意:

有一个 \(n\) 个点的隐藏的有向图,保证所有的 \(i \to j\) 的边都满足 \(i < j\)
且对于任意的三点,至少有两个点 \(i < j\) 可以保证 \(i\) 能到达 \(j\)
你每次可以询问 \(i,j\) 表示询问 \(i\) 是否可以到达 \(j\)
在至多 \(2 \times n\) 次询问后,你需要将每个点 \(01\) 染色,使得颜色相同的两两可达。
\(n \le 100\)

解题思路:

首先根据 Dilworth 定理,最小链覆盖等于最大反链,而本题的最大反链显然最大为 2。
也就是我们一定存在一个合法的方案。

由于他保证所有的有向边都满足 \(i < j\),那么我们自然想到从小到大将数加进集合里。
如果我们遇到了一个只能加进一个集合的点,那么我们必须将他加进集合内。
可如果遇到了一个能加进两个集合的点,他可能会影响后面的点能否加入。

所以我们考虑将这些点特殊地放到一个新的集合内,表示两个集合都能放。
这样我们一旦遇到一个不能加入第三个集合的点,就将第三个集合中的点和当前点分开放并清空。

在发现做法的正确性不对的时候,可以去考虑我们期望代码的结果与实际哪里不同,为什么不同。
这也是修锅的一种方向。

http://www.gsyq.cn/news/1030.html

相关文章:

  • Code and Data Relocation in Zephyr
  • 模板
  • 【Kubernetes】 PVC 和 PV
  • Docker镜像
  • ROS2环境配置
  • windows项目下统计代码行数
  • ETF 简介
  • 2025年艺术、教育和管理国际学术会议(ICAEM 2025)- 第五期
  • reLeetCode 热题 100-1 两数之和-扩展1 unordered_map实现 - MKT
  • vue3 项目中优雅的使用 SVG 图标(vite-plugin-svg-icons)
  • ​​高压差分探头:高电压测量的精密之眼​​
  • 全国连锁贸易公司数字化管理软件-优德普SAP零售行业解决方案
  • Win7、WinServer2008运行.net8.net4.8程序的解决方案
  • [SQL] SQL Server 编写表脚本生成的SQL语句不包含索引以及触发器的解决方法
  • chrome高版本浏览器不兼容driver.execute_script(“return window.performance.getEntries()“)的解决方法
  • 【API接口】最新可用天翼云盘解析接口
  • TOR内置网桥失效 - Andy
  • PageHelper的使用
  • HarmonyOS实现快递APP自动识别地址
  • 基于 Rockchip 开发板的 openEuler 镜像的构建
  • 日期函数(mysql和oracle)
  • 图灵因果测试是由本框架(ECT-OS-JiuHuaShan)定义的下一代智能评估范式
  • QOJ 5357 芒果冰加了空气
  • 易路联合智享会权威发布,2025《AI技术如何重构人才获取全链路》
  • 个人使用IDEA经验总结
  • Redis数据持久化方案与集群部署
  • 物业管理小程序系统介绍
  • 快照同步思想
  • Windows-系统自动切换IPv4地址
  • sql嵌套查询