CCF CSP认证历年题目自练Day30

题目一

试题编号： 202203-1
试题名称：未初始化警告
时间限制： 1.0s
内存限制： 512.0MB
问题描述：
题目背景
一个未经初始化的变量，里面存储的值可能是任意的。因此直接使用未初始化的变量，比如将其赋值给另一个变量，并不符合一般的编程逻辑。代码中出现这种情况，往往是因为遗漏了初始化语句、或是打错了变量名。对代码中使用了未初始化变量的语句进行检查，可以方便地排查出代码中的一些隐秘 Bug。
在这里插入图片描述
样例输入
10 7
1 2
3 3
3 0
3 3
6 2
2 1
8 2
Data
样例输出
3
Data
样例解释
其中第一、二、五条赋值语句右值未被初始化。

子任务
50% 的测试数据满足 0<n,k<=1000；

全部的测试数据满足 0<n,k<=10**5

题目分析（个人理解）

还是先看题目，第一行输入n个变量，输入k个赋值语句。之后的k行输入变量，空格，变量/常量。
从第二行开始，第一个数值只能是变量，之后要去进行判断哪些是不合法的赋值语句，如果左边的变量在前面的赋值语句中的右值中出现过，那么就是合法，否则就是不合法。
如何在算法中实现？这无疑是一个判断问题，判断是否存在的问题，我选择用列表来表示，首先创建一个长度为n+1的列表，注意输入要求左边的变量从1开始，我用列表的位序表示左边变量的值（xi），如果左边变量存在，那么对应列表的位置的值就设置为1，如果左边变量的值不存在，那么列表对应的值就为0，最后只需要判断列表中以yi为位序判断x中的值为0的个数就是不符合赋值条件的语句的个数。这里注意判断条件（是0对应的就是不符合赋值条件，计数器就要加1，所以要在x[0]=1）。
上代码！！！

n,k = map(int,input().split())
x = [0]*(n+1)
s = 0
x[0] = 1
for i in range(k):xi,yi = map(int,input().split())if x[yi] ==0 :s += 1x[xi] = 1
print(s)

第二种方法，用元组存储，反而比列表还要方便一些，还是先将xi存在元组x中，判断yi如果不在xi中且yi不等于0，那么就说明不赋值语句不合法，然后计数器加1。当然yi是0一定是合法的，0在本题只可能是值，而不可能是变量（题目要求的范围）。
上代码！！！

n,k = map(int,input().split())
x = set()
s = 0
for i in range(k):xi,yi = map(int,input().split())if yi not in x and yi != 0:s += 1x.add(xi)
print(s)

题目二

试题编号： 202203-2
试题名称：出行计划
时间限制： 1.5s
内存限制： 512.0MB
问题描述：
问题描述
最近西西艾弗岛上出入各个场所都要持有一定时限内的核酸检测阴性证明。

具体来时，如果在 t 时刻做了核酸检测，则经过一段时间后可以得到核酸检测阴性证明。这里我们假定等待核酸检测结果需要 k 个单位时间，即在 t+k 时刻可以获得结果。如果一个场所要求持 24 个单位时间内核酸检测结果入内，那么凭上述的核酸检测结果，可以在第 t+k 时刻到第 t+k+23 时刻进入该场所。

小 C 按时间顺序列出接下来的 n 项出行计划，其中第 i 项（1≤i≤n）可以概括为：
ti 时刻进入某场所，该场所需持有 ci 个单位时间内的核酸检测结果入内，其中 0<ci≤2×10**5。

为了合理安排核酸检测时间，试根据小 C 的出行计划，回答如下查询：

如果在 q 时刻做了核酸检测，有多少项出行计划的核酸检测要求可以得到满足？
这样的查询共有 m 个，分别为 q1,q2,⋯,qm；查询之间互不影响。

输入格式
输入的第一行包含空格分隔的三个正整数 n、m 和 k，分别表示出行计划数目、查询个数以及等待核酸检测结果所需时间。

接下来输入 n 行，其中每行包含用空格分隔的两个正整数 ti、ci，表示一项出行计划；出行计划按时间顺序给出，满足 0<t1≤t2≤⋯≤tn≤2×10**5。

最后输入 m 行，每行仅包含一个正整数 qi，表示一个查询。m 个查询亦按照时间顺序给出，满足 0<q1<q2<⋯<qm≤2×10**5。

输出格式
输出共 m 行，每行一个整数，表示对应查询的答案。

样例输入
6 2 10
5 24
10 24
11 24
34 24
35 24
35 48
1
2

样例输出
3
3

样例解释
时刻 1 做检测，可以满足第三、四、六项出行计划；

时刻 2 做检测，可以满足第四、五、六项出行计划。

子任务
40% 的测试数据满足 0<n,k≤1000、m=1；

70% 的测试数据满足 0<n,m,k≤1000；

全部的测试数据满足 0<n,m,k≤10**5

题目分析（个人理解）

还是先理解题目，看输入，第一行含空格分隔的三个正整数 n、m 和 k，分别表示出行计划数目、查询个数以及等待核酸检测结果所需时间。后面的n行输入的是到达时间空格需要多少小时的核酸（才能进入场所）。最后的m行是表示从什么时候做的核酸。
我选择用列表存储n行出行计划。用二维列表need_time_list将出行计划全部转换为核算出结果有效区间，依次遍历每个查询对应的出结果时间。
上代码！！！但是超过时间限制。必须优化算法。

#运行超时只能70分
# n：出行计划数，m：查询个数，k：核酸等待所需时间
n, m, k = map(int, input().split())
# valid
need_time_list = []
for w in range(n):t, c = map(int, input().split())need_time_list.append([t-c+1, t])start = 0 # 上一个有效的起点
#两层循环时间复杂度一下增上去了
for w in range(m):q = int(input()) + kres = 0for i in range(start, n):if q > need_time_list[i][1]:start += 1continueif need_time_list[i][0]<=q:res += 1print(res)

第二种方法前缀和思想：
每个出行计划就是对有效区间的操作。最后前缀和统计一下，随后查询即可。
5.== 还是用二维列表来实现，将每一次的出行计划的ti ci 存入列表。找到所有子列表中第一个整数的最大值num，并处理子列表以确保第二个整数表示最后一个有效整数。==
读入包含m个整数的列表，并将每个整数加上k，存入times列表；创建长度为num*2的临时列表temp，里面的值全部赋值为0；对于每个子列表，将位于该子列表第一个整数处的索引处的值加1，将位于该子列表第二个整数+1处的索引处的值减1。然后计算临时列表的前缀和。最后对于times列表中的每个整数，在临时列表temp中打印索引等于（该整数+k）的值即可。

#满分
# 读入三个整数n、m和k
n, m, k = map(int,input().split())# 读入包含n个子列表的列表，每个子列表包含两个整数
spots = [[i for i in map(int, input().split())] for j in range(n)]# 找到所有子列表中第一个整数的最大值num，并处理子列表以确保第二个整数表示最后一个有效整数
num = 0
for i in range(n):if num < spots[i][0]:num = spots[i][0]+1spots[i][0], spots[i][1] = max(1,spots[i][0]-spots[i][1]+1), spots[i][0]# 读入包含m个整数的列表，并将每个整数加上k，存入times列表
times = []
for i in range(m):point = int(input())times.append(point+k)# 创建长度为num*2的临时列表temp，用零初始化
temp = [0 for i in range(num*2)]# 对于每个子列表，将位于该子列表第一个整数处的索引处的值加1，将位于该子列表第二个整数+1处的索引处的值减1。
for spot in spots:temp[spot[0]] += 1temp[spot[1]+1] -= 1# 计算临时列表的前缀和
for i in range(1,num+1):temp[i] += temp[i-1]# 对于times列表中的每个整数，在临时列表temp中打印索引等于（该整数+k）的值
for time in times:print(temp[time])

第三种方法采用一维列表做，还是超时70分，核心思想没变。
extend() 函数
用于在列表末尾一次性追加另一个序列中的多个值（用新列表扩展原来的列表）。
1、extend()方法只能将值添加到列表的末尾
2、extend()方法只能传入序列
上代码！！！

#只能拿70分，运行超时
n, m, k = map(int, input().strip().split())
day_l=[]
time_l=[]
for i in range(n+m):if i < n:day_l.extend(map(int, input().split()))else:time_l.extend(map(int, input().split()))for i in time_l:sum_l = 0for j in range(0,n*2, 2):if  i+k<=day_l[j]<i+k+day_l[j+1]:sum_l += 1print(sum_l)