QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#358359 | #6829. It Takes Two of Two | crsfaa | WA | 1ms | 3956kb | C++14 | 1.6kb | 2024-03-19 19:24:10 | 2024-03-19 19:24:11 |
Judging History
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);
}
詳細信息
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'