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; }