题解 P5139 【z小f的函数】

· · 题解

又是一条暴力模拟 本蒟蒻已经被P3952时间复杂度虐惨

这道题实际上是关于数学和二次函数的题目，涉及到图像的变换问题。

乍一看，y=ax²+bx+c似乎令人无从下手，不过我们可以利用我们的数学知识，将函数变换成y=a(x-k)²+h，表示顶点为(k,h)的抛物线，因为：|a|全程不变

那么我们很容易得到k，h和a，b，c的关系:

k=-b/(2*a);
h=c-k*k*a;

接着就是各种移动：上下移改变h，左右移改变k。操作1和操作2都很简单

操作4：判断区间最大值和最小值：那么我们需要看看对称轴k在不在定义域内，还要看看开口向上还是向下，开口向上那么fkaojin是最小值，fyuanli是最大值，开口向下反之

操作5：判断2个函数有没有交点，很容易想到相减后判断det=b²-4ac。但是问题来了：我们已经把y=ax²+bx+c切换成了y=a(x-k)²+h，本蒟蒻本来是想不断更新两个函数，然后RE了两个点。那么：y=a(x-k)²+h和y=px²+qx+r两个函数相减，此时det是可以算出来的。本蒟蒻又耗费了一张草稿纸

det=(2*a*k+q)*(2*a*k+q)-4*(a-p)*(a*k*k+h-r);

最难的是变换3：旋转。把定点(k,h)绕着另一个点(p,q)旋转到(k',h')，我们可以利用对称性，计算出k',h'的数值：k=2*p-k，h=2*q-h;。这里有个坑点：开口方向要改变，也就是改变a=-a。所以本蒟蒻把变换3的代码放在了最后

最后，奉上自己精(bu)心(kan)打(ru)造(mu)的代码

#include <bits/stdc++.h>
using namespace std;
int T,n;
double a,b,c;//ax2+bx+c
double k,h;//ax2+bx+c转化为a(x-k)2+h 
double f(double x) //函数思想，方程转化为函数f(x)= a(x-k)2+h
{
    return a*(x-k)*(x-k)+h; 
}
int main()
{
//  freopen("1.hx902in","r",stdin);
//  freopen("3.hx902out","w",stdout);
    int i,j;
    scanf("%d",&T);
    while(T--)
    {

        scanf("%lf%lf%lf",&a,&b,&c);
        k=-b/(2*a);
        h=c-k*k*a;//ax2+bx+c转化成a(x-k)+h，注意：a可以一直使用，但b，c要转化 
        scanf("%d",&n);
        while(n--)
        {
            int tipic;//type好像是关键字所以我改一下 
            scanf("%d",&tipic);
            if(tipic==1)
            {
                double p;
                scanf("%lf",&p);//上移 
                h+=p;
            }
            if(tipic==2)
            {
                double p;
                scanf("%lf",&p);//左移 
                k+=p;
            }
            if(tipic==4)
            {
                double p,q;
                double fkaojin,fyuanli;//计算靠近点和远离点 
                scanf("%lf%lf",&p,&q); 
                if(k>=p&&k<=q)//对称轴在定义域内 
                    fkaojin=k;
                else //对称轴不再定义域内 
                {
                    if(fabs(k-p)>fabs(k-q)) fkaojin=q;
                    else fkaojin=p;//判断一下远离对称轴的点是哪个 
                }
                if(fabs(k-p)>fabs(k-q)) fyuanli=p;
                    else fyuanli=q;
                if(a>0)//注意开口方向 
                {
                    printf("%.2lf %.2lf\n",f(fkaojin),f(fyuanli));
                } 
                if(a<0)
                {
                    printf("%.2lf %.2lf\n",f(fyuanli),f(fkaojin));
                }
            }
            if(tipic==5)
            {
                double p,q,r;
                scanf("%lf%lf%lf",&p,&q,&r);//判断有几个根 
                double det=(2*a*k+q)*(2*a*k+q)-4*(a-p)*(a*k*k+h-r);
                if(det>=0) printf("%d\n",2);
                else printf("%d\n",0);
            }
            if(tipic==3)//这个是旋转，也是最难得，我草稿纸上画了很久才算出来 
            {
                double p,q;
                scanf("%lf%lf",&p,&q);
                a=-a;
                k=2*p-k;
                h=2*q-h;
            }
        }
        printf("%.2lf\n",h);
    }
    return 0;
}

多练习练习模拟，还是很好的。因为：万题可模。 NOIP2018D1T2一个背包问题在考场上硬是被我看做模拟然后搞了75分

最后推荐一道难度差不多的模拟题：P4711