题目：here

AC记录：here

题意简述

有 $n$ 个三次函数 $y=x^3+a_ix^2+b_ix+c_i$，现要求出任意一个正整数 $m$ 使得整点 $A(0,m)$ 不在任意一个函数与 $x$ 轴的交点上，且 $m \le 10^6$。

思路：

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

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

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

但如果你试试 （就像我） ，你会发现，因为有 $10^6$ 的常数，有 $4$ 个点会 TLE！虽说这样能够拿到 68 分，但这远远不是我们想要的。

所以我们要优化这个代码。我们仍然遍历每一个点，但遍历的顺序改为随机，这样复杂度还是 $O(n)$，但不会超时。这是因为在运行中，因为函数的交点最多有 $2\times10^5\times3=6\times10^5$ 个，所以每次随机至少有 $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;
}

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