打比赛被暴打了，深感基础没有打牢，于是现在开始刷洛谷基础题单。
https://www.luogu.com.cn/training/103#problems
三道相同思路的题目，给处理过的区域打上标记，遍历计数未处理区域。
【P1047】校门外的树
题目描述
某校大门外长度为 l 的马路上有一排树，每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴，马路的一端在数轴 0 的位置，另一端在 l 的位置；数轴上的每个整数点，即 0,1,2,…,l，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入格式
第一行有两个整数，分别表示马路的长度 l 和区域的数目 m。
接下来 m 行，每行两个整数 u, v，表示一个区域的起始点和终止点的坐标。
输出格式
输出一行一个整数，表示将这些树都移走后，马路上剩余的树木数量。
样例输入
1
2
3
4
| 500 3
150 300
100 200
470 471
|
样例输出
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
| import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
int l = input.nextInt();
int m = input.nextInt();
int arr[] = new int[l + 1];
int n = 0;
for(int i = 0; i <= l; i++)
{
arr[i] = 0;
}
for(int i = 0; i < m; i++)
{
int beg = input.nextInt();
int end = input.nextInt();
for(int j = beg; j <= end; j++)
{
arr[j] = 1;
}
}
for(int i = 0; i < l + 1; i++)
{
if(arr[i] == 0)
{
n++;
}
}
System.out.println(n);
}
}
|
【P1789】Mc生存 插火把
题目背景
初一党应该都知道……
题目描述
话说有一天 linyorson 在“我的世界”开了一个 n * n 的方阵，现在他有 m 个火把和 k 个萤石，分别放在 (x_1, y_1) - (x_m, y_m) 和 (o_1, p_1) - (o_k, p_k) 的位置，没有光并且没放东西的地方会生成怪物。请问在这个方阵中有几个点会生成怪物？
P.S. 火把的照亮范围是：
1
2
3
4
5
| |暗|暗| 光 |暗|暗|
|暗|光| 光 |光|暗|
|光|光|火把|光|光|
|暗|光| 光 |光|暗|
|暗|暗| 光 |暗|暗|
|
萤石：
1
2
3
4
5
| |光|光| 光 |光|光|
|光|光| 光 |光|光|
|光|光|萤石|光|光|
|光|光| 光 |光|光|
|光|光| 光 |光|光|
|
输入格式
输入共 m + k + 1 行。
第一行为 n, m, k。
第 2 到第 m + 1 行分别是火把的位置 x_i, y_i。
第 m + 2 到第 m + k + 1 行分别是萤石的位置 o_i, p_i。
注：可能没有萤石，但一定有火把。
输出格式
有几个点会生出怪物。
样例输入
样例输出
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
| #include <stdio.h>
#include <math.h>
#define N 100 + 5
int main()
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
int block[N][N];
int t = 0;
for(int i = 0; i < m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
for(int j = x - 1; j <= x + 1; j++)
{
for(int k2 = y - 1; k2 <= k + 1; k2++)
{
block[j][k2] = 1;
}
}
block[x][abs(y - 2)] = 1;
block[x][y + 2] = 1;
block[abs(x - 2)][y] = 1;
block[x + 2][y] = 1;
}
for(int i = 0; i < k; i++)
{
int x,y;
scanf("%d%d",&x,&y);
for(int j = x - 2; j <= x + 2; j++)
{
for(int k2 = y - 2; k2 <= k + 2; k2++)
{
block[j][k2] = 1;
}
}
}
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= n; j++)
{
if(block[i][j] == 0) t++;
}
}
printf("%d",t);
}
|
【P5729】工艺品制作
题目描述
现有一个长宽高分别为 w,x,h 组成的实心玻璃立方体，可以认为是由 1 * 1 * 1 的数个小方块组成的，每个小方块都有一个坐标 ( i,j,k ) 。现在需要进行 q 次切割。每次切割给出 (x_1,y_1,z_1),(x_2,y_2,z_2) 这 6 个参数，保证 x_1 <= x_2，y_1 <= y_2，z_1 <= z_2；每次切割时，使用激光工具切出一个立方体空洞，空洞的壁平行于立方体的面，空洞的对角点就是给出的切割参数的两个点。
换句话说，所有满足 x_1 <= i <= x_2，y_1 <= j <= y_2 ，$z_1 <= k <= z_2 的小方块 (i,j,k) 的点都会被激光蒸发。例如有一个 4 * 4 * 4 的大方块，其体积为 64；给出参数 (1,1,1),(2,2,2) 时，中间的 8 块小方块就会被蒸发，剩下 56 个小方块。现在想知道经过所有切割操作后，剩下的工艺品还剩下多少格小方块的体积？
输入格式
第一行三个正整数 w,x,h。
第二行一个正整数。
接下来 q 行，每行六个整数 (x_1,y_1,z_1),(x_2,y_2,z_2)。
输出格式
输出一个整数表示答案。
样例输入
样例输出
数据保证，1 <= w,x,h <= 20，1 <= q <= 100。1 <= x_1 <= x_2 <= w，1 <= y_1 <= y_2 <= x，1 <= z_1 <= z_2 <= h。
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
| import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
int m = input.nextInt();
int x = input.nextInt();
int h = input.nextInt();
int block[][][] = new int[m][x][h];
int q = input.nextInt();
int n = 0;
for(int i = 0; i < q; i++)
{
int x1 = input.nextInt();
int y1 = input.nextInt();
int z1 = input.nextInt();
int x2 = input.nextInt();
int y2 = input.nextInt();
int z2 = input.nextInt();
for(int j = x1; j <= x2; j++)
{
for(int k = y1; k <= y2; k++)
{
for(int l = z1; l <= z2; l++)
{
block[j][k][l] = 1;
}
}
}
}
for(int i = 0; i < m; i++)
{
for(int j = 0; j < x; j++)
{
for(int k = 0; k < h; k++)
{
if(block[i][j][k] == 0) n++;
}
}
}
System.out.println(n);
}
}
|