P4526 题解

· · 题解

鲜花：刚做这道题的时候，自学乱学了 \displaystyle\int_{0}^{80.33195401}x^2\mathrm{d}x 秒微积分的我以为这题能和 P4525 一样，推不定积分就能做，于是被此题爆切。

题意很清楚了，输入 a，计算 \displaystyle{\int_0^\infty x^{\frac{a}{x}-x}\mathrm{d}x}，若发散输出 \text{orz}，否则输出答案。

观察函数图象，不断改变 a 的值（a\in[-50,50]），可以发现：当 a<0 时，函数是发散的，而且不论 a 取何值，当 x>10 时， 函数值是趋于 0 的。也就是说，这个 \infty 的上限就是个纸老虎，你把它改成大于 10 的数也可以算，当然它要收敛。

关于这个 a<0 时函数发散，没有证明，我懒，而且我应该也不会证。（瞪眼法多好用啊。

做法如下：先套上辛普森公式：对于一个二次函数 f(x)=ax^2+bx+c，\displaystyle{\int_l^r f(x)\mathrm{d}x}=\dfrac{(r-l)[f(l)+f(r)+4f(\dfrac{l+r}{2})]}{6}（此公式的推导写在了文末）。

诶这题的函数也不是二次函数啊咋求啊？

我们这样考虑：假如有一段图象已经很接近二次函数的话，直接带入公式求积分，得到的值精度就很高了，不需要再继续分割这一段了。
于是我们有了这样一种分割方法：每次判断当前段和二次函数的相似程度，如果足够相似的话就直接代入公式计算，否则将当前段分割成左右两段递归求解。
现在就剩下一个问题了：如果判断每一段和二次函数是否相似？
我们把当前段直接代入公式求积分，再将当前段从中点分割成两段，把这两段再直接代入公式求积分。如果当前段的积分和分割成两段后的积分之和相差很小的话，就可以认为当前段和二次函数很相似了，不用再递归分割了。——OI-Wiki

总之就是将函数分割成多个与二次函数图象相似的部分进行计算，递归求解。

double asr(double l, double r, double eps, double ans, int step) {
    double mid = (l + r) / 2;
    double fl = simpson(l, mid), fr = simpson(mid, r);
    if (abs(fl + fr - ans) <= 15 * eps && step < 0)
    return fl + fr + (fl + fr - ans) / 15;
    return asr(l, mid, eps / 2, fl, step - 1) + asr(mid, r, eps / 2, fr, step - 1);
}

code

那坨辛普森函数是 Copy 自 OI-Wiki 的，因为我懒得打。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

double a;
double f(double x) {
    return pow(x, a / x - x);
}
double simpson(double l, double r) {
    double mid = (l + r) / 2;
    return (r - l) * (f(l) + 4 * f(mid) + f(r)) / 6;
}

double asr(double l, double r, double eps, double ans, int step) {
    double mid = (l + r) / 2;
    double fl = simpson(l, mid), fr = simpson(mid, r);
    if (abs(fl + fr - ans) <= 15 * eps && step < 0)
    return fl + fr + (fl + fr - ans) / 15;
    return asr(l, mid, eps / 2, fl, step - 1) + asr(mid, r, eps / 2, fr, step - 1);
}

double calc(double l, double r, double eps) {
  return asr(l, r, eps, simpson(l, r), 12);
}
void solve() {
    if (a < 0) puts("orz");
    else printf("%.5lf",calc(1e-10, 20, simpson(1e-10, 20)));
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> a;
    solve();

    return 0;
}

对辛普森公式 \displaystyle{\int_l^r f(x)\mathrm{d}x}=\dfrac{(r-l)[f(l)+f(r)+4f(\dfrac{l+r}{2})]}{6} 的推导：

设有函数 f(x)=ax^2+bx+c 和 F(x)，其中 \dfrac{\mathrm d}{\mathrm d x}F(x) = f(x)，a,b,c 为常数。

则有

\begin{aligned} F(x) &=\displaystyle{\int f(x)\mathrm{d}x}\\&=\displaystyle{\int ax^2\mathrm{d}x}+\displaystyle{\int bx\mathrm{d}x}+\displaystyle{\int c\mathrm{d}x}\\&=a\displaystyle{\int x^2\mathrm{d}x}+b\displaystyle{\int x\mathrm{d}x}+c\displaystyle{\int x^0\mathrm{d}x}\\&=a\dfrac{x^{2+1}}{2+1}+b\dfrac{x^{1+1}}{1+1}+c\dfrac{x^{0+1}}{0+1}+C\\&=\dfrac{a}{3}x^3+\dfrac{b}{2}x^2+cx+C\end{aligned}

其中 C 为常数。

所以

\begin{aligned}\displaystyle{\int_l^r f(x)\mathrm{d}x}&=F(x)|^r_l\\&=F(r)-F(l)\\&=\dfrac{a}{3}r^3+\dfrac{b}{2}r^2+cr-\dfrac{a}{3}l^3+\dfrac{b}{2}l^2+cl\\&=\dfrac{(r-l)[2a(l^2+r^2+lr)+3b(l+r)+c]}{6}\\&=\dfrac{(r-l)(2al^2+2ar^2+2alr+3bl+3br+c)}{6}\\&=\dfrac{(r-l)(al^2+bl+c+ar^2+br+c+al^2+ar^2+2alr+2bl+2br)}{6}\\&=\dfrac{(r-l)\{f(l)+f(r)+4[a(\dfrac{l+r}{2})^2+b(\dfrac{l+r}{2})+c]\}}{6}\\&=\dfrac{(r-l)[f(l)+f(r)+4f(\dfrac{l+r}{2})]}{6}\end{aligned}