CCF CSP认证 历年题目自练Day31

题目一

试题编号： 202206-1
试题名称： 归一化处理
时间限制： 500ms
内存限制： 512.0MB
题目背景
在机器学习中，对数据进行归一化处理是一种常用的技术。
将数据从各种各样分布调整为平均值为 0、方差为 1的标准分布，在很多情况下都可以有效地加速模型的训练。

样例输入
7
-4 293 0 -22 12 654 1000
Data
样例输出
-0.7485510379073613
0.04504284674812264
-0.7378629047806881
-0.7966476369773906
-0.7057985054006686
1.0096468614303775
1.9341703768876082

题目分析（个人理解）

1. 此题送分题，还是先看输入，第一行输入n，第二行输入n个数，每个数用空格分开。
2. 再看输出，求的是每个数减去平均数在除以方差。
3. 还是选择列表存储我将所有值都存入列表。我采用列表推导式。
   l=[i for i in map(int,input().split())]
4. 然后用sum函数求和除以n获得平均数，用math库的sqrt函数来开根号求得F（ai）。
5. 最后遍历输出fa即可。
6. 上代码！！！

import math
D=[]
mean=0
n=int(input())
l=[i for i in map(int,input().split())]
mean=sum(l)/n
for i in range(n):
    d=abs(l[i]-mean)**2#不用abs求绝对值也行，只是数学逻辑严谨一些
    D.append(d)
Da=math.sqrt(sum(D)/n)
for i in range(n):
    fa=(l[i]-mean)/Da
    print(fa)
1
2
3
4
5
6
7
8
9
10
11
12
13

题目二

试题编号： 202206-2
试题名称： 寻宝！大冒险！
时间限制： 500ms
内存限制： 512.0MB
题目背景
暑假要到了。可惜由于种种原因，小 P 原本的出游计划取消。失望的小 P 只能留在西西艾弗岛上度过一个略显单调的假期……直到……某天，小 P 获得了一张神秘的藏宝图。

输出格式
输出到标准输出。
输出一个整数，表示绿化图中有多少处坐标可以与藏宝图左下角对应，即可能埋藏着顿顿的宝藏。

样例 1 输入
5 100 2
0 0
1 1
2 2
3 3
4 4
0 0 1
0 1 0
1 0 0
Data
样例 1 输出
3
Data
样例 1 解释
绿化图上 （0,0）（1,1）（2,2）三处均可能埋有宝藏。

样例 2 输入
5 4 2
0 0
1 1
2 2
3 3
4 4
0 0 0
0 1 0
1 0 0
Data
样例 2 输出
0
Data
样例 2 解释
如果将藏宝图左下角与绿化图 （3,3） 处对应，则藏宝图右上角会超出绿化图边界，对应不成功。

题目分析（个人理解）

1. 还是先读题目，大意是这样的，有一张地图A（绿化图，题目是这么叫的），用类矩阵表示里面只有数值1或0,1代表有树，0代表没树。还有一张图B（也就是题目中的藏宝图），B图比A图小，一样只有1或0表示是否有树，如何判断宝藏地点？
2. 绿化图中有多少处坐标可以与藏宝图左下角对应，即可能埋藏着顿顿的宝藏。如何理解？就是满足b图作为A图的子图（0和1位置完全符合）且B图的左下角（只有一个点）才是一个藏宝地点，那么我只需要按照B图的大小以及数值，遍历A图（0和1）判断满足有几个子图那么就说明有几个藏宝地点。这里尤其注意输入，不管A图还是B图都是左下角是（0,0）点，而且，最先输入的是B[s][0]最后输入的是B[0][s]；所以当给B图赋值的时候要倒序遍历。
3. 那么如何判断满不满足B图是A图的子图的条件呢?只需要从a图左下角依次遍历以b图左下角为开始到右上角的值是否都相等，如果都相等，那么就是子图，否则则不是。
4. 代码如何具体实现？我选择列表存储A图和B图，具体用列表推导式，用二维列表表示01矩阵。
5. 然后分别将A，B两图的值输入，然后依次（从A图左下角开始）把和B图同等大小的A图的局部图抠下来，去和B图判断是否相等即可。如果相等计数器加1，最后输出计数器数值。
6. 上代码！！！（只能拿70分，因为抠下来的图太多了，占用空间太大）

n, L, S = map(int, input().split()) # n棵树，L绿化图大小，S藏宝图大小
A = [[0 for _ in range(L+1)] for _ in range(L+1)] # A绿化图坐标
t = [] # 树的坐标列表
for _ in range(n): # 把n棵树写到A绿化图中
  x, y = map(int, input().split()) # 每棵树的坐标
  t.append([x,y])
  A[x][y] = 1
B = [[0 for _ in range(S+1)] for _ in range(S+1)] # B藏宝图坐标
for i in range(S,0-1,-1): # 把局部树写到B藏宝图中
  B[i] = list(map(int, input().split()))

res = 0 # 可能情况的数量
for i in t:
  if i[0] + S <= L and i[1] + S <= L:
    T = [] # 同大小局部绿化图坐标
    for j in range(S+1):
      T.append(A[i[0]+j][i[1]:i[1]+S+1])
    if T == B:
      res = res + 1
print(res)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

7. 只能换个思路了，第二种方法是这样的：
8. 我完全可以只遍历A图中有树（值为1）的位置，作为B图的左下角（B图左下角必须有树，题目告诉了藏宝图左下角一定是一棵树）。那么我只需要遍历n次就可以判断完全。
9. 为了减少判断次数，可先将是否满足B图是A图的子图作为第一个判断条件，具体就是如果A图中值为1坐标x,y轴分别加上B图的横，纵长度如果超过A图的大小就不满足是A图子图的条件，那么就没必要进行下一步判断了。
   10.上代码！！！

# 输入三个正整数 n、L 和 S，分别表示西西艾弗岛上树的棵数、绿化图和藏宝图的大小
n, l, s = map(int, input().split())
# 输入每棵树的坐标
points = [[i for i in map(int,input().split())] for j in range(n)]
# 将树的坐标整理成集合的形式，方便后面进行地图与树位置的比对
temp = {}
for point in points:
    x, y = point[0], point[1]
    temp[(x, y)] = 1
# 建立藏宝图
money = []
for i in range(s+1):
    money.insert(0, list(map(int, input().split())))
# 设置time值来记录绿化图中有多少处坐标可以与藏宝图左下角对应
time = 0
# 开始遍历树的坐标与藏宝图中的树的坐标进行比对
for x, y in points:
    # 设置一个标志值来判定是否符合藏宝图要求
    flag = 0
    # 开始遍历比对
    for i in range(s+1):
        for j in range(s+1):
            if (x+i > l) or (y+j > l): #藏宝图的要求：大小必然小于绿化图
                flag = 1
                break
            if money[i][j]: 
                if (x+i, y+j) not in temp:
                    flag = 1
                    break
            else:      
                if (x+i, y+j) in temp:
                    flag = 1
                    break
        if flag == 1:  
            break
    if flag == 0:
        time += 1
print(time)

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

总结