[NICA #1] 弹幕题解

· · 题解

本来想用这题写整活题解的。

整活题解

看到这题我们可以通过循环枚举检查某处能否成为安全点，只要找到即为答案，但是如果我们考虑最坏的情况，我们枚举到的每一个点都在弹道上，那么我们就要一直枚举，直到 n 条弹道都弄完了一遍，如此多的枚举次数，肯定要超时。

事实上只要数据巧妙无论你是正序、倒序、枚举奇数、枚举偶数、枚举质数都可以出现最坏的情况（如果出题人足够狡猾）！

我们可以换个思路，我们可以随机一个点检查！随机到每一个点的概率相等，通过数据范围可以发现对于每个点成功的概率极高！而随机让出题人无法预判你每个输出的数，轻轻松松就能通过！

关于为什么要用随机化思想（对重要结论的证明），举个例子：

有五十张卡片，你最多选三张，而有四张是红色的，其余是白色的，你希望得到白卡，你不知道某一张是红的或白的，也许你想到了一种选卡方式，比如选出第一张、第五张、第十四张，但是给你卡的人非常智慧，他预想到了你会使用一种定式获取卡片，于是提前在你想的三个地方放上了红卡，甚至让你多次重复这一操作，每一次的位置都不一样，这样无论如何都你选的位置都会出现三张红卡！

但你可以使用抛骰子的方式来决定你的选择，摆卡片的人并不能预判你的（骰子的）选择，事实上，他的摆法对你没什么影响，因为无论放在什么位置你取到红卡片的概率一致！此时只要你不是太非酋就能选出至少一张白卡片了。

注意：

代码：

#include <bits/stdc++.h>
using namespace std;
long long n;
long long o;
long long a[200010],b[200010],c[200010];
bool check(long long x){      //检查位置
    for(int i=1;i<=n;i++){
        if(x*x*x+a[i]*x*x+b[i]*x+c[i]==0){
            return 0;
        }
    }
    return 1;
}
int main(){
    srand(time(NULL));  //用时间当随机数种子
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i];
    }
    while(1){
        o=rand()%1000001; //取模，否则会超出输出范围限制
        if(check(o)){
            cout<<o;   //发现可行位置
            return 0;  
        }
    }
    return 0;
}