Zth's Blog

记录学习路上的点滴

0%

csp202104

发表于 更新于 分类于

csp认证2021年四月部分题解

202104-1.灰度直方图

题意

给一个 $n \times m$ 的矩阵， 矩阵中每个数均为非负整数且小于$L$， $h[i]$表示数字$i$出现的次数， 输出$h[i], 0 \leq i < L$

数据范围

$0 < n, m \leq 500, 4 \leq L \leq 256$

题解

直接开一个数组$h$， 每次输入一个数$a, h[a] ++$， 最后输出$h$数组即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>

int n, m, L;
int h[262];

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

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            int a;
            scanf("%d", &a);

            h[a] ++;
        }

    for(int i = 0; i < L; i ++) printf("%d%c", h[i], " \n"[i == L - 1]); //控制输出的一种方法

    return 0;
}

202104-2.邻域均值

题意

给一个$n \times n$的矩阵$A_{i, j}$， 矩阵中每个数都为非负整数且小于$L$， 求邻域中所有数的平均值小于等于$t$的， $A_{i, j}$的个数

特别的， 对于一个矩阵元素$A_{i, j}$， 其邻域定义如下

$Neighbor(i, j, r) = A_{x, y} | 0 \leq x, y < n, |x - i | \leq r, |y - j| \leq r$

$r$题目中会给出

数据范围

$70\%$数据， $n \leq 100, r \leq 10$

$100\%$数据， $0 < n \leq 600, 0 < r \leq 100, 2 \leq t < L \leq 256$

题解

70分解法

我们设$s$， 为$A_{i, j}$的邻域中所有数的和， 枚举$i, j$， 每次暴力的遍历$A_{i, j}$的邻域统计$s$， 然后将其均值与$t$比较

时间复杂度$O(n^2r^2)$

代码

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
#include <iostream>
#include <cstdio>

int n, L, R, t;
int a[602][602];
int s, ans;

int main()
{
    scanf("%d%d%d%d", &n, &L, &R, &t);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            scanf("%d", &a[i][j]);

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
        {
          
            int u = std:: max(1, i - R), d = std:: min(n, i + R), l = std:: max(1, j - R), r = std:: min(n, j + R);
            // u表示邻域矩阵的上边界， d表示下边界， l左边界， r右边界
            s = 0; // s表示邻域中所有数的和
            for(int k = u; k <= d; k ++)
                for(int p = l; p <= r; p ++)
                    s += a[k][p];
                
            if(s <= (r - l + 1) * (d - u + 1) * t) ans ++; // 均值与t比较
        }

    printf("%d\n", ans);

    return 0;
}

100分解法

二维前缀和， 不会百度

代码

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
#include <iostream>
#include <cstdio>

int n, L, R, t;
int a;
int s[602][602], ans;

int main()
{
    scanf("%d%d%d%d", &n, &L, &R, &t);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
        {
            scanf("%d", &a);

            s[i][j] = a + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
        {
            int u = std:: max(1, i - R), d = std:: min(n, i + R), l = std:: max(1, j - R), r = std:: min(n, j + R);

            if(s[d][r] - s[u - 1][r] - s[d][l - 1] + s[u - 1][l - 1] <= t * (d - u + 1) * (r - l + 1)) ans ++;
        }

    printf("%d\n", ans);

    return 0;
}

202104-4.校门外的树

题意

一连续序列中存在$n$个障碍物$a$，我们可以在非障碍物的点上种树但是种的树需要满足以下条件：

以这些障碍物中的一些为端点将这个序列分成若干段， 每一段中种的树和端点构成等差数列

问不同的种树的方案数， 对$10^9 + 7$取模

数据范围

$2 \leq n \leq 1000, 0 \leq a_i \leq 100000$

题解

只会100分的

显然这是一道$dp$题， 那么尝试设计状态， 设$dp[i]$表示只考虑前$i$个障碍物时的方案数量， 那么我们要求$dp[i + 1]$时， 只需统计以$i + 1$为右端点的方案加进答案里就可以了， 也就是说这个$dp$状态的设计已经可以满足我们的要求了， 而且显然没有优化空间， 那么我就这么设计状态， 然后考虑转移

假设我们当前应该计算$dp[i]$, 那么

其中$res_{i, j}$为以$a_i, a_j$为端点的合法的种树的方案数

下面证明这样可以不重不漏的计算所有的方案

  1. 不漏

    对于$dp$数组而言， $dp[i]$中是计算了$a_i$为右端点的所有的方案的， $dp[i]$肯定是包含了所有的方案的

  2. 不重

    这一部分是这一道题的核心

对于$dp[i]$而言， 我们在枚举$j$的过程中， 计算$res_{i, j}$, 怎么避免出现重复呢？ 其实根本就不可能出现重复， 证明如下

假设对于$j_1 < j_2$， 计算$res_{i, j}$的过程中出现了两种相同的状态

也就是说对于一个间隔$d$, 以$d$为间隔$[a_{j_1}, a_i], [a_{j_2}, a_i]$均可以构成等差数列， 那么$[a_{j_1}, a_i]$的这个等差数列必然是由$[a_{j_1}, a_i]$向左延伸而来的， 也就是说在$[a_{j_1}, a_i]$中， 我们需要在$a_{j_2}$处种上一颗树， 这显然不合法， 与我们之前设定的$res_{i, j}$为以$a_i, a_j$为端点的合法的种树的方案数相违背， 所以必然不会出现重复的情况， 得证

在得到了上述不重的证明以后， 我们其实还得到了一个优化方案

计算$dp[i]$时， 对于$res_{i, j}$中的间隔$d$, 每个$d$只会出现一次， 而且出现的唯一一次就是以$d$为间隔的最靠右的那个$j$

那这样的话我们只需要倒序的枚举$j$, 然后枚举$d$, 如果$d$之前出现过， 直接跳过， 否则$d$可行， $res_{i, j} ++$， 标记$d$出现过

另外还有一个小细节， 如果我们$[a_j, a_i]$看成一整段，即他们之间不种树，这样不应该统计这次答案， 但是我们仍然是需要标记$d$的

代码

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
51
52
53
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>

const int mod = 1e9 + 7;

int n;
int a[1003];
int f[1003]; // dp数组， 这里叫f
bool ap[100005]; // 表示间隔d是否出现过
std:: vector<int> fac[100005]; // vector， 不定长数组， 不会百度

int main()
{
    for(int i = 1; i <= 100000; i ++) // 预处理出间隔d
        for(int j = 1, sqi = sqrt(i); j <= sqi; j ++)
            if(i % j == 0)
            {
                fac[i].push_back(j);

                if(j * j != i && j != 1) fac[i].push_back(i / j);
            }

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

    f[1] = 1;
    for(int i = 2; i <= n; i ++)
    {
        memset(ap, 0, sizeof(ap)); // 对于每个i初始化d未出现过

        for(int j = i - 1; j >= 1; j --)
        {
            int d = a[i] - a[j];

            ap[d] = true; // 小细节

            if(d == 1) continue;

            for(int k = 0; k < fac[d].size(); k ++)
                if(! ap[fac[d][k]]) // 检查d是否出现过
                    f[i] = (1LL * f[i] + 1LL * f[j]) % mod, ap[fac[d][k]] = true; // 转移
        }
    }

    //for(int i = 1; i <= n; i ++) printf("%d%c", f[i], " \n"[i == n]);

    printf("%d\n", f[n]);

    return 0;
}