QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#358359#6829. It Takes Two of TwocrsfaaWA 1ms3956kbC++141.6kb2024-03-19 19:24:102024-03-19 19:24:11

Judging History

你现在查看的是最新测评结果

  • [2024-03-19 19:24:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3956kb
  • [2024-03-19 19:24:10]
  • 提交

answer

#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
using Yukinoshita Yukino;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
double dp[205][205][205],f[205][205][205];//有x条非平凡链,y个孤点,z个二元链 
/*
非平凡链合并:4x^2,x-=1
非平凡链加孤点:4xy,y-=1
非平凡链加二元链:8xz,z-=1
孤点加孤点:y^2-y, y-=2,z+=1
孤点加二元链:2yz,x+=1,y-=1,z-=1
二元链合并:4z^2-4z,x+=1,z-=2 
*/
int main()
{
	int n=read(),x,y,z,sum;
	double ans=0;
	f[0][n][0]=1;
	for(sum=n;~sum;sum--)
		for(x=0;x<=sum;x++)
			for(y=0;x+y<=sum;y++)
			{
				z=sum-x-y;
				if(!(4*x*x+4*x*y+8*x*z+y*y-y+2*y*z+4*z*z-4*z))
				{
					ans+=dp[x][y][z]*f[x][y][z];
					continue;
				}
//				cout<<x<<' '<<y<<' '<<z<<':'<<f[x][y][z]<<' '<<dp[x][y][z]<<endl;
//				cout<<x<<' '<<y<<' '<<z<<' '<<4*x*x+4*x*y+8*x*z+y*y-y+2*y*z+4*z*z-2*z<<endl;
				double fm=4*x*x+4*x*y+8*x*z+y*y-y+2*y*z+4*z*z-4*z,v=n*n/fm+dp[x][y][z],tp;
				if(x)
					tp=4*x*x/fm*f[x][y][z],dp[x-1][y][z]+=tp*v,f[x-1][y][z]+=tp;
				if(y)
					tp=4*x*y/fm*f[x][y][z],dp[x][y-1][z]+=tp*v,f[x][y-1][z]+=tp;
				if(z)
					tp=8*x*z/fm*f[x][y][z],dp[x][y][z-1]+=tp*v,f[x][y][z-1]+=tp;
				if(y>=2)
					tp=(y-1)*y/fm*f[x][y][z],dp[x][y-2][z+1]+=tp*v,f[x][y-2][z+1]+=tp;
				if(y&&z)
					tp=2*y*z/fm*f[x][y][z],dp[x+1][y-1][z-1]+=tp*v,f[x+1][y-1][z-1]+=tp;
				if(z>=2)
					tp=(4*z*z-4*z)/fm*f[x][y][z],dp[x+1][y][z-2]+=tp*v,f[x+1][y][z-2]+=tp;
			}
	printf("%.8lf",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3828kb

input:

1

output:

0.00000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

2

output:

2.00000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3768kb

input:

3

output:

8.25000000

result:

ok found '8.2500000', expected '8.2500000', error '0.0000000'

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3956kb

input:

4

output:

3.48148148

result:

wrong answer 1st numbers differ - expected: '11.3333333', found: '3.4814815', error = '0.6928105'