给孩子用的，孩子很开心，9月份还会买的

成绩

反正就是 50 块换了一个 CSP 选修课及格

题解

说实话我就会两道题... ...硬着头皮写题解，还是第一次写多美妙的词汇

灰度直方图

原题链接：链接

问题描述

一幅长宽分别为 n 个像素和 m 个像素的灰度图像可以表示为一个 n×m 大小的矩阵 A。 其中每个元素 Aij（0≤i<n、0≤j<m）是一个 [0,L) 范围内的整数，表示对应位置像素的灰度值。 具体来说，一个 8 比特的灰度图像中每个像素的灰度范围是 [0,128)。
一副灰度图像的灰度统计直方图（以下简称“直方图”）可以表示为一个长度为 L 的数组 h，其中 h[x]（0≤x<L）表示该图像中灰度值为 x 的像素个数。显然，h[0] 到 h[L−1] 的总和应等于图像中的像素总数 n⋅m。
已知一副图像的灰度矩阵 A，试计算其灰度直方图 h[0],h[1],⋯,h[L−1]。

输入格式

输入共 n+1 行。
输入的第一行包含三个用空格分隔的正整数n、m 和 L，含义如前文所述。
第二到第 n+1 行输入矩阵 A 。
第 i+2（0<=i<=n）行包含用空格分隔的 m 个整数，依次为Ai0,Ai1...Ai(m-1) 。

输出格式

输出到标准输出。
输出仅一行，包含用空格分隔的 L 个整数 h[0],h[1],⋯,h[L−1]，表示输入图像的灰度直方图。
全部的测试数据满足 0<n,m≤500 且 4≤L≤256。

样例

输入

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

输出

48 0 0 0 0 0 0 29

题解

这题完全白给，你甚至不需要建立矩阵，直接边输入边加和就完事了。

代码

#include <cstdio>
#include <cstring>

int main() {
    int n, m, L;
    scanf("%d %d %d", &n, &m, &L);

    int h[L];
    int point;

    memset(h, 0, sizeof(h));

    for (int i = 0; i < m; i++) {
	    for (int j = 0; j < n; j++) {
		    scanf("%d", &point);
		    h[point]++;
	    }
    }

    for (int k = 0; k < L; k++) {
	    printf("%d ", h[k]);
    }
}

邻域均值

原题链接：链接

题目背景

顿顿在学习了数字图像处理后，想要对手上的一副灰度图像进行降噪处理。不过该图像仅在较暗区域有很多噪点，如果贸然对全图进行降噪，会在抹去噪点的同时也模糊了原有图像。因此顿顿打算先使用邻域均值来判断一个像素是否处于较暗区域，然后仅对处于较暗区域的像素进行降噪处理。

题目描述

待处理的灰度图像长宽皆为 n 个像素，可以表示为一个 n×n 大小的矩阵 A，其中每个元素是一个 [0,L) 范围内的整数，表示对应位置像素的灰度值。 对于矩阵中任意一个元素 Aij（0≤i,j<n），其邻域定义为附近若干元素的集和：
Neighbor(i,j,r)={Axy|0≤x,y<n and |x−i|≤r and |y−j|≤r}
这里使用了一个额外的参数 r 来指明 Aij 附近元素的具体范围。根据定义，易知 Neighbor(i,j,r) 最多有 (2r+1)2 个元素。
如果元素 Aij 邻域中所有元素的平均值小于或等于一个给定的阈值 t，我们就认为该元素对应位置的像素处于较暗区域。 下图给出了两个例子，左侧图像的较暗区域在右侧图像中展示为黑色，其余区域展示为白色。现给定邻域参数 r 和阈值 t，试统计输入灰度图像中有多少像素处于较暗区域。

图我就不放了，没什么卵用

输入格式

从标准输入读入数据。
输入共 n+1 行。
输入的第一行包含四个用空格分隔的正整数 n、L、r 和 t，含义如前文所述。
第二到第 n+1 行输入矩阵 A。 第 i+2（0≤i<n）行包含用空格分隔的 n 个整数，依次为 Ai0,Ai1,⋯,Ai(n−1)。

输出格式

输出到标准输出。
输出一个整数，表示输入灰度图像中处于较暗区域的像素总数。
70% 的测试数据满足 n≤100、r≤10。
全部的测试数据满足 0<n≤600、0<r≤100 且 2≤t<L≤256。

样例

输入

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

输出

83

题解

嵌套 4 层 for 循环的暴力解直接超时，无法通过 30% 的测试样例。（我为什么知道，因为我就这么做的... ...）

建议做这道题前先掌握前缀和打表法的知识（其实我也会，但真的没想到要用... ...还是题做少了）

贴个链接，讲得比较好的：链接

如果你掌握了上面的知识，那这道题也相当于白给了。核心思想就是用前缀和公式求那一片的平均值而不是两层循环。注意边界条件，比如不能超过二维数组的范围，以及左上角的数据要 -1 等。

代码

#include <cstdio>
#include <algorithm>

using namespace std;
int a[610][610];

int main() {
    int res = 0;
    int n, L, r, t;
    scanf("%d %d %d %d", &n, &L, &r, &t);

    int x;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &x);
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + x;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int total, m;
            int x1, x2, y1, y2;

            x1 = max(1, i - r);
            y1 = max(1, j - r);
            x2 = min(n, i + r);
            y2 = min(n, j + r);

            total = a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1];
            m = (y2 - y1 + 1) * (x2 - x1 + 1);

            if (total <= t * m)
                res++;
        }
    }

    printf("%d", res);
}

感谢博客2021年四月CCF-CSP认证题目提供的相关思路。