CCF-CSP真题《202209-3—防疫大数据》思路+python题解

想查看其他题的真题及题解的同学可以前往查看：CCF-CSP真题附题解大全

试题编号：202209-3试题名称：防疫大数据时间限制：1.0s内存限制：512.0MB问题描述：

题目背景

近期，国内 COVID-19 疫情多点散发，西西艾弗岛的防疫形势也异常严峻。西西艾弗岛疫情防控指挥部决定在岛上建立一套疫情风险监测系统。这套风险监测系统的主要功能是，收集手机用户到访地区的信息，根据用户的到访地区，判断用户的疫情风险。具体而言，在每天夜里，西西艾弗岛大数据运行管理中心都会收到一批手机用户到访地区的信息，以及当天疫情风险地区的信息。数据中心需要根据这些信息，生成一份存在风险的手机用户的名单，提供给疫情防控指挥部，以便进行后续的疫情防控工作。

题目描述

为了简化和便于处理问题，我们用连续的整数来表示日期，例如 -1、0、1、2 就是连续的 4 个日期。每日收到的漫游数据分为若干条，每条表示某一个用户在某日到访过某地区，记为：〈d,u,r〉，其中，u 表示用户，r 表示地区，它们都是一个正整数；d 表示日期，是一个整数。每日收到的漫游数据中，可能会有这样的数据，需要在处理的过程中考虑：

• 延迟数据：即在某日收到的漫游数据中，日期小于当日的日期。例如，在 2 日收到的某条漫游数据，内容是某用户在 1 日到访过某地区；
• 重复数据：即在某日收到的漫游数据中，可能存在两条完全相同的数据；
• 多地访问数据：即在某日收到的漫游数据中，存在两条数据，其日期和用户相同，但地区不同。

每日收到的疫情风险地区的信息，是一个列表，列表中的每个元素表示某个地区在某日被列为疫情风险地区。收到该消息的当日起 7 日内，该地区处于风险状态。即对于地区 r，我们称 r 在 d 日处于风险状态，当且仅当存在一个日期 d0∈(d−7,d]，在 d0 日收到地区 r 的风险信息。例如，在 1 日收到地区 1 的风险信息，表示自 1 日（包含）至 8 日（不包含）地区 1 处于风险状态。如果分别在 1 日和 6 日收到地区 1 的风险信息，那么意味着地区 1 自 1 日（包含）至 13 日（不包含）持续处于风险状态。

每日生成的存在风险的手机用户的名单，是一个列表，列表中的每个元素表示某个用户被认为存在疫情风险。我们认为，同时满足下列条件的用户，会被列入当日生成的风险名单：

• 该用户在近 7 日内曾经出现在接收到的漫游数据中，并且近 7 日内有到访某个地区的记录；
• 该用户在近 7 日内到访的地区在到访的那一日处于风险状态；
• 上述存在风险的地区自到访日至生成名单当日持续处于风险状态。

形式化地，在 d 日生成的风险名单中，用户 u 被列入风险名单，当且仅当：

存在一个日期 d0∈(d−7,d]，存在一条 d0 日收到的漫游数据 〈d1,u,r〉，使得

• d1∈(d−7,d]，并且
• 对于任意的 D∈[d1,d]，地区 r 在 D 日处于风险状态。

例如，在第 0 日收到下列漫游数据：

〈0,1,1〉；〈−1,1,1〉；〈−1,2,1〉；〈0,2,2〉

又在第 0 日收到了 1 号地区为风险地区的消息，那么此后第 0 日（包含）至第 7 日（不包含），1 号地区都处于风险状态。

在第 0 日生成的风险名单中，用户 1 被列入风险名单，因为用户 1 在第 0 日到访了 1 号地区。用户 2 不被列入风险名单，因为用户 2 在第 0 日到访了 2 号地区，但是在第 0 日 2 号地区不是风险地区；虽然用户 2 在第 -1 日到访了 1 号地区，但是在第 -1 日 1 号地区不是风险地区。

假设在第 1 日，又收到下列漫游数据：

〈0,3,1〉；〈1,2,2〉；〈1,3,2〉

同时没有收到新的风险地区的消息，那么在第 1 日生成的风险名单中，用户 1 和 3 被列入风险名单，因为刚收到的信息显示用户 3 在第 0 日到访了 1 号地区，而用户 1 在第 0 日到访了 1 号地区，且在第 1 日 1 号地区仍处于风险状态，虽然第 1 日没有收到用户 1 的漫游数据，但是仍然将用户 1 列入风险名单。

假设后续没有收到更多漫游数据和风险地区信息，直到第七日，收到下列漫游数据：

〈5,4,1〉

同时没有收到新的风险地区的消息，此时，没有用户被列入风险名单。例如对于用户 4，虽然在第 5 日到访了 1 号地区，但是生成风险名单的当日，1 号地区已经不是风险地区。

假设在第 8 日，没有收到更多的漫游数据，但是收到了 1 号地区为风险地区的消息，那么在第 8 日生成的风险名单中，也没有用户被列入风险名单。因为在第 7 日，地区 1 不处于风险状态，用户 4 在第 5 日到访了 1 号地区，虽然第 5 日和本日（第 8 日）地区 1 处于风险状态，但是，由于不满足持续处于风险状态的条件，用户 4 不被列入风险名单。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 n，表示总共输入数据的天数。

接下来是 n 组数据，依次表示自第 0 日开始每一天的输入数据。

对于第 i 日的一组数据，其第一行内，包含空格分隔的两个非负整数 ri、mi，以及 ri 个正整数 pi,j（i=0,1,…,(n−1), j=1,2,...,ri），分别表示当日收到的风险地区信息的数量、当日收到的漫游数据的条目数量，以及当日收到的风险地区的列表。

每组数据接下来有 mi 行，每行包含空格分隔的一个整数和两个正整数 di,j、ui,j、ri,j（j=1,2,…,mi），分别表示一条漫游数据中的日期、用户和地区。

输出格式

输出到标准输出。

输出 n 行，自第 0 天起，按顺序输出各日运算产生的疫情风险名单。每行包含空格分隔的若干整数。其中第一个整数表示当天的日期，接下来的各个整数为按从小到大排序的存在风险的用户列表。

样例输入

9
1 4 1
0 1 1
-1 1 1
-1 2 1
0 2 2
0 3
0 3 1
1 2 2
1 3 2
0 0
0 0
0 0
0 0
0 0
0 1
5 4 1
1 0 1

样例输出

0 1
1 1 3
2 1 3
3 1 3
4 1 3
5 1 3
6 1 3
7
8

样例解释

本样例数据即为题目描述中所叙述的情况。

子任务

对于前 20% 的数据，有 ri=mi=0,(i=1,2,…(n−1))；

对于前 40% 的数据，有 ri=0,(i=1,2,…(n−1))；

对于前 70% 的数据，对所有的 i 与 j，都有 pi,j≤400，ui,j≤400，且 ri,j≤400；并且对所有的 i，都有 ri≤300，且 mi≤300；

对于 100% 的数据，对所有的 i 与 j，都有 1≤pi,j≤109，1≤ui,j≤109，1≤ri,j≤109，且 −105≤di,j≤i；对所有的 i∈[0,n)，都有 0≤ri≤1000，且 0≤mi≤1000；并且 0≤n≤1000；对所有的 i∈[0,n)，和任意的 j1,j2∈[1,ri],j1≠j2，都有 pi,j1≠pi,j2。

真题来源：防疫大数据

解题思路：

    这题感觉应该是读题比较难，建议那个笔写一遍捋一下情况，每个值是干嘛的搞清楚才开始写，然后就按要求写，但因为原先没考虑题中的三个特殊情况，属于读题不严，得到10分代码；

10分题解：

# 输入n，代表数据的天数
n = int(input())
# 设置place来存储每天的风险地区
place = {}
# 设置people来存储用户的漫游数据
people = {}
# 开始遍历每一天
for i in range(n):
    # people[i]来存储每一天的漫游信息
    people[i] = []
    # 输入当日收到的风险地区信息的数量、当日收到的漫游数据的条目数量，以及当日收到的风险地区的列表
    data = [i for i in map(int,input().split())]
    # 表示当日收到的风险地区信息的数量
    r = data[0]
    # 表示当日收到的漫游数据的条目数量
    m = data[1]
    # 存储当日收到的风险地区的列表
    if r!=0:
        for d in data[2:]:
            # 遍历将从今日起的风险地区标记七日风险
            for q in range(i,i+7):
                if q not in place:
                    place[q] = set()
                place[q].add(d)
    # 接收漫游信息，并存储到people[i]中去
    if m!=0:
        for j in range(m):
            ud,u,ur = map(int,input().split())
            if ud<0:
                continue
            people[i].append([ud,u,ur])
    # 设置t，确保日期循环最早从第0天开始
    t = max(0,i-6)
    # 存储输出日期及用户
    out = []
    # 提取此前七天每天用户的漫游信息
    for h in range(t,i+1):
        # 用hu存储当前天的用户漫游信息
        hu = people[h]
        # 开始遍历hu中的漫游信息
        for k in range(len(hu)):
            d = hu[k][0]
            u = hu[k][1]
            r = hu[k][2]
            if d<(i-6):
                continue
            # 设置一个标签值
            temp = 1
            # 判断是否持续处于风险区
            for l in range(d,i+1):
                if l not in place:
                    temp = 0   
                    break
                if r not in place[l]:
                    temp = 0   
                    break
            if temp:
                out.append(u)
            # 将用户从小到大排序
            out.sort()
    # 插入日期
    out.insert(0,i)
    print(*out)

**运行结果： **

**40分题解： **

改进项：

增加了对重复数据的一个筛选去重，将分数提升到40分了；

# 输入n，代表数据的天数
n = int(input())
# 设置place来存储每天的风险地区
place = {}
# 设置people来存储用户的漫游数据
people = {}
# 开始遍历每一天
for i in range(n):
    # people[i]来存储每一天的漫游信息
    people[i] = []
    # 输入当日收到的风险地区信息的数量、当日收到的漫游数据的条目数量，以及当日收到的风险地区的列表
    data = [i for i in map(int,input().split())]
    # 表示当日收到的风险地区信息的数量
    r = data[0]
    # 表示当日收到的漫游数据的条目数量
    m = data[1]
    # 存储当日收到的风险地区的列表
    if r!=0:
        for d in data[2:]:
            # 遍历将从今日起的风险地区标记七日风险
            for q in range(i,i+7):
                if q not in place:
                    place[q] = set()
                place[q].add(d)
    # 接收漫游信息，并存储到people[i]中去
    if m!=0:
        for j in range(m):
            ud,u,ur = map(int,input().split())
            if ud<0:
                continue
            people[i].append([ud,u,ur])
    # 设置t，确保日期循环最早从第0天开始
    t = max(0,i-6)
    # 存储输出日期及用户
    out = []
    # 提取此前七天每天用户的漫游信息
    for h in range(t,i+1):
        # 用hu存储当前天的用户漫游信息
        hu = people[h]
        # 开始遍历hu中的漫游信息
        for k in range(len(hu)):
            kd = hu[k][0]
            ku = hu[k][1]
            kr = hu[k][2]
            if d<(i-6):
                continue
            # 设置一个标签值
            temp = 1
            # 判断是否持续处于风险区
            for l in range(kd,i+1):
                if l not in place:
                    temp = 0   
                    break
                if kr not in place[l]:
                    temp = 0   
                    break
            if temp:
                out.append(ku)
            # 将用户进行去重并从小到大排序
            out = list(set(out))
            out.sort()
    # 插入日期
    out.insert(0,i)
    print(*out)

**运行结果： **

满分题解：

改进项：