题解：B3800 [NICA #1] 弹幕

· · 题解

简要题意

给出 n 个关于 x 的一元三次方程，求出任意一个整数 x 使其均不是这些方程的解。

主思路

作为一道正常的题，我们暴力枚举肯定不行，其复杂度显然过大。

这时我们能轻松地想到一种有点瞎搞的做法：随机化。

我们来分析一下其时间复杂度：

首先有一个数学上的常识：对于一个一元 k 次方程，其实数解最多有 k 个。那么对于此题的 3 次方程，每个方程最多有 3 个实数解。总共最多也只有 6\times10^5 个解。那么对于一个长度为 1000001 的区间，一个整数满足其均不是这些方程的解的概率实际上在 0.4 以上。平均算下来枚举 3 次左右就可以成功了。

但是本地调试和提交测评的时候要注意一些坑点：

rand() 在 Windows 系统中的值域为 0 至 32767，需要将两个 rand() 乘起来。

我们还需要强转一下 long long 再取模，因为 rand() 在 Linux 系统中的值域更大，乘起来会炸 int，所以如果想兼容 Windows 和 Linux 的话需要进行上述操作。

考虑到概率过小的超时，可以用 srand() 刷新一下运气，这样每次运行都极大概率能输出不相同的值。

其具体用法为在主函数中加上 srand((unsigned)time(0))。不过请添加上 ctime 头文件。

这样，当我们输入并存储完毕后，就可以随机枚举答案并验证，如果通过就直接输出，否则继续随机枚举。

下面附上代码。

#include<iostream>
#include<algorithm>
#include<ctime>
using namespace std;
#define int long long
int a[200005], b[200005], c[200005], n;
inline bool check(int ps) {
    for (int i = 1; i <= n; ++i)
        if (ps * ps * ps + a[i] * ps * ps + b[i] * ps + c[i] == 0) return 0;
    return 1;
}
signed main() {
    ios::sync_with_stdio(0);
    srand((unsigned)time(0));
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i] >> b[i] >> c[i];
    for (register int i = 1; i <= n; ++i) {
        int pos = rand() * 1ll * rand() % 1000000;
        if (check(pos)) {
            cout << pos << endl;
            return 0;
        }
    }
}