第二讲 二分与前缀和

数的范围

题目

给定一个按照升序排列的长度为n的整数数组,以及 q 个查询。

对于每个查询,返回一个元素k的起始位置和终止位置(位置从0开始计数)。

如果数组中不存在该元素,则返回“-1 -1”。

输入格式
第一行包含整数n和q,表示数组长度和询问个数。

第二行包含n个整数(均在1~10000范围内),表示完整数组。

接下来q行,每行包含一个整数k,表示一个询问元素。

输出格式
共q行,每行包含两个整数,表示所求元素的起始位置和终止位置。

如果数组中不存在该元素,则返回“-1 -1”。

数据范围

1
2
3
1≤n≤100000
1≤q≤10000
1≤k≤10000

输入样例:

1
2
3
4
5
6 3
1 2 2 3 3 4
3
4
5

输出样例:

1
2
3
3 4
5 5
-1 -1

思路

整数二分模板题。
在这里插入图片描述

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.Scanner;

public class Main {

static int[] q = new int[100100];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n,m;
n = sc.nextInt();
m = sc.nextInt();


for(int i = 0; i < n; i++) {
q[i] = sc.nextInt();
}

while(m-- > 0) {

int x = sc.nextInt();

int l = 0, r = n - 1;
while(l < r) {
int mid = (l + r) /2;
if(q[mid] >= x) {
r = mid;
}
else {
l = mid + 1;
}
}
if(q[l] == x) {
System.out.print(l + " ");
r = n - 1;
while(l < r) {
int mid = (l + r + 1) / 2;
if(q[mid] <= x) {
l = mid;
}
else {
r = mid - 1;
}
}
if(q[l] == x) {
System.out.println(l);
}
}
else {
System.out.println("-1 -1");
}
}
}

}

数的三次方根

题目

给定一个浮点数n,求它的三次方根。

输入格式
共一行,包含一个浮点数n。

输出格式
共一行,包含一个浮点数,表示问题的解。

注意,结果保留6位小数。

数据范围
−10000≤n≤10000
输入样例:

1
1000.00

输出样例:

1
10.000000

思路

实数二分。
要注意的点是当题目指出要保留多少位小数时,在计算时一般多指定两位参与运算。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.text.DecimalFormat;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

double n = sc.nextDouble();

double l = -10000d,r = 10000d;

while(r - l > 1e-8) {
double mid = (r + l) / 2;

if(mid * mid * mid < n) {
l = mid;
}
else r = mid;
}
System.out.println(new DecimalFormat("#.000000").format(l));
}

}

子矩阵的和

题目

输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1, y1, x2, y2,表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式
第一行包含三个整数n,m,q。

接下来n行,每行包含m个整数,表示整数矩阵。

接下来q行,每行包含四个整数x1, y1, x2, y2,表示一组询问。

输出格式
共q行,每行输出一个询问的结果。

数据范围

1
2
3
4
5
1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000

输入样例:

1
2
3
4
5
6
7
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

输出样例:

1
2
3
17
27
21

思路

二维数组前缀和模板题。

1
mg[i][j] += mg[i - 1][j] + mg[i][j] - mg[i - 1][j -1]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {

static int[][] row = new int[1005][1005];
static int[][] col = new int[1005][1005];
static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws Exception {
String line = sc.readLine();
String src[] = line.split(" ");
int n = Integer.parseInt(src[0]);
int m = Integer.parseInt(src[1]);
int q = Integer.parseInt(src[2]);

for(int i = 1; i <= n; i++) {
line = sc.readLine();
src = line.split(" ");
int j = 1;
for(String str : src) {

row[i][j] = Integer.parseInt(str);
col[i][j] = col[i - 1][j] + col[i][j - 1] - col[i - 1][j - 1] + row[i][j];

j++;
}
}
while(q-- > 0) {
line = sc.readLine();

src = line.split(" ");
int a = Integer.parseInt(src[0]);

int b = Integer.parseInt(src[1]);

int c = Integer.parseInt(src[2]);

int d = Integer.parseInt(src[3]);
System.out.println(col[c][d] - col[c][b - 1] - col[a - 1][d] + col[a - 1][b - 1]);
}
}
}

机器人跳跃问题

题目

机器人正在玩一个古老的基于DOS的游戏。

游戏中有N+1座建筑——从0到N编号,从左到右排列。

编号为0的建筑高度为0个单位,编号为 i 的建筑高度为H(i)个单位。

起初,机器人在编号为0的建筑处。

每一步,它跳到下一个(右边)建筑。

假设机器人在第k个建筑,且它现在的能量值是E,下一步它将跳到第k+1个建筑。

如果H(k+1)>E,那么机器人就失去H(k+1)-E的能量值,否则它将得到E-H(k+1)的能量值。

游戏目标是到达第N个建筑,在这个过程中能量值不能为负数个单位。

现在的问题是机器人以多少能量值开始游戏,才可以保证成功完成游戏?

输入格式
第一行输入整数N。

第二行是N个空格分隔的整数,H(1),H(2),…,H(N)代表建筑物的高度。

输出格式
输出一个整数,表示所需的最少单位的初始能量值。

数据范围
1≤N,H(i)≤10^5,

输入样例1:

1
2
5
3 4 3 2 4

输出样例1:

1
4

输入样例2:

1
2
3
4 4 4

输出样例2:

1
4

输入样例3:

1
2
3
1 6 4

输出样例3:

1
3

思路

二分答案。

二分初始能量值(即0-10^5),将每次得到的数带入题中所给的条件,看能否满足要求,不断地缩小答案数量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.Scanner;

public class Main {

static final int MAXN = 100005;
static long[] q = new long[MAXN];
static int n;

private static boolean check1(long mid) {
for(int i = 0; i < n; i++) {
if(q[i] > mid) {
return false;
}
}
return true;
}
public static boolean check(long mid) {

for(int i = 0; i < n; i++) {

if(check1(mid)) {
return true;
}
if(mid < q[i]) {
mid = mid - (q[i] - mid);
}
else {
mid = mid + (mid - q[i]);
}
if(mid < 0) {
return false;
}


}

return true;
}
public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

for(int i = 0; i < n; i++) {
q[i] = sc.nextLong();
}

long l = 0, r = MAXN;

while(l < r) {
long mid = (l + r) / 2;

if(check(mid)) {
r = mid;
}
else {
l = mid + 1;
}
}
System.out.println(l);
}
}

四平方和

题目

四平方和定理,又称为拉格朗日定理:

每个正整数都可以表示为至多 4 个正整数的平方和。

如果把 0 包括进去,就正好可以表示为 4 个数的平方和。

比如:

5=0^2+0^2+1^2+2^2

7=1^2+1^2+1^2+2^2

对于一个给定的正整数,可能存在多种平方和的表示法。

要求你对 4 个数排序:

0≤a≤b≤c≤d

并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法。

输入格式
输入一个正整数 N。

输出格式
输出4个非负整数,按从小到大排序,中间用空格分开。

数据范围

0<N<5∗10^6

输入样例:

1
5

输出样例:

1
0 0 1 2

思路

对于这样的题目,如果一开始找不出思路,那就开始想一个暴力的解法。

可以看到,任意找4个数使得它们的平方的和等于给定的数,首先想到的就是4个循环解决。

1
2
3
4
5
6
7
8
9
for(i = 0; ; i++) {
for(j = i; ; j++) {
for(t = j; ; t++) {
for(k = t; ; k++) {
i*i+j*j+k*k+t*t;
}
}
}
}

明显的会超出时间。

其实不妨这样想,假如现在已经求得了两个数的平方和了(记为a),那么另外两个数的平方和就是n-a=b。

b可以怎么求呢?

可以知道,如果a+b能够组成n,b一定要能够分成两个数的平方和,如果不能,那么说明组成a的两个整数不是答案。

提前算好b的每种可能组合,之后查找即可。

又因为只要字典序最小的答案,利用map的特性,只保存第一次组合即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

static int n ;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
Map<Integer,String> map = new HashMap<Integer,String>();

for(int i = 0; i * i <= n; i++) {
for(int j = i; i * i + j * j <= n; j++) {
if(!map.containsKey(i * i + j * j)) {
map.put(i * i + j * j, i + " " + j);
}
}
}
for(int i = 0; i * i <= n; i++) {
for(int j = i; i * i + j * j <= n; j++) {
int t = n - (i * i + j * j);
if(map.containsKey(t)) {
String ans = i + " " + j + " " +map.get(t);
System.out.println(ans);
return;
}
}
}

}
}

分巧克力

题目

儿童节那天有 K 位小朋友到小明家做客。

小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 N 块巧克力,其中第 i 块是 Hi×Wi 的方格组成的长方形。

为了公平起见,小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。

切出的巧克力需要满足:

形状是正方形,边长是整数
大小相同
例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大,你能帮小明计算出最大的边长是多少么?

输入格式
第一行包含两个整数 N 和 K。

以下 N 行每行包含两个整数 Hi 和 Wi。

输入保证每位小朋友至少能获得一块 1×1 的巧克力。

输出格式
输出切出的正方形巧克力最大可能的边长。

数据范围
1≤N,K≤105,
1≤Hi,Wi≤105
输入样例:

1
2
3
2 10
6 5
5 6

输出样例:

1
2

思路

二分答案。

二分正方形的边长,将枚举的边长带入看能否满足题目条件。不断缩小答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.Scanner;

public class Main {

static final int MAXN = 100000 + 5;
static int n, k;
static int[] H = new int[MAXN];
static int[] W = new int[MAXN];


public static boolean check(int mid) {

int cnt = 0;
for(int i = 1; i <= n; i++) {
cnt += (H[i] / mid) * (W[i] / mid);
}

if(cnt < k) {
return false;
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

n = sc.nextInt();
k = sc.nextInt();

for(int i = 1; i <= n; i++) {
H[i] = sc.nextInt();
W[i] = sc.nextInt();
}

int l = 1, r = MAXN;

while(l < r) {

int mid = (l + r + 1) / 2;

if(check(mid)) {
l = mid;
}
else {
r = mid - 1;
}

}
System.out.println(r);
sc.close();
}

}

K倍区间

题目

给定一个长度为 N 的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数,我们就称这个区间 [i,j] 是 K 倍区间。

你能求出数列中总共有多少个 K 倍区间吗?

输入格式
第一行包含两个整数 N 和 K。

以下 N 行每行包含一个整数 Ai。

输出格式
输出一个整数,代表 K 倍区间的数目。

数据范围

1≤N,K≤100000,

1≤Ai≤100000

输入样例:

1
2
3
4
5
6
5 2
1
2
3
4
5

输出样例:

1
6

思路

可以很容易的想到一个方法:枚举一段区间,求得这段区间和,能整除k即是一个答案。而快速求区间和可以利用前缀和算法。

很快的写出暴力解法:

1
2
3
4
5
6
7
for(len = 1; len <= n ; len++) {
for(i = 1; i <=n ; i++) {
if((arr[i + len - 1] - arr[i - 1]) % k == 0) {
ans++;
}
}
}

其中arr为前缀和数组。
推导算式

1
2
3
4
5
(arr[i + len - 1] - arr[i - 1]) % k == 0

(arr[i] - arr[j]) % k == 0

arr[i] % k == arr[j] % k

说明,在前缀和数组中,只要后面的数模k余数与前面的数模k余数相等,即满足答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.Scanner;

public class Main {

static final int MAXN = 100000 + 5;
static int n,k;

static long[] q = new long[MAXN];
static long[] p = new long[MAXN];

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
long ans = 0;
for(int i = 1; i <= n; i++) {
q[i] = sc.nextInt();
q[i] = (q[i - 1] + q[i]) % k;

ans += p[(int)q[i]];
p[(int)q[i]]++;
}
System.out.println(ans + p[0]);

}
}
-------------本文结束感谢您的阅读-------------
0%