CCF CSP认证 历年题目自练Day27

题目一

试题编号： 202104-1
试题名称： 灰度直方图
时间限制： 1.0s
内存限制： 512.0MB

样例输入
7 11 8
0 7 0 0 0 7 0 0 7 7 0
7 0 7 0 7 0 7 0 7 0 7
7 0 0 0 7 0 0 0 7 0 7
7 0 0 0 0 7 0 0 7 7 0
7 0 0 0 0 0 7 0 7 0 0
7 0 7 0 7 0 7 0 7 0 0
0 7 0 0 0 7 0 0 7 0 0
Data
样例输出
48 0 0 0 0 0 0 29
Data
评测要求：

题目分析（个人理解）

1. 还是先看输入，第一行输入n表示类矩阵的行数，m表示列数，第三个参数l表示每个元素都小于l。
2. 很简单，直接用列表推导式生成二维列表，依次写入元素值即可，然后再将二维列表一维化，要求输出的是0到(l-1)的元素值出现的次数，那就遍历l，统计在一维列表中出现的次数，然后将次数追加写入到新列表，最后输出新列表即可。
3. 上代码！！！

n, m, l = map(int, input().split())
num = [[i for i in map(int, input().split())] for j in range(n)]
nums = [i for j in num for i in j]
#nums = sum(num, [])
#上面两种方法都是将二维数组num化为一维数组nums,选一种即可
h = []
for i in range(l):
    h.append(nums.count(i))
    #统计i在一维数组中出现的次数，并记录到h中
print(*h)
1
2
3
4
5
6
7
8
9
10

题目二

试题编号： 202104-2
试题名称： 邻域均值
时间限制： 1.0s
内存限制： 512.0MB


样例输入
4 16 1 6
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
Data
样例输出
7
Data
样例输入
11 8 2 2
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 7 0 0 0 7 0 0 7 7 0
7 0 7 0 7 0 7 0 7 0 7
7 0 0 0 7 0 0 0 7 0 7
7 0 0 0 0 7 0 0 7 7 0
7 0 0 0 0 0 7 0 7 0 0
7 0 7 0 7 0 7 0 7 0 0
0 7 0 0 0 7 0 0 7 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
Data
样例输出
83

题目分析（个人理解）

1. 首先，这个题目就很能吓唬人，大概思路是这样的，第一行输入n表示有一个n行n列的矩阵（图像），之后的n行输入元素。第二个参数l代表矩阵中的元素小于l，第三个参数是r，用来表示范围，再仔细看题，我们需要判断矩阵中每个元素（像素）在r范围内的平均数是否小于等于t(阈值）也就是第四个参数，如果小于等于那就count +1（count作为计数器），最后输出count就知道较暗区域有几个像素了。
2. 那么问题来了，r是变的，可以是1,2,3…那么对应要求和的数目也在变化，如果是最左上角的元素，当r=1时，总共有四个数相加求和之后再求平均值，如果是第一行第二列就要计算6个数的数值，在中间的位置就要计算9个数的值，很不方便判断，我对类矩阵依旧选择二维列表来实现。那么为了统一针对不同位置的元素可以使用相同的算法我选择对原矩阵扩充r行2r列，使其每一个元素都满足在r=1时计算9个元素求和再求平均数的问题。
3. 如图：就以第一个输入例子为例：（填充之后）
   
   那么用列表生成机器迭代生成即可

mat = [[0] * (n + 2 * r) for _ in range(n + 2 * r)]
for i in range(r, n + r):
    mat[i] = [0] * r + list(map(int, input().split())) + [0] * r
count = 0
1
2
3
4

4. 最关键的点到了，现在都满足遍历原矩阵的时候求和求平均值都是最大的情况（（2r+1）**2个），那就很好办来了，接下来给大家介绍二维矩阵前缀和，用来解决任意一个子矩阵内的元素和。
5. 如图：红色区域相当于要求和的所有元素所在的位置。
   
   我要求红色部分面积如何求？

# sum[x1][y1] 被减掉两次
area_red=sum[x4][y4]-sum[x3][y3]-sum[x2][y2]+sum[x1][y1]

1
2
3

二维前缀和矩阵的生成：

# mat[xc][yc]表示原始矩阵
sum[x_c][y_c]=sum[x_a][y_a]+sum[x_b][y_b]+mat[x_c][y_c]
<==>
sum[x][y]=sum[x-1][y]+sum[x][y-1]+mat[x][y]

1
2
3
4
5

6. 那么这道题如何求红色部分？

for i in range(r, n + r):
    for j in range(r, n + r):
        sum_mat[i][j] = mat[i][j] + sum_mat[i][j - 1] + sum_mat[i - 1][j] - sum_mat[i - 1][j - 1]

1
2
3
4

7. 之后只需遍历每一个元素判断是否在红色区域如果是那就加起来求平均值在去和t比大小，若是小于等于就count+1，然后输出count就结束啦！！！
8. 上完整代码！！！

n, l, r, t = map(int, input().split())
mat = [[0] * (n + 2 * r) for _ in range(n + 2 * r)]
for i in range(r, n + r):
    mat[i] = [0] * r + list(map(int, input().split())) + [0] * r
count = 0
#计算二维前缀和
sum_mat = [[0] * (n + 2 * r) for _ in range(n + 2 * r)]
for i in range(r, n + r):
    for j in range(r, n + r):
        sum_mat[i][j] = mat[i][j] + sum_mat[i][j - 1] + sum_mat[i - 1][j] - sum_mat[i - 1][j - 1]

for i in range(r, n + r):
    for j in range(r, n + r):
        # 判断领域内元素个数
        # 领域x，y最左，最右坐标
        min_i = i - r if i - r > r - 1 else r
        max_i = i + r if i + r < n + r else n + r - 1
        min_j = j - r if j - r > r - 1 else r
        max_j = j + r if j + r < n + r else n + r - 1
        # print(min_i, min_j, max_i, max_j)
        nums = (max_i - min_i + 1) * (max_j - min_j + 1)
        # print(nums)
        sum_m = sum_mat[max_i][max_j] - sum_mat[i - r - 1][max_j] - sum_mat[max_i][j - r - 1] + \
                sum_mat[i - r - 1][j - r - 1]
        flag = sum_m / nums
        if flag <= t:
            count = count + 1
print(count)




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

总结

脑子要裂开，出去跑步冷静一下。