CSP-2021-4

CSP 2021年4月试题

第一题 灰度直方图

分析

乍一看是一个二维数组模拟灰度值存储，实际上只需要一个一维数组计数即可，类似桶排序，输入一个对应位置加一

程序

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m, l;
    cin >> n >> m >> l;
    int temp;
    vector<int> v(l, 0);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> temp;
            v[temp]++;
        }
    }
    for (int i = 0; i < l; i++)
    {
        cout << v[i] << ' ';
    }
}

第二题 邻域均值

思路

感觉最近两次的第二题暴力算法基本都会超时，只能拿到70分左右，此题也是如此如果对每一个元素循环相加其邻域内的元素相当于增加了两层循环，总循环为4层，会导致30%数据超时，为了提高效率，需要想办法降维。
为了提高运算效率，容易想到，提前计算一些东西，在算邻域平均值时可以直接拿来用。
此处使用前缀和(数组第k项之前的和)的方式实现，使用一个二维数组rowSum[i][j]表示第i行中j元素之前的所有元素之和，这样就可以通过相减的方式快速算出某一行中某两个元素之间的数字和。这样就减少了一层循环，只需要三层就可完成。成功通过剩余30%测试点

程序

#include <bits/stdc++.h>
using namespace std;
int main()
{
    //dark用于记录暗点个数
    int n, l, r, t, temp, dark = 0;
    cin >> n >> l >> r >> t;
    //row[i][j]为第i行从0到j个的总和
    int rowSum[n][n];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> temp;
            if (j == 0)
            {
                rowSum[i][j] = temp;
            }
            else
            {
                rowSum[i][j] = rowSum[i][j - 1] + temp;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            float tempSum = 0, tempNum;
            //区域的界限
            int li = i - r >= 0 ? i - r : 0;
            int ri = i + r < n ? i + r : n - 1;
            int lj = j - r >= 0 ? j - r : 0;
            int rj = j + r < n ? j + r : n - 1;
            for (int m = li; m <= ri; m++)
            {
                //此处注意从a到b的和不是rowSum[m][b]-rowSum[m][a]而是rowSum[m][b]-rowSum[m][a-1]同时要注意a-1可能导致的数组越界问题
                tempSum += rowSum[m][rj] - (lj - 1 >= 0 ? rowSum[m][lj - 1] : 0);
            }
            //元素个数和(行数*列数)；
            tempNum = (ri - li + 1) * (rj - lj + 1);
            if (tempSum / tempNum <= t)
            {
                dark++;
            }
        }
    }
    cout << dark;
}