关于double和long double 的精度
查看原帖
关于double和long double 的精度
126972
Kevinx楼主2024/10/25 09:36

四份代码只改变了long double , double 还有最后的 if(g[0] == 1.0) 和计算方式,为什么依旧爆精度?

WA*1 https://atcoder.jp/contests/abc189/submissions/59119931

#include<bits/stdc++.h>
#define ll int
//#define double long double
using namespace std;
const int N = 1e5 + 20;
ll n, m, k, a[N], cnt = 0;
int t;
bool flag[N];
double f[N], g[N];
double sumf, sumg;
int main(){
	cin >> n >> m >> k;
	cnt = k;
	a[0] = -1;
	for(int i = 1;i <= k;i++)
	{
		scanf("%d",&t);
		flag[t] = true;
	}
	sumg = g[n] = 0, sumf = f[n] = 0;
	for(int i = n-1; i >= 0; i--) {
		
		if(i+m+1 <= n) sumf -= f[i+m+1], sumg -= g[i+m+1]; 
		if(flag[i]){
			g[i] = 1.0, f[i] = 0.0, cnt--;
		}
		else {
			f[i] = 1.0*sumf*(1.0/(1.0*m))+1.0;
			g[i] = 1.0*sumg*(1.0/(1.0*m));
		}
		sumg += g[i], sumf += f[i];
	}
	if(g[0] == 1.0) {
		puts("-1");
		return 0;
	}
	double ans = 1.0*f[0]/(1.0-g[0]);
	if(ans < 1) printf("-1\n");
	else printf("%.10lf", ans);
	return 0;
}

WA*5 https://atcoder.jp/contests/abc189/submissions/59119978

#include<bits/stdc++.h>
#define ll int
using namespace std;
const int N = 1e5 + 20;
ll n, m, k, a[N], cnt = 0;
int t;
bool flag[N];
long double f[N], g[N];
long double sumf, sumg;
int main(){
	cin >> n >> m >> k;
	cnt = k;
	a[0] = -1;
	for(int i = 1;i <= k;i++)
	{
		scanf("%d",&t);
		flag[t] = true;
	}
	sumg = g[n] = 0, sumf = f[n] = 0;
	for(int i = n-1; i >= 0; i--) {
		
		if(i+m+1 <= n) sumf -= f[i+m+1], sumg -= g[i+m+1]; 
		if(flag[i]){
			g[i] = 1.0, f[i] = 0.0, cnt--;
		}
		else {
			f[i] = 1.0*sumf*(1.0/(1.0*m))+1.0;
			g[i] = 1.0*sumg*(1.0/(1.0*m));
		}
		sumg += g[i], sumf += f[i];
	}
	if(g[0] == 1.0) {
		puts("-1");
		return 0;
	}
	long double ans = 1.0*f[0]/(1.0-g[0]);
	if(ans < 1) printf("-1\n");
	else printf("%.10Lf", ans);
	return 0;
}

WA*3 https://atcoder.jp/contests/abc189/submissions/59119851

#include<bits/stdc++.h>
#define ll int
//#define double long double
using namespace std;
const int N = 1e5 + 20;
ll n, m, k, a[N], cnt = 0;
int t;
bool flag[N];
long double f[N], g[N], hf[N], hg[N];
long double sumf, sumg;
int main(){
	cin >> n >> m >> k;
	for(int i = 1;i <= k;i++)
	{
		scanf("%d",&t);
		flag[t] = true;
	}
	g[n] = 0, f[n] = 0;
	for(int i = n-1; i >= 0; i--) {
		if(flag[i]){
			g[i] = 1.0, f[i] = 0.0, cnt--;
		}
		else {
			f[i] = 1.0*(hf[i+1]-hf[i+m+1])*(1.0/(1.0*m))+1.0;
			g[i] = 1.0*(hg[i+1]-hg[i+m+1])*(1.0/(1.0*m));
		}
		hf[i] = hf[i + 1] + f[i];
		hg[i] = hg[i + 1] + g[i];
	}
	if(g[0] == 1.0) {
		puts("-1");
		return 0;
	}
	long double ans = 1.0*f[0]/(1.0-g[0]);
	if(ans < 1) printf("-1\n");
	else printf("%.10Lf", ans);
	return 0;
}

AC

#include<bits/stdc++.h>
#define ll int
using namespace std;
const int N = 1e5 + 20;
ll n, m, k, a[N], cnt = 0;
int t;
bool flag[N];
double f[N], g[N], hf[N], hg[N];
double sumf, sumg;
int main(){
	cin >> n >> m >> k;
	for(int i = 1;i <= k;i++)
	{
		scanf("%d",&t);
		flag[t] = true;
	}
	g[n] = 0, f[n] = 0;
	for(int i = n-1; i >= 0; i--) {
		if(flag[i]){
			g[i] = 1.0, f[i] = 0.0;
		}
		else {
			f[i] = 1.0*(hf[i+1]-hf[i+m+1])*(1.0/(1.0*m))+1.0;
			g[i] = 1.0*(hg[i+1]-hg[i+m+1])*(1.0/(1.0*m));
		}
		hf[i] = hf[i + 1] + f[i];
		hg[i] = hg[i + 1] + g[i];
	}
	if(g[0] == 1) {
		puts("-1");
		return 0;
	}
	double ans = 1.0*f[0]/(1.0-g[0]);
	if(ans < 1) printf("-1\n");
	else printf("%.10lf", ans);
	return 0;
}
/*
f[i] = f[j]+1/m
*/

2024/10/25 09:36
加载中...