CCF CSP认证 历年题目自练Day24

题目一

试题编号： 202009-1
试题名称： 称检测点查询
时间限制： 1.0s
内存限制： 256.0MB
问题描述：
题目背景
2020 年 6 月 8 日，国务院联防联控机制发布《关于加快推进新冠病毒核酸检测的实施意见》，提出对“密切接触者”等八类重点人群“应检尽检”，其他人群“愿检尽检”。

问题描述
某市设有 n个核酸检测点，编号从 1 到 n，其中 i 号检测点的位置可以表示为一个平面整数坐标 (xi,yi)。为方便预约核酸检测，请根据市民所在位置 (x,y)，查询距其近的三个检测点。多个检测点距离相同时，编号较小的视为更近。
输入格式
输入共 n+1 行。

第一行包含用空格分隔的三个整数 n、x 和 y，表示检测点总数和市民所在位置。

第二行到第 n+1 行依次输入 n 个检测点的坐标。第 i+1(1<=i<=n) 行包含用空格分隔的两个整数 xi和 yi，表示 i 号检测点所在位置。

输出格式
输出共三行，按距离从近到远，依次输出距离该市民最近的三个检测点编号。

样例输入1
3 2 2
2 2
2 3
2 4
Data
样例输出1
1
2
3
Data
样例输入2
5 0 1
-1 0
0 0
1 0
0 2
-1 2
Data
样例输出2
2
4
1
Data
样例2解释

评测用例规模与约定
全部的测试点满足，s<=n<=200，所有坐标均为整数且绝对值不超过 1000。

提示
市民到第 i 号检测点的距离 可由如下公式算出：Di**2=(X-Xi)**2+(Y-Yi)**2

题目分析（个人理解）

1. 常规输入核酸点总数，居民所在位置n,X,Y=map(int,input().split())
2. 后面的每一行输入的是核酸检测点（x，y）我将每个核酸点与居民位置的距离追加写入列表 l[] 中。 l.append([i,math.sqrt((X-x) * (X-x)+(Y-y) * (Y-y))])
   sqrt（）函数是开根号函数。
3. 注意输出，我需要将距离最短的3个核酸点编号输出，如果存在距离相同的点，那么输出编号最小的检测点。
4. 如何实现？我可以遍历l[]的每一个索引和值，如果值比上线（两点最大距离：2000*$\sqrt{2}$)小那就替换，之后一直遍历（就是重复找最小的步骤）找到遍历完之后的最小值（距离）然后输出编号，由于该编号是从1开始到n,遍历找最小值的时候也是按照此顺序寻找，所以输出的时候就解决了距离相同时输出最小编号的问题，之后再将该项从列表中删除，执行以上操作（找最小输出编号）三次（只要三个点）然后执行一次输出一次即可。
5. 上代码！！！

import math
n,X,Y=map(int,input().split())
l=[]
for i in range(1,n+1):#编号从1开始
    x,y=map(int,input().split())
    l.append([i,math.sqrt((X-x)*(X-x)+(Y-y)*(Y-y))])#列表嵌套

for i in range(3):
    mc=0#记录最小距离索引
    mv=2829#记录最小距离
    for c,v in l:
        if v<mv:
            mc=c
            mv=v
    print(mc)
    l.remove([mc,mv])


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

题目二

试题编号： 202009-2
试题名称： 风险人群筛查
时间限制： 1.0s
内存限制： 256.0MB
问题描述：
题目背景
某地疫情爆发后，出于“应检尽检”的原则，我们想要通知所有近期经过该高危区域的居民参与核酸检测。

问题描述
想要找出经过高危区域的居民，分析位置记录是一种简单有效的方法。

具体来说，一位居民的位置记录包含 t 个平面坐标(x1,y1),…,(xi,yi) ，其中 xi,yi 表示该居民 i 时刻所在位置。
高危区域则可以抽象为一个矩形区域（含边界），左下角和右上角的坐标分别为 (xl,yd) 和 (xr,yu)，满足 xl

考虑某位居民的位置记录，如果其中某个坐标位于矩形内（含边界），则说明该居民经过高危区域；进一步地，如果其中连续 k 个或更多坐标均位于矩形内（含边界），则认为该居民曾在高危区域逗留。需要注意的是，判定经过和逗留时我们只关心位置记录中的 t 个坐标，而无需考虑该居民在 i 到 i+1 时刻之间位于何处。

给定高危区域的范围和 n位居民过去 t 个时刻的位置记录，试统计其中经过高危区域的人数和曾在高危区域逗留的人数。

输入格式
输入共n+1 行。

第一行包含用空格分隔的七个整数 n,k,t,xl,yd,xr,yu，含义如上文所述。

接下来 n 行，每行包含用空格分隔的 2t 个整数，按顺序表示一位居民过去 t 个时刻的位置记录 (x1,y1)…(xt,yt)

输出格式
输出共两行，每行一个整数，分别表示经过高危区域的人数和曾在高危区域逗留的人数。

样例输入1
5 2 6 20 40 100 80
100 80 100 80 100 80 100 80 100 80 100 80
60 50 60 46 60 42 60 38 60 34 60 30
10 60 14 62 18 66 22 74 26 86 30 100
90 31 94 35 98 39 102 43 106 47 110 51
0 20 4 20 8 20 12 20 16 20 20 20
Data
样例输出1
3
2
Data
样例1说明
如下图红色标记所示，前三条位置记录经过了高危区域；
但第三条位置记录（图中左上曲线）只有一个时刻位于高危区域内，不满足逗留条件。

样例输入2
1 3 8 0 0 10 10
-1 -1 0 0 0 0 -1 -1 0 0 -1 -1 0 0 0 0
Data
样例输出2
1
0
Data

样例2说明
该位置记录经过了高危区域，但最多只有连续两个时刻位于其中，不满足逗留条件。

评测用例规模与约定
全部的测试点满足 1<=n<=20，1<=k<=t<=10**3，所有坐标均为整数且绝对值不超过 10 **6。

题目分析（个人理解）

1. 还是先看题目输入：第一行输有n个人，连续k个，t个时刻，和高危区域四个坐标（矩形）判断是否是高危的条件。
2. 我还是选择列表存储所有数据，首先要判断是否经过，如果经过再判断是否续，连续还要判断是否大于等于K个，如果都满足上述条件那么，就是逗留。如果在高危区域的点小于k个那么就是经过。
3. 首先还是判断每个人每个点（每一时刻的位置）是否在矩形内，如果出现一次计数器就+1 如果计数器大于k那么就说明此人逗留了，如果小于k就说明此人经过。
4. 我设置con=1 表示连续出现的次数(不连续就是1，两个连续就是2) ，num[]列表存储每一个人每次连续出现的次数（也就是con的值），jg=0表示经过的人数，dl=0表示逗留的人数，两个开关 ，bl表示是否连续，bn判断是否经过，初始值都为False
5. 存好坐标后，循环t次判断在不在矩形内，在就 bn=True如果bl = =True那就说明上一个点也经过，con+=1，如果上一个点未经过，那就说明该点是第一次出现在矩形中，将con=1追加写入num[]中，不在矩形中的点将con=1写入num[]即可。
6. 如果每一次num中的最大值都大于等于k那么dl+=1，如果bn==True那么bn+=1,最后输出jg和dl即可。
7. 上代码！！！

n,k,t,xl,yd,xr,yr=map(int,input().split())
jg,dl=0,0
for i in range(n):
    l=list(map(int,input().split()))
    bl=False#判断是否连续
    bn=False#判断是否经过
    num=[]#存储每次连续的个数
    con=1#连续的次数
    for j in range(t):
        if xl<=l[2*j]<=xr and yd<=l[2*j+1]<=yr:#在高危区域内
            bn=True#经过
            if bl==True:#前一个坐标也经过
                con+=1
            else:
                num.append(con)
                con=1
            bl=True
        else:
            bl=False
    num.append(con)
    if bn==True:
        jg+=1
    if max(num)>=k:
        dl+=1
print(jg)
print(dl)


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

总结

把时间、精力、耐心多留给自己未尝不是一个正确的选择。

										——————shangzhaoyun 2023.10.7
1
2
3