2026-02-22 16:36:29
发布于：浙江
我严重怀疑这个题目测试点有问题
其他网址可以AC 这里就不行了？
代码如下
#include <bits/stdc++.h>
#define x first
#define y second
// #define int long long
#define double long double
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i32 = int;
using i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = __int128;
// using ldouble = long double;
using pii = pair<int, int>;
using pis = pair<int, string>;
const double eps = 1e-7;
const int N = 6e5 + 10, C = 30;
int n, q;
int a[N];
int f[N][C];
double sum[N][C];
double ans;
int getmax(int l, int r) {
int res = l;
for (int i = C - 1; i >= 0; i --) {
int w = 1 << i;
if (w <= r - l + 1) {
if (a[res] < a[f[l][i]])
res = f[l][i];
l += w;
}
}
return res;
}
void solve(int l, int r, int &x) {
if (l > r || ans < eps)
return ;
int pos = getmax(l, r);
if (l == r || a[pos] * 2 > x) {
ans *= (1.0 - 1.0 * a[pos] / x);
solve(l, pos - 1, x);
solve(pos + 1, r, x);
} else {
double res = 0.0, div = x;
for (int i = 1; i < C; i ++, div *= x)
res += (sum[r][i] - sum[l - 1][i]) / div;
ans *= exp(-res);
}
}
signed main() {
stdiossync_with_stdio(false);
std::cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
f[i][0] = i;
double t = a[i];
for (int j = 1; j < C; j ++, t *= a[i])
sum[i][j] = sum[i - 1][j] + t / j;
}
for (int j = 1; j < C; j ++)
for (int i = 1; i <= n; i ++)
if (i + (1 << j - 1) > n)
f[i][j] = f[i][j - 1];
else {
if (a[f[i][j - 1]] < a[f[i + (1 << j - 1)][j - 1]])
f[i][j] = f[i + (1 << j - 1)][j - 1];
else
f[i][j] = f[i][j - 1];
}
cout << fixed << setprecision(10);
while (q --) {
int l, r, x;
cin >> l >> r >> x;
ans = 1.0;
// cout << getmax(l, r) << ' ';
solve(l, r, x);
cout << 1.0 - ans << '\n';
}
return 0;
}
全部评论 4
还有，这才是正确的代码段
#include <bits/stdc++.h> #define x first #define y second // #define int long long #define double long double using namespace std; using ll = long long; using ull = unsigned long long; using i32 = int; using i64 = long long; using u32 = unsigned int; using u64 = unsigned long long; using u128 = __int128; // using ldouble = long double; using pii = pair<int, int>; using pis = pair<int, string>; const double eps = 1e-7; const int N = 6e5 + 10, C = 30; int n, q; int a[N]; int f[N][C]; double sum[N][C]; double ans; int getmax(int l, int r) { int res = l; for (int i = C - 1; i >= 0; i --) { int w = 1 << i; if (w <= r - l + 1) { if (a[res] < a[f[l][i]]) res = f[l][i]; l += w; } } return res; } void solve(int l, int r, int &x) { if (l > r || ans < eps) return ; int pos = getmax(l, r); if (l == r || a[pos] * 2 > x) { ans *= (1.0 - 1.0 * a[pos] / x); solve(l, pos - 1, x); solve(pos + 1, r, x); } else { double res = 0.0, div = x; for (int i = 1; i < C; i ++, div *= x) res += (sum[r][i] - sum[l - 1][i]) / div; ans *= exp(-res); } } signed main() { std::ios_sync_with_stdio(false); std::cin.tie(nullptr); cin >> n >> q; for (int i = 1; i <= n; i ++) { cin >> a[i]; f[i][0] = i; double t = a[i]; for (int j = 1; j < C; j ++, t *= a[i]) sum[i][j] = sum[i - 1][j] + t / j; } for (int j = 1; j < C; j ++) for (int i = 1; i <= n; i ++) if (i + (1 << j - 1) > n) f[i][j] = f[i][j - 1]; else { if (a[f[i][j - 1]] < a[f[i + (1 << j - 1)][j - 1]]) f[i][j] = f[i + (1 << j - 1)][j - 1]; else f[i][j] = f[i][j - 1]; } cout << fixed << setprecision(10); while (q --) { int l, r, x; cin >> l >> r >> x; ans = 1.0; // cout << getmax(l, r) << ' '; solve(l, r, x); cout << 1.0 - ans << '\n'; } return 0; }17小时前 来自 福建
0
有帮助，赞一个