【题解】 [AGC020F] Arcs on a Circle-北京尧图网络

https://www.luogu.com.cn/problem/AT_agc020_f看 Benny 的题解学会的有借鉴感谢巨佬。题目数据范围明显状压 dp。先计算有多少种放置方式能覆盖整个圆环再求概率也就是成功放置数 / 总放置数。线段位置为实数计算不方便考虑对线段的端点坐标进行离散化。由于线段长度必为整数判断两个线段是否相交只需要端点坐标小数部分的大小关系。将坐标离散化为 n×c 个点其中 c 代表圆周的总长度n 则是 n 条线段的大小关系关系之间的比较离散成点小数部分的位置。我们可以枚举坐标之间的大小关系。然后计算不同情况下的全覆盖方案数环不好处理考虑断环为链。以最长弧的起点为链的起点在此段的后面进行 dp。以下为断最长弧充要性的证明其他详见代码注释#includebits/stdc.h using namespace std; int n, C; // n:圆弧数量, c:圆周长度 int l[51]; // 存储每条圆弧的长度 double f[502][102]; // DP数组: f[位置][状态] double res, cnt; // res:成功方案数, cnt:总方案数 int main() { ios::sync_with_stdio(false); cin.tie(0); cin n C; for (int i 0; i n; i ) { cin l[i]; } // 排序使得最长的弧在最后 sort(l, l n); // 枚举除最长弧外其他 n - 1 条弧起点的小数部分相对顺序 while (1) { // 初始化DP数组 // f[i][s] 表示当前处理到位置i已放置的弧的状态为s时的方案数 for (int i 0; i C * n; i ) for (int s 0; s (1 n - 1); s ) f[i][s] 0; // 初始状态最长弧从位置 0 开始覆盖到 l[n-1]*n 位置 // 这里乘以 n 是为了离散化因为要区分小数部分的顺序 f[l[n - 1] * n][0] 1; // DP过程i表示当前处理到的离散化位置 for (int i 1; i C * n; i ) { int p i % n - 1; // p 表示当前位置对应的是哪条弧的起点位置 // i % n 确定小数部分的相对位置-1 得到弧的编号 if (p 0) continue; // j表示当前覆盖到的最远位置 for (int j i; j C * n; j ) { for (int s 0; s (1 n - 1); s ) { // 如果弧 p 还未被放置 if (((~s) p) 1) { // 放置弧p更新覆盖范围 // 弧 p 从位置i开始长度为 l[p]结束位置为 i l[p]*n // 但长度要乘以n以匹配离散化尺度 int new_j max(j, i l[p] * n); // 不能超过圆周长度 new_j min(C * n, new_j); // 转移状态 f[new_j][s | (1 p)] f[j][s]; } } } } // 统计成功方案覆盖到圆周末端且所有弧都已放置 res f[C * n][(1 n - 1) - 1]; cnt ; // 总方案数增加 // 改变下一种小数部分的相对顺序并且检查是否是最后一个排列 if (!next_permutation(l, l n - 1)) { // 下标 [0, n - 1] break; } /* 假设 n4l [2, 3, 5, 8]最长弧8在最后我们枚举前3个元素 [2, 3, 5] 的所有排列第1次: [2, 3, 5] 第2次: [2, 5, 3] 第3次: [3, 2, 5] 第4次: [3, 5, 2] 第5次: [5, 2, 3] 第6次: [5, 3, 2] 只有第6次 next_permutation 返回 false退出循环 */ } // 输出概率成功方案数 / (总方案数 * c^(n-1)) // 分母额外乘以 c^(n-1) 是因为每条弧的起点可以在圆周上连续移动 cout setprecision(13) res / cnt / pow(C, n - 1) \n; return 0; }

【题解】 [AGC020F] Arcs on a Circle

相关推荐

UE4 C++高效获取目录下蓝图类：资产注册表查询与性能优化实践

TMS320F280049C CMPSS配置实战：数字电源与电机控制的硬件保护核心

ePaper驱动板核心架构与选型指南：从硬件连接到软件调优

更多资讯

STM32 FOC中Y/Δ接法对SVPWM扇区判断与矢量合成的影响

数学建模pdf网盘资源

系统架构设计师知识点集锦PDF：高效复习与避坑指南

STM32嵌入式开发为何必须掌握QEMU仿真调试

科克罗夫特-沃尔顿发生器实战：从12V到330V高压倍压电路全解析

固态激光雷达选型：单线、多线与场景匹配指南

今日更新

Play Framework 迁移指南：移除 GlobalSettings，全面转向依赖注入（Scala 与 Java）

Numba 类型推断机制详解：从 Numba IR 到编译期类型重建的完整原理与实践

企业级项目dragonballz_e159-1的技术架构与实现方案

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？