P8924 Perfect Math Class 题解

· · 题解

感谢GMOI，让我这个蒟蒻终于有一场公开赛能够250pts+。

我在的出题组（传送门，欢迎加入）曾有一个人在数学课上出过绘制函数图像的题目，甚至也是用 * 和 .，不过不是这样的多项式函数，而是输入解析式，这里不多说了。我看到这题感到莫名亲切，于是决定赛后来提交一篇题解（虽然我认为肯定过不了）。

根据函数的定义，我们知道，对于函数定义域内的任意 x，\operatorname{f}(x) 有且仅有一个与其对应的值，也就是说，在输出数据中，每一列最多只有一个点是 *，（也可能没有，\operatorname{f}(x) 的值域为 [0,m)，超出就不输出了）。于是我们就得到了一个很简单的做法，只要计算出 \operatorname{f}(x) 的定义域 [0,n) 中每个正整数 x 对应的 \operatorname{f}(x) 的值即可。

AC代码如下：

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,a[10],s[105];//s[i] 存储 x=i 时 f(x) 的值，超出值域则为 -1
long long f(long long x){//求 f(x) 的值
    long long t=1,sum=0;
    for(int i=0;i<=k;i++){
        sum+=t*a[i];
        t*=x;
    }
    if(sum<0||sum>=m)
        return -1;//出界改为-1 
    return sum;
}
int main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=0;i<=k;i++)
        scanf("%lld",&a[i]);
    for(int i=0;i<n;i++)
        s[i]=f(i);
    for(int i=m-1;i>=0;i--){//打印图像，注意 y 轴是从大到小的
        for(int j=0;j<n;j++){
            if(i==s[j])
                printf("*");
            else
                printf(".");
        }
        printf("\n");
    }
    return 0;
}

另外需要注意的是：不开 long long 见祖宗。

其实本题还有另一种做法。任意一元函数，可以看作某个二元方程的解集的映射，只要在输出每个位置时判断这个位置的 x 和 y 是否符合 y=\operatorname{f}(x) 即可。但这太浪费时间了，不TLE都对不起出题组。于是这个想法刚一萌生就被我摒弃。

本题解作者是个大蒟蒻，才上初一，CSP-J连初赛都过不了，难免有一些错误的地方，希望看到的大佬指正。