AT_agc020_f [AGC020F] Arcs on a Circle 题解

思路

看到题目数据范围，想到状压dp。

由于题目中的线段位置为实数，难以进行转移，我们需要对线段的端点坐标进行离散化。

那么要如何离散化才便于我们统计答案呢？假如我们要判断两条线段之间是否有重合部分，我们需要的数据是两个线段端点的坐标以及线段长度，线段长度为整数，思考一下，我们要如何记录坐标才能进行判断。

假如我们只记录坐标的整数部分，会出现因为小数部分二无法重合的情况，也就是说我们需要找一个高效记录小数部分的方法。

注意到，整数部分确定时，判断两个线段是否相交只需要知道端点坐标小数部分的大小关系，具体来说，将坐标离散化为 $n\times c$ 个点，其中 $c$ 代表圆周的总长度，$n$ 则是因为只有 $n$ 条线段，所以离散化后的小数部分只有 $n$ 种，虽然可能会出现端点重合的情况，但因为概率过小，可以忽略不计。

由于 $n$ 较小，我们可以直接 $O(n!)$ 枚举坐标之间的大小关系。

然后需要计算不同情况下的全覆盖方案数，先断环为链，将最长的线段放在开头（原因后文会说）。

然后进行状压dp，设 $dp_{i,j,s}$ 表示放置完线段左端点在 $i$ 前的线段，右端点最多到达 $j$，线段使用集合为 $s$ 的方案数，转移即为：

$$dp_{i+1,\min(n\times c,\max(i+a_p\times n)),s\cup p}\leftarrow dp_{i,j,s}$$

$p$ 为当前枚举到的线段。

设全部线段集合为 $S$，则最后答案为：

$$\frac{\sum dp_{n\times c,n\times c,S}}{c^{n-1}(n-1)!}$$

此处为 $n-1$ 是因为固定了长度最长的线段，不过注意坐标离散化必须把所有线段都算上。

关于断环为链必须将最长的线段放在开头的原因是如果开头的线段不是最长，则有可能出现以下情况

有的线段在末尾覆盖了开通的空隙，但在实际dp中会直接忽略超过结尾的线段部分，所以要把最长的线段防在开头来避免这种情况。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,c,a[7];
ll dp[310][55];//滚动数组优化 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>c;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	double ans=0;
	ll cnt=0;
	while(114514){
		memset(dp,0,sizeof(dp));
		dp[a[n]*n][0]=1;//初始将最长的线段放在开头 
		for(int i=1;i<=c*n;i++){
			int p=i%n;
			if(p==0)continue;//跳过放置最长的线段 
			for(int j=i;j<=c*n;j++){
				for(int s=0;s<(1<<n-1);s++){
					if(!((s>>p-1)&1))dp[min(c*n,max(i+a[p]*n,j))][s|(1<<p-1)]+=dp[j][s];//转移 
				}
			}
		}
		ans+=dp[c*n][(1<<n-1)-1];cnt++;//统计答案 
		if(!next_permutation(a+1,a+n))break;//找下一个排列 
	}
	printf("%.13lf",ans/pow(c,n-1)/cnt);//输出答案，记得保留至少11位 
	return 0;
}

标签: 状压DP, 神奇套路.

这道题的做法感觉很经典, 又或者说很套路, 然而我只做过一道这种套路的题;)

首先断环为链, 以最长的弧的起点作为链的起点(同时也是链的终点), 由于将环的的问题转化为了线段的问题, 下面将弧描述为线段.

然后由于坐标的连续性为求解带来的困难, 我们需要将坐标离散化, 套路化的方法是将坐标 $x$ 分为整数部分 $a$ 和小数部分 $b$ , 对小数部分进行离散化(不知道这么表述是否准确).

试图揣摩一下这么离散化的思路: 本题研究的是线段相交的问题, 这个涉及到这两弧端点之间的坐标差. 更深入地, 由于线段的长度为整数, 两线段相交只与坐标整数部分的数值和小数部分的相对大小有关, 即我们不在乎小数部分的具体数值, 故将其离散化(整数部分本身具有离散性, 不需要特别处理).

也就是说, 如果线段的长度是没有特殊性质的实数这么离散化就不行了.

离散化之后, 坐标变为 $nc$ 个, 这个问题就可以比较容易的解决了. $\mathcal O(n!)$ 地枚举各个线段小数部分的相对大小, 然后状压Dp一下就好了.

具体的, 设 $f[i][j][s]$ 表示左端点坐标(离散化后的, 下同)不大于 $i$ 的线段已经放置完毕, 覆盖到的最大的坐标为 $j$ , 线段的是否放置的状态为 $s$ 的方案数. 转移就枚举是否以 $i$ 为左端点放置线段 $x$ , 这样分别转移到 $f[i+1][j][s]$ 和 $f[i+1][max(j,to[x][i])][s\cup\{x\}]$ , 其中 $to[x][i]$ 表示在以 $i$ 为左端点放置 $x$ , $x$ 右端点的坐标. 注意由于我们限定了小数部分的相对大小, 每一处可以放置的线段 $x$ 只有一条, 所以转移是 $\mathcal O(1)$ 的.

时间复杂度 $\mathcal O(2^n\times n!\times(nc)^2)$.

#include <bits/stdc++.h>
using namespace std;
int read();
int n, c, l[51];
double f[502][102], res, cnt;
int main() {
    n = read(), c = read();
    for (int i = 0; i < n; ++i) l[i] = read();
    sort(l, l + n);
    while (1) {
        for (int i = 0; i <= c * n; ++i)
            for (int s = 0; s < (1 << n - 1); ++s) f[i][s] = 0;
        f[l[n - 1] * n][0] = 1;
        for (int i = 1, p; i <= c * n; ++i) {
            if ((p = i % n - 1) < 0) continue;
            for (int j = i; j <= c * n; ++j)
                for (int s = 0; s < (1 << n - 1); ++s)
                    if (~s >> p & 1)
                        f[min(c * n, max(j, i + l[p] * n))][s | (1 << p)] +=
                            f[j][s];
        }
        res += f[c * n][(1 << n - 1) - 1], ++cnt;
        if (!next_permutation(l, l + n - 1)) break;
    }
    printf("%.13lf\n", (double)res / cnt / pow(c, n - 1));
    return 0;
}

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : f, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}