有人在赛时使用随机分组的方法通过本题,以下为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+22+2* (19565)195 \choose 65种,即将19519511分在一组,或者将656511226565分在一组。此时,随机分组的正确率约为2.41072.4*10^{-7}

2 条评论

  • 1

信息

ID
41
时间
1000ms
内存
256MiB
难度
7
标签
(无)
递交数
94
已通过
22
上传者