社区讨论

请求添加 hack，题解区几乎沦陷！

uuser100566
P8666[蓝桥杯 2018 省 A] 三体攻击参与者 10已保存回复 11

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@m5afvgbj
此快照首次捕获于
2024/12/30 10:47
去年
此快照最后确认于
2025/11/04 23:18
4 个月前
查看原帖

hack 数据

hack 输入

PLAIN
1 1 1 6
1000000000
1 1 1 1 1 1 1000000000
1 1 1 1 1 1 1000000000
1 1 1 1 1 1 1000000000
1 1 1 1 1 1 0
1 1 1 1 1 1 0
1 1 1 1 1 1 0

hack 答案

PLAIN
2

hack 输出 #1

PLAIN
6

hack 输出 #2

PLAIN
7

hack 原理

m≤106,ht≤109m\le10^6,h_t\le 10^9
在差分数组上某位置增加或减少的 hth_t 的总和可能溢出 int，例如上面的 hack 数据中，如果检查 ≥3\ge3 次攻击，则会由于 (1,1,1)(1, 1, 1) 位置连续加了 33 次 10910^9 溢出 int 变为负数，导致误判没有爆炸。
后面添加的攻击 1 1 1 1 1 1 0 是为了凑足 mm，防止二分法直接判断 22 次攻击，可以看出如果直接判断 22 次攻击的话则能正确判断出爆炸。
由于判断 33 次攻击时认为没有爆炸，因此正确答案 22 被排除到二分范围外，被 hack 程序检查后面的攻击时发现始终没有爆炸，因此输出 66 或 77，这取决于程序是否利用 保证一定存在这样的战舰。 来调整二分法。

被 hack 的题解

截止发帖，共有 1414 篇题解，其中有完整代码的共计 1111 篇，其中 88 篇题解代码不能通过 hack，22 篇能通过 hack 的代码不能 AC，仅有 11 篇题解代码能通过 hack 且 AC，甚至还是用的 #define int long long 才过的。
题解 #1
PLAIN
6
题解 #2
PLAIN
6
题解 #3
PLAIN
6
题解 #4
PLAIN
7
题解 #5
PLAIN
6
题解 #6
PLAIN
7
题解 #7
该题解代码虽然能通过 hack，但是不能通过本题已有的任何一个测试点。
评测记录，可以看到不仅 WA，而且严重超时。
题解 #8
PLAIN
6
题解 #9
该题解代码虽然能通过 hack，但是不能通过本题的测试点 #5 #6。
评测记录，可以看到测试点 #5 #6 WA。
题解 #10
PLAIN
7

对照代码

能通过 hack 的代码

评测记录
CPP
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int64;

int A, B, C, m;

vector<vector<vector<int> > > d;
vector<vector<vector<int64> > > damage;

int la[1000000], ra[1000000], lb[1000000], rb[1000000], lc[1000000], rc[1000000], h[1000000];

bool check(int attack){
	for(int i=0; i<A; ++i){
		for(int j=0; j<B; ++j){
			vector<int64>& subdamage = damage[i][j];
			for(int k=0; k<C; ++k){
				subdamage[k] = 0;
			}
		}
	}
	for(int i=0; i<attack; ++i){
		damage[la[i]][lb[i]][lc[i]] += h[i];
		damage[la[i]][lb[i]][rc[i]+1] -= h[i];
		damage[la[i]][rb[i]+1][lc[i]] -= h[i];
		damage[la[i]][rb[i]+1][rc[i]+1] += h[i];
		damage[ra[i]+1][lb[i]][lc[i]] -= h[i];
		damage[ra[i]+1][lb[i]][rc[i]+1] += h[i];
		damage[ra[i]+1][rb[i]+1][lc[i]] += h[i];
		damage[ra[i]+1][rb[i]+1][rc[i]+1] -= h[i];
	}
	
	for(int i=0; i<A; ++i){
		for(int j=0; j<B; ++j){
			for(int k=0; k<C; ++k){
				damage[i][j][k+1] += damage[i][j][k];
			}
		}
	}
	for(int i=0; i<A; ++i){
		for(int j=0; j<B; ++j){
			for(int k=0; k<C; ++k){
				damage[i][j+1][k] += damage[i][j][k];
			}
		}
	}
	for(int i=0; i<A; ++i){
		for(int j=0; j<B; ++j){
			for(int k=0; k<C; ++k){
				damage[i+1][j][k] += damage[i][j][k];
			}
		}
	}
	for(int i=0; i<A; ++i){
		for(int j=0; j<B; ++j){
			vector<int>& subd = d[i][j];
			vector<int64>& subdamage = damage[i][j];
			for(int k=0; k<C; ++k){
				if(subdamage[k]>subd[k]) return false;
			}
		}
	}
	return true;
}

int main(){
	scanf("%d%d%d%d",&A,&B,&C,&m);
	d.resize(A);
	for(int i=0; i<A; ++i){
		d[i].resize(B);
		for(int j=0; j<B; ++j){
			d[i][j].resize(C);
			vector<int>& subd = d[i][j];
			for(int k=0; k<C; ++k){
				scanf("%d", &subd[k]);
			}
		}
	}
	damage.resize(A+1);
	for(int i=0; i<=A; ++i){
		damage[i].resize(B+1);
		for(int j=0; j<=B; ++j){
			damage[i][j].resize(C+1);
		}
	}
	for(int i=0; i<m; ++i){
		scanf("%d%d%d%d%d%d%d",la+i,ra+i,lb+i,rb+i,lc+i,rc+i,h+i);
		--la[i];
		--ra[i];
		--lb[i];
		--rb[i];
		--lc[i];
		--rc[i];
	}
	int ans = lower_bound((char*)1, (char*)m, 0, [](char& attack, int _){
		bool res = check(&attack-(char*)0);
		return res;
	})-(char*)0;
	printf("%d", ans);
}

不能通过 hack 的代码

评测记录
将上面的代码的第 55 行 typedef long long int64; 改为 typedef int int64;，即将本应该使用 6464 位整数的地方改为使用 3232 位整数。
输出：
PLAIN
6

回复

共 11 条回复，欢迎继续交流。

正在加载回复...