P8931 [入门赛 #10] Hack Problem P 题解

· · 题解

题目大意:

给定三个问题及解决这三个问题的代码，你需要出一组数据，使得代码出错。

这是一道 Hack 题，让我们一个一个问题来看吧！

  1. 求 x,y 的最小公倍数。

数据范围：1 \le x,y \le 10^9，且它们的最小公倍数也不超过 10^9。

分析：

注意到求答案时出现了 x * y，且它们均为 int 类型，于是我们可以使 x * y 爆 int 来使代码答案出错。

Code:

if(taskId==1)cout<<"1000000000 1000000000";
//因为两数的最小公倍数也不能超过10^9，所以最容易想到的方法就是使两数相等。
  1. T 组数据，每组数据给出一个长度为 n 且单调递增的数组，进行 q 次询问，每次询问该数组中有多少个数小于等于给定的数 x。

数据范围：1 \le T \le 3，1 \le n,q \le 10^5，1 \le x,a_i \le 10^9。

分析：

数组长度定义没有问题，因此无法使数组越界。

但是我们可以发现，在二分查找小于等于 x 的数的个数时，判断条件为 l < r，因此我们可以使一开始的 l 就等于 r，即给定一个长度为 1 的数组，然后询问一个大于等于该数的 x，此时函数会返回 0，即输出了错误结果。

Code:

if(taskId==2)printf("1\n1 1\n1\n2");
  1. T 组数据，每组数据给出一个长度为 n 的数组，进行 q 次询问，每次询问该数组中有多少个数小于等于给定的数 x。

数据范围：1 \le T \le 3，1 \le n,q,x,a_i \le 10^6。

分析：

这题的代码使用了桶排序 + 前缀和，因此普通的超时做法不可行。

但是我们可以发现，输入完一组数据后程序并没有重新初始化 b 数组，于是我们只需要构造两组一样的数据即可。

Code:

if(taskId==3)printf("2\n3 3\n4 4 5\n4 5 6\n3 3\n4 4 5\n4 5 6");

最后附上全部代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int taskId;
    cin>>taskId;
    if(taskId==1)cout<<1000000000<<' '<<1000000000;
    if(taskId==2)printf("1\n1 1\n1\n2");
    if(taskId==3)printf("2\n3 3\n4 4 5\n4 5 6\n3 3\n4 4 5\n4 5 6");
    return 0;
}