#创作计划# hack大大和2的乱搞做法
2025-09-08 14:44:36
发布于：广东
119阅读
0回复
0点赞
在审核作弊时，我发现很多人在“大大和2”这题使用了以下的乱搞做法。
乱搞做法 1：部分选择
- 指定一个数 （ 在 以内）。
- 对于每个 ，暴力判断所有 是否满足 。
时间复杂度 。
hack：
显然，我们只需要保证每个不符合题意的数的长度大于 即可。
那么我们可以设计这样的数据：
将整个数据分为 段，每段的区间为 。
然后我们将每段的第一个元素设置成任意一个大于前面一段除了第一个元素的所有元素之和的相反数，即 ，将后面的元素设置成任意负数，但是需要保证它们的和的相反数小于等于第一个元素，即 。
显然，这样所有段内都不会出现不符合题意的，而所有不符合题意的区间只能在段之间。
我们只需要保证每个段的长度大于 即可。
乱搞做法 2：最大子段和 + ？？分治
- 求出以 结尾的最大子段和。
- 当 且最大子段和 时，返回
NO。
注意到在官方数据下，WA 的只有小数据，所以套个小数据暴力即可。
时间复杂度 。
毫无逻辑，但是能过。
经过对拍，我发现分段也可以解决这个问题。
将整个数据分为 段，每段的区间为 。
然后我们将每段的第一个元素设置成前面一段除了第一个元素的所有元素之和，即 ，将后面的元素设置成任意负数，但是需要保证它们的和的相反数小于第一个元素，即 。
generator:
#include <iostream>
#include <iostream>
#include <cstdio>
#include <random>
#include <vector>
using namespace std;
mt19937 rng(114514);
void hack1(){
vector <int> v;
vector <int> sizes = {0};
for(int i = 1; i <= 10; i++){
sizes.push_back(rng() % 500 + 9000);
}
v.push_back(rng() % 10000000 + 900000000);
for(int i = 1; i <= 10; i++){
int tmp = v.back(), ct = 0;
for(int j = 1; j <= sizes[i]; j++){
int val = rng() % 1000 + 1;
if(tmp < ct + val) break;
ct += val;
v.push_back(-val);
}
v.push_back(rng() % (1000000000 - ct) + ct + 1);
}
cout << v.size() << '\n';
for(int i:v) cout << i << ' ';
cout << '\n';
}
void hack2(){
vector <int> v;
vector <int> sizes = {0};
for(int i = 1; i <= 10; i++){
sizes.push_back(rng() % 500 + 9000);
}
v.push_back(rng() % 10000000 + 900000000);
for(int i = 1; i <= 10; i++){
int tmp = v.back(), ct = 0;
for(int j = 1; j <= sizes[i]; j++){
int val = rng() % 100 + 1;
if(tmp <= ct + val) break;
ct += val;
v.push_back(-val);
}
v.push_back(ct);
}
cout << v.size() << '\n';
for(int i:v) cout << i << ' ';
cout << '\n';
}
int main(){
freopen("test.in", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cout << "4\n";
for(int i = 1; i <= 2; i++){
hack1();
hack2();
}
return 0;
}
output:
NO
YES
NO
YES
做法 1 全部输出 YES，做法 2 全部输出 NO。
有帮助，赞一个