请求加强数据

P2572 [SCOI2010] 序列操作

rp_INF @ 2022-02-11 16:39:31

昨天@Cerisier 就提到过用暴力就能 AC，但暴力是 O(n^2) 的，不应该过。

随便搞组数据都能卡到 10 秒，例如下面的数据生成：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<1e5<<" "<<1e5<<endl;
    for(int i=0;i<1e5;i++)
        cout<<1<<" ";
    cout<<endl;
    for(int i=0;i<1e5;i++)
        cout<<4<<" "<<0<<" "<<1e5<<endl;
}

直接把暴力卡到了 25 秒（本地的运行结果）。。

by rp_INF @ 2022-02-11 16:39:53

@Cerisier

by Cerisier @ 2022-02-11 16:40:33

@rp_INF 是的

by Cerisier @ 2022-02-11 16:41:03

但是昨天有个别 xxs 直接贺我代码 AC 了，于是就删帖了。

by rp_INF @ 2022-02-11 16:41:32

所以@tiger2005 加强一下

by yurzhang @ 2022-02-19 17:09:12

@rp_INF hack 数据已经添加，感谢您的贡献~

另外，您的数据生成器生成的右端点超过了序列长度。

by rp_INF @ 2022-02-19 17:49:39

@yurzhang 数据生成器确实是有一些问题，谢谢您的指正

by rp_INF @ 2022-02-19 17:50:28

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<1e5<<" "<<1e5<<endl;
    for(int i=0;i<1e5;i++)
        cout<<1<<" ";
    cout<<endl;
    for(int i=0;i<1e5;i++)
        cout<<4<<" "<<0<<" "<<1e5-1<<endl;
}

上面这个才正确