hack 第一篇题解
查看原帖
hack 第一篇题解
353688
王熙文楼主2022/2/20 14:59

第一篇题解的做法是随机化,但我算了一下,我构造的数据有大于 0.9 的概率它这篇题解的代码会挂掉(

数据生成器:

#include<bits/stdc++.h>
using namespace std;

int main()
{
    // freopen("1.in","w",stdout);
    srand((unsigned)time(NULL));
    int n=10000; // 数据没开满,因为 x,y 的坐标受限制了
    cout<<n<<endl;
    for(int i=1; i<=4999; ++i) cout<<0<<' '<<i-1<<endl;
    for(int i=1; i<=4999; ++i) cout<<10000<<' '<<i+4998<<endl;
    cout<<1<<' '<<10000<<endl<<9999<<' '<<-1<<endl;
    return 0;
}

正解输出:199980005

第一篇题解输出:199940009

然而,第一篇题解的代码如果增加随机点的次数,能过当前数据范围,但其实,如果加大数据范围到 n106n\le 10^6,这篇题解不管在时间上或正确性上都会错。

2022/2/20 14:59
加载中...