1 条题解

  • 1
    @ 2024-7-14 22:32:14

    题目:here

    AC记录:here

    题意简述

    nn 个三次函数 y=x3+aix2+bix+ciy=x^3+a_ix^2+b_ix+c_i,现要求出任意一个正整数 mm 使得整点 A(0,m)A(0,m) 不在任意一个函数与 xx 轴的交点上,且 m106m \le 10^6

    思路:

    首先,如果你对三次函数有过了解,那么你会发现,一个三次函数会有 131\sim 3 个与 xx 轴的交点。

    若要求出函数所有零点,涉及的数学知识太多,我不会,我们暂时不予研究。

    换一种思路,遍历 xx 轴上每一个整点,逐个判断是否是函数与 xx 轴的交点。这种思路的时间复杂度是 O(n)O(n)

    但如果你试试 (就像我) ,你会发现,因为有 10610^6 的常数,有 44 个点会 TLE!虽说这样能够拿到 68 分,但这远远不是我们想要的。

    所以我们要优化这个代码。我们仍然遍历每一个点,但遍历的顺序改为随机,这样复杂度还是 O(n)O(n),但不会超时。这是因为在运行中,因为函数的交点最多有 2×105×3=6×1052\times10^5\times3=6\times10^5 个,所以每次随机至少有 40%40\% 的概率得到答案。

    代码实现:

    #include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<ctime>
    #include<set>
    using namespace std;
    typedef long long ll;
    const int maxx=0x3f3f3f,minn=-0x3f3f3f;
    int ans,n,a[222222],b[222222],c[222222];
    set<int>s;//这个集合用于标记随机访问是否访问过
    ll f(int x,int i){//第 i 个函数里目前 x 对应的 y,保险起见,开 long long
    	return x*x*x+a[i]*x*x+b[i]*x+c[i];
    }
    int main(){
    	srand(time(0));//随机种子设为时间才能真正做到随机
        cin>>n;
        for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]);
    	while(1){
    		ans=rand()%1000001;//取一个 0~1000000 范围内的随机整数
            bool flag=1;
            if(s.count(ans)) continue;//忽略被遍历过的位置
            s.insert(ans);//标记访问
            for(int i=1;i<=n;i++){//遍历每一条函数
                if(f(ans,i)==0){//判断是否在交点上
                    flag=0;
                    break;
                }
            }
            if(flag){//是解则输出
                cout<<ans;
                return 0;
            }
        }
        return 0;
    }
    

    记得给五星好评哦喵~ 谢谢客官啦~

    • 1

    信息

    ID
    349
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者