四份代码只改变了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
*/