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

AtCoder ARC207 总结

AtCoder ARC207 总结

B

构造题。观察样例,发现 \(i\) 恰好三步到达 \(n-i\),其他点都是两步到达,这使我们想到 \(n\) 为偶数时的解法:分成 \(\le n/2\)\(>n/2\) 的两部分点,对于其中一部分,我们让一个点恰好两步到达恰好一个或两个点。而对于两部分之间的连边,我们让 \(n-i\) 连向 \(i\) 在它那一部分恰好两步到达的点,这样就使 \(n-i\) 恰好三步到达 \(i\),且不影响其他点。

对于 \(n\) 为奇数时的情况,可以把 \(n\) 号点拎出来,其他 \(n-1\) 做偶数的情况,发现只要使 \(n\) 号点能两步内到达所有点即可满足条件。画两下发现只需将 \(n\) 号点连向所有奇数点即可。

对于 \(n=6\)\(n=7\) 不能用上述方法构造,\(n=6\)\(1,2,3,6,5,4\) 的环;\(n=7\) 是在环的基础上将 \(7\) 连向 \(1,3,5\)。当 \(n<6\) 时无解。

C

考虑到固定 \(r\),那么只有 \(O(\log A)\) 个或值,且每种或值的左端点在一个区间 \([l_1,l_2]\) 内。

可以考虑对所有的 \(O(n\log A)\)\((l_1,l_2,r)\) 按照或值排序,相同或值按 \(r\) 排序。

然后依次执行每个 \((l_1,l_2,r)\) 对答案的更新,即 \(dp_r\gets \max _{i\in [l_1,l_2]}dp_i+1\)。用线段树维护,复杂度 \(O(n\log n\log A)\)

D

取出中心 \(4\times 4\) 的矩形然后跑暴力即可。

可以证明是对的,只要讨论 \(n,m\) 的不同奇偶性时的情况。

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

相关文章:

  • 2025.10.7模拟赛
  • 详细介绍:ZLG ZCANPro,ECU刷新,bug分享
  • 好好学习, 天天向上
  • 2.洋葱开发法
  • OpenStack搭建
  • OpenStack实验过程
  • 2025.10.7+7
  • oppoR9m刷Linux系统:VCOM模式备份系统与基带IMEI/NVRAM/QCN
  • 两个开源中国象棋引擎的编译
  • 推荐一款Swift开发框架- Aquarius
  • 1.如何导入Aquarius开发框架
  • 课程作业(10月8日)
  • 帮宣——可控核聚变
  • 浅谈导数
  • 洛谷P5304 [GXOI/GZOI2019] 旅行者(二进制分类技巧)
  • 英语_阅读_AI Robot_待读
  • 【C++】AVL树的概念及完成(万字图文超详解)
  • 打造自主学习的AI Agent:强化学习+LangGraph代码示例
  • 关于二分
  • NKOJ全TJ计划——NP11721
  • 印度全球能力中心2030年展望与技术基建规划
  • NOI Linux 食用教程
  • 详细介绍:基于 Android 和 JBox2D 的简单小游戏
  • 基于深度学习的语音识别高效的系统设计与实现
  • CF2152H2 Victorious Coloring (Hard Version) 题解
  • 题解:P6162 [Cnoi2020] 四角链
  • 题解:P3301 [SDOI2013] 方程
  • # 20232321 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 题解:CF1292E Rin and The Unknown Flower
  • 打印A3大小的PDF文件为A4幅面