[学习笔记] $Maximum$ $Minimum$ $identity$

$Maximum$ $Minimum$ $identity$学习笔记

　　比较好玩的一个科技。具体来说就是$max(a,b)=a+b-min(a,b)$，这个式子是比较显然的，但是这个可以扩展到更多数字，比如说$max(a,b,c)=a+b+c-min(a,b)-min(a,c)-min(b,c)+min(a,b,c)$，其实就是容斥一下。这个东西的用处就是直接求$max$比较难求，转化成求$min$。

　　例题$1$： $bzoj$ $4036$。

　　首先根据$|$的性质，如果这一位有了$1$就会一直又下去，假设$t[i]$表示二进制下第$i$位变成$1$的时间，那么最后要求的其实就是$E[max(t[0],t[1],...t[n-1])]$，$E$就是期望。这个东西直接求是比较麻烦的，要把问题转化一下，利用$Maximum$ $Minimum$ $identity$，可以把原来的式子化简一下。这里举个简单的例子，比如说只有两位数，那么$E[max(t[0],t[1])]=E[t[0]]+E[t[1]]-E[min(t[0],t[1])]$，如何求$min(t[0],t[1])$呢?其实就是相当于第$0$位与第$1$位均没有变成$1$的期望时间，设集合$S$为全集减去$0,1$的集合，操作集合就是$S$的一个子集。然后根据公式期望时间$T=1/p$，$p$为概率。只需要y用$FMT$把一个集合的所有子集概率和算出来就行了，最后枚举一下状态，看一下$1$的个数来确定容斥系数，时间复杂度$O(2^n*n)$。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstdlib>

using namespace std;

const int MAXN = (1<<20)+5;

int n;

double p[MAXN],ans;

int main(){

	scanf("%d",&n);

	for(int i=0;i<(1<<n);i++) scanf("%lf",&p[i]);

	for(int i=1;i<=n;i++)

		for(int j=0;j<(1<<n);j++)

			if((j&(1<<(i-1)))) p[j]+=p[j^(1<<(i-1))];

	for(int i=0;i<(1<<n)-1;i++){

		if(p[i]>=1.0-1e-7) {puts("INF");return 0;}

		int now=__builtin_popcount(i);now=n-now;

		if(now&1) ans+=1.0/(1.0-p[i]);

		else ans-=1.0/(1.0-p[i]);

	}

	printf("%.10lf",ans);

	return 0;

}

　　例题$2$：$hdu$ $4624$

　　题目相当于给一个序列染色，首先可以利用上一道题的思路直接算，但时间复杂度是$O(2^n)$的。需要一个多项式时间复杂度的算法，自然而然能想到$dp$。我们把这个序列是否被染过色用一个$0/1$串表示，如果被染过则为$1$。我们发现其实需要的信息只有两条，一个是染过的奇偶性，这个用来确定容斥系数，还有一个是有多少个操作能操作到没被染过颜色的集合。设$f[i][0/1][j]$表示染到第$i$位，$0/1$表示为奇数还是偶数，$j$表示能操作到的没被染过色的集合。那么转移方程为$f[i][j][k]->f[l][j$ $xor$ $1][k+C_{l-i-1}^2 ]$。首先预处理出$f$数组，然后就可以计算期望$E[x]$，这就与上一题的计算方式差不多了，只需要枚举每一个状态，注意还要算上$x$这个点到枚举的终点这一段的区间。具体看代码，$hdu$需要保留$15$位小数，必须要写高精度，我懒得写了。。。时间复杂度$O(n^4)$。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

using namespace std;

const int MAXN = 55;

const double eps = 1e-8;

typedef long long LL;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}

	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return f?x:-x;

}

LL f[MAXN][2][MAXN*MAXN/2];

int n,T;

double E[MAXN];

int main(){

	f[0][0][0]=1;

	for(int i=0;i<=49;i++)

		for(int j=0;j<=(i*(i+1))/2;j++)

			for(int op=0;op<=1;op++)if(f[i][op][j])

				for(int k=i+1;k<=50;k++)

					f[k][op^1][j+(k-i)*(k-i-1)/2]+=f[i][op][j];

	for(int i=1;i<=50;i++)

		for(int j=0;j<=i;j++)

			for(int k=0;k<=(j+1)*j/2;k++)

				for(int op=0;op<=1;op++)if(f[j][op][k]){

					double p=(double)(k+(i-j)*(i-j+1)/2)/(i*(i+1)/2);

					if(p>=1.0-eps) continue;

					if(op) E[i]+=(double)f[j][op][k]/(1-p);

					else E[i]-=(double)f[j][op][k]/(1-p);

				}

	T=rd();

	while(T--){

		n=rd();printf("%.15lf\n",E[n]);

	}

	return 0;

}

巴特西

[学习笔记] $Maximum$ $Minimum$ $identity$

\(Maximum\) \(Minimum\) \(identity\)学习笔记

最新文章

热门文章