【竞赛题解】第22次CCF计算机软件能力认证 B

今天（准确说是昨天，一下子就过12点了）下午刚参加了CSP认证考试，大概是考了220（前两题AC，第三题太折磨了懒得看了，后面两题各混了10分），唯一有点参与感的就是B题了，于是这里分析下我的B题思路。

题意：对于$n?n$的矩阵，求存在多少个这样的点（以该点为中心半径为 $r$ 正方形块中的总值的平均数不大于阈值 $t$ ）

思路：如上图所示，靠边缘的点所形成的方块是不完整的，当时第一遍我是打算用dp计算中央部分完整的块，而对于边缘不完整的块则采用暴力，实现起来比较简单，没想到的是有30%($n<=600,r<=100$)TLE了，码代码前只是粗略的计算了一下时间复杂度，感觉能过。于是又想到了下面的方法，消除了暴力的部分。

人为地将矩阵向外扩充 $r$ 个单位，这样就避免了靠近边缘的点形成不完整的方块，并且对于扩充的格子均填上阈值 $t$ ，这样在计算平均值时又保持了原方块的平均值与阈值的大小关系

$$\begin{gathered} \frac{sum}{m}\le t\to sum\le m?t \\ sum+(n?t)\le m?t+(n?t) \\ sum+(n?t)\le (m+n)?t \\ \frac{sum+n?t}{m+n}\le t \end{gathered}$$

dp的部分有空再分析分析，现在得睡觉了。。

代码：（赛后重写了一遍，没交过，不保证AC）

#include<bits/stdc++.h>
#define debug1(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef unsigned long long ull;
const int N = 1000;
using namespace std;
int a[N][N], dp[N][N],row[N],col[N][N];
int n,L,r,t,R;
void init()
{
    for(int i = 0; i < N; i++)
    {
        row[i] = -1;
        for(int j = 0; j < N; j++)
        {
            a[i][j] = t;
            col[i][j] = -1;
        }
    }
}
int calc_row(int i)
{
    if(row[i] == -1)
    {
        int sum = 0;
        for(int j = 0 - r; j <= 0 + r; j++) sum += a[i][R + j];
        row[i] = sum;
    }
    return row[i];
}
int calc_col(int i, int j)
{
    if(col[i - 1][j] == -1)
    {
        int sum = 0;
        for(int k = i - r; k <= i + r; k++) sum += a[k][j];
        col[i][j] = sum;
    }
    else
    {
        col[i][j] = col[i - 1][j] + a[i + r][j] - a[i - 1 - r][j];
    }
    return col[i][j];
}
int main()
{
    cin>>n>>L>>r>>t;
    R = r + 5;
    init();
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            scanf("%d",&a[R + i][R + j]);
        }
    }
    // calculate dp[0][0]
    for(int i = 0 - r; i <= 0 + r; i++)
    {
        for(int j = 0 - r; j <= 0 + r; j++)
        {
            dp[0][0] += a[R + i][R + j];
        }
    }
    
    for(int i = 0; i < n; i++)
    {
        if(i)
        {
            int sub_row = calc_row(R + i - 1 - r);
            int add_row = calc_row(R + i + r);
            dp[i][0] = dp[i - 1][0] + add_row - sub_row;
        }
        for(int j = 1; j < n; j++)
        {
            int sub_col = calc_col(R + i, R + j - 1 - r);
            int add_col = calc_col(R + i, R + j + r);
            dp[i][j] = dp[i][j - 1] + add_col - sub_col;
        }
    }
    
    int ans = 0, block = (2 * r + 1)*(2 * r + 1);
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(dp[i][j] <= t * block) ans++;
        }
    }
    cout<<ans<<"\n";

	return 0;
}

刚去学习了一下二维前缀和的知识，果然比自己写的dp简约多了！

代码：采用二维前缀和+人为扩矩（依旧不保证正确，目前还没机会交）

#include<bits/stdc++.h>
#define debug1(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef unsigned long long ull;
const int N = 1000;
using namespace std;
int a[N][N], dp[N][N], s[N][N];
int n,L,r,t,R;
void init()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            a[i][j] = t;
        }
    }
}

int main()
{
    cin>>n>>L>>r>>t;
    R = r + 5;
    init();
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            scanf("%d",&a[R + i][R + j]);
        }
    }
    for(int i = 0 - r; i < n + r; i++)
    {
        for(int j = 0 - r; j < n + r; j++)
        {
            s[R + i][R + j] = s[R + i - 1][R + j]
                            + s[R + i][R + j - 1]
                            - s[R + i - 1][R + j - 1]
                            + a[R + i][R + j];
        }
    }
    int i1,j1,i2,j2,sum;
    int ans = 0, block = (2 * r + 1)*(2 * r + 1);
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            i1 = R + i - r; i2 = R + i + r;
            j1 = R + j - r; j2 = R + j + r;

            sum = s[i2][j2]
                - s[i2][j1 - 1]
                - s[i1 - 1][j2]
                + s[i1 - 1][j1 - 1];

            if(sum <= t * block) ans++;
        }
    }
    cout<<ans<<"\n";

    return 0;
}

A题：比较基础的统计题，按题目要求统计每个数出现的次数即可

#include<bits/stdc++.h>
#define debug1(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int main()
{
	int n, m, L;
    cin>>n>>m>>L;
    vector<int> ans(L);
    int tmp;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            scanf("%d",&tmp);
            ans[tmp]++;
        }
    }
    for(int i = 0; i < L; i++) cout<<ans[i]<<" ";
    
	return 0;
}