- 奶牛喝水
小朋友,你的随机化被卡了!
- @ 2026-9-20 13:20:27
有人在赛时使用随机分组的方法通过本题,以下为hack数据生成器:
#include<bits/stdc++.h>
using namespace std;
signed main(){
freopen("data.in","w",stdout);
cout<<198<<"\n";
for(int i=1;i<=195;i++) cout<<"1 1\n";
for(int i=1;i<=3;i++) cout<<"65 1\n";
return 0;
}
原理:
随机分组的正确性主要依赖于最终答案的分组两边元素个数相差不大。因此我们构造奇数个较大元素,就能使最终答案两边个数之差尽可能大。
这组数据中,合法的分组方式只有 种,即将个分在一组,或者将个和个分在一组。此时,随机分组的正确率约为。
2 条评论
-
Programming_Konjac LV 7 @ 2026-9-21 8:55:04
w不想写 dp 了想骗分来着qwq
😄 1🤣 1 -
@ 2026-9-21 8:48:01
吓哭了
- 1
信息
- ID
- 41
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 94
- 已通过
- 22
- 上传者