「申请添加 hack（含数据生成器），34 题解代码遭殃！」

申请添加 hack（含数据生成器），34 题解代码遭殃！

板块P1314 [NOIP2011 提高组] 聪明的质监员
楼主user100566
当前回复7
已保存回复7
发布时间2024/12/14 18:58
上次更新2024/12/14 21:20:38

被骇客银狼阻止的越权访问保存失败

申请添加 hack（含数据生成器），34 题解代码遭殃！

user100566楼主2024/12/14 18:58

根据题目给出的数据范围， $y$ 可能超过 $64$ 位有符号整数的表示范围，当然也超过了 $64$ 位无符号整数的表示范围。

考虑每个 $y_i$ ，乘号左边的最大值可达 $n=2\times10^5$ （ $w_j\ge W$ 全部成立），右边可达 $n*v_{max}=2\times10^{11}$ ，也就是说每个 $y_i$ 的最大值可达 $4\times10^{16}$ 。
同时 $m$ 最大可取 $2\times10^5$ ，这就意味着真实的 $y$ 值可达到 $8\times10^{21}$ ，远超 $64$ 位无符号整数的表示范围。

一种解决方法是在加 $y_i$ 的过程中剪枝，如果当前累计的 $y$ 达到某一阈值，则直接退出，这个阈值的最小值应为 $2s+1$ ，如果二分法比较巧妙可以是 $2s$ 。

hack 数据生成器

输入

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

const int n = 200000;
const int m = 200000;
const long long s = 1000000000000ll;

int main(){
	freopen("P1314.in", "w", stdout);
	cout << n << ' ' << m << ' ' << s << endl;
	for(int i=1; i<=n; ++i){
		cout << 1 << ' ' << 200000 << endl;
	}
	for(int i=1; i<=m; ++i){
		cout << 1 << ' ' << n << endl;
	}
	return 0;
}

输出

1000000000000

hack 成果

正解对比实例

应用剪枝可以过上述 hack 的代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long int64;

int n, m;
int64 s;
int w[200001], v[200001];
int l[200000], r[200000];

int sum1[200001]; int64 sum2[200001];

int64 check(int W){
	for(int i=1; i<=n; ++i){
		sum1[i] = sum1[i-1]+(w[i]>=W);
		sum2[i] = sum2[i-1]+(w[i]>=W?v[i]:0);
	}
	int64 res = 0;
	for(int i=0; i<m; ++i){
		res += (sum1[r[i]]-sum1[l[i]-1])*(sum2[r[i]]-sum2[l[i]-1]);
		if(res > (s<<1)) break;
	}
	return res;
}

int main(){
	scanf("%d %d %lld", &n, &m, &s);
	for(int i=1; i<=n; ++i) scanf("%d %d", w+i, v+i);
	for(int i=0; i<m; ++i) scanf("%d %d", l+i, r+i);
	
	int res = lower_bound((char*)1, (char*)1000000, 0, [](char& W, int _){
		return check(&W-(char*)0)>s;
	})-(char*)0;
	int64 error = min(s-check(res), check(res-1)-s);
	printf("%lld", error);
	return 0;
}