时间戳

首页 > 技术文章 > CCF201604-Python题解

CCF201604-Python题解

z-712 2020-09-03 20:28 原文

折点计数

原题链接：http://118.190.20.162/view.page?gpid=T42

试题编号： 201604-1
试题名称： 折点计数
时间限制： 1.0s
内存限制： 256.0MB
问题描述：
问题描述
　　给定n个整数表示一个商店连续n天的销售量。如果某天之前销售量在增长，而后一天销售量减少，则称这一天为折点，反过来如果之前销售量减少而后一天销售量增长，也称这一天为折点。其他的天都不是折点。如下图中，第3天和第6天是折点。
   
　　给定n个整数a1, a2, …, an表示销售量，请计算出这些天总共有多少个折点。
　　为了减少歧义，我们给定的数据保证：在这n天中相邻两天的销售量总是不同的，即ai-1≠ai。注意，如果两天不相邻，销售量可能相同。
输入格式
　　输入的第一行包含一个整数n。
　　第二行包含n个整数，用空格分隔，分别表示a1, a2, …, an。
输出格式
　　输出一个整数，表示折点出现的数量。
样例输入
7
5 4 1 2 3 6 4
样例输出
2
评测用例规模与约定
　　所有评测用例满足：1 ≤ n ≤ 1000，每天的销售量是不超过10000的非负整数。

 

题解：找两种情况（1）1<4>2，（2）6>3<4  也就是“凹凸”

 1 n = int(input())
 2 b = input().split()
 3 a = [0]*len(b)
 4 
 5 for i in range(len(b)):
 6     a[i] = int(b[i])
 7 
 8 find = 0
 9 for i in range(1, len(a)-1):
10     if a[i-1] < a[i] and a[i] > a[i+1]:
11         # print("find",a[i-1], a[i], a[i+1])
12         find += 1
13     if a[i-1] > a[i] and a[i] < a[i+1]:
14         # print("find",a[i-1], a[i], a[i+1])
15         find += 1
16 
17 print(find)

 

 

俄罗斯方块

原题链接：http://118.190.20.162/view.page?gpid=T41

试题编号： 201604-2
试题名称： 俄罗斯方块
时间限制： 1.0s
内存限制： 256.0MB
问题描述：
问题描述
　　俄罗斯方块是俄罗斯人阿列克谢·帕基特诺夫发明的一款休闲游戏。
　　游戏在一个15行10列的方格图上进行，方格图上的每一个格子可能已经放置了方块，或者没有放置方块。每一轮，都会有一个新的由4个小方块组成的板块从方格图的上方落下，玩家可以操作板块左右移动放到合适的位置，当板块中某一个方块的下边缘与方格图上的方块上边缘重合或者达到下边界时，板块不再移动，如果此时方格图的某一行全放满了方块，则该行被消除并得分。
　　在这个问题中，你需要写一个程序来模拟板块下落，你不需要处理玩家的操作，也不需要处理消行和得分。
　　具体的，给定一个初始的方格图，以及一个板块的形状和它下落的初始位置，你要给出最终的方格图。
输入格式
　　输入的前15行包含初始的方格图，每行包含10个数字，相邻的数字用空格分隔。如果一个数字是0，表示对应的方格中没有方块，如果数字是1，则表示初始的时候有方块。输入保证前4行中的数字都是0。
　　输入的第16至第19行包含新加入的板块的形状，每行包含4个数字，组成了板块图案，同样0表示没方块，1表示有方块。输入保证板块的图案中正好包含4个方块，且4个方块是连在一起的（准确的说，4个方块是四连通的，即给定的板块是俄罗斯方块的标准板块）。
　　第20行包含一个1到7之间的整数，表示板块图案最左边开始的时候是在方格图的哪一列中。注意，这里的板块图案指的是16至19行所输入的板块图案，如果板块图案的最左边一列全是0，则它的左边和实际所表示的板块的左边是不一致的（见样例）
输出格式
　　输出15行，每行10个数字，相邻的数字之间用一个空格分隔，表示板块下落后的方格图。注意，你不需要处理最终的消行。
样例输入
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0
1 1 1 0 0 0 1 1 1 1
0 0 0 0 1 0 0 0 0 0
0 0 0 0
0 1 1 1
0 0 0 1
0 0 0 0
3
样例输出
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 0 0 0 0

 

题外话：这个题目挺有意思的，没有涉及到什么图论里面的算法，也不是什么图的搜索，咋一看吓死人无从下手，这个才是第二题，信息量比较大，正常人看完题目首先想到的是找规律，这个题目要是找规律你就亏大了，因为你会浪费很多时间，而且找完规律也很难拿到100分。ccf就喜欢出这种题目，叫做“动态模拟执行”，特别是图里面的，你可以看每年ccf出的题目，五道题至少有三道是图，当然用的算法是不一样的。[1]

解题思路：
1.我们可以模拟俄罗斯方块下降的过程直到不再下降，最后输出整个矩阵，程序就结束了。
2.我们需要输入的有两个矩阵，大矩阵15×10记作A，小矩阵4×4记作b（就是存放俄罗斯方块的）,我们需要把整个矩阵A存起来，因为题目的答案就是对最后的A输出。
3. 最后模拟板块下降的过程，若有碰撞则发生碰撞上一行就是最终确定的位置，若板块与方格图某个位置都为1即为碰撞了产生重叠，这个位置两项加起来为2，判断板块与方格图每项分别加起来是否有2就能确认是否碰撞。

 1 A=[list(map(int, input().split())) for _ in range(15)]
 2 b=[list(map(int, input().split())) for _ in range(4)]
 3 n=int(input())
 4 
 5 #扩展三行
 6 for i in range(3):
 7     A.insert(len(A), [0]*10)
 8 
 9 
10 #避免下落不到位    b：4*4
11 drop=12
12 for i in range(4):
13     if sum(b[3-i])==0:
14         drop+=1
15     else:
16         break
17 
18 
19 def IsTrue(p,bk):
20     res=[[0]*4 for _ in range(4)]
21     for i in range(4):
22         for j in range(4):
23             res[i][j]=p[i][j]+bk[i][j]
24     for k in range(4):
25         if 2 in res[3-k]:
26             return False, res
27         else:
28             continue
29     return True,res
30 
31 t=0
32 tre=[[0]*4 for _ in range(4)]
33 for m in range(drop):
34     dd = [l[n-1:n+3] for l in A[m:m+4]]
35     flag,re=IsTrue(dd,b)
36     if flag:
37         t=m
38         tre=re
39     else:
40         break
41 
42 # 修改初始矩阵值
43 for c in range(4):
44     A[t:t+4][c][n-1:n+3]=tre[c]
45 
46 for o in range(15):
47     for p in range(10):
48         print(A[o][p], end=' ')
49     print()

 

 

 路径解析

试题编号： 201604-3
试题名称： 路径解析
时间限制： 1.0s
内存限制： 256.0MB
问题描述：
问题描述
　　在操作系统中，数据通常以文件的形式存储在文件系统中。文件系统一般采用层次化的组织形式，由目录（或者文件夹）和文件构成，形成一棵树的形状。文件有内容，用于存储数据。目录是容器，可包含文件或其他目录。同一个目录下的所有文件和目录的名字各不相同，不同目录下可以有名字相同的文件或目录。
　　为了指定文件系统中的某个文件，需要用路径来定位。在类 Unix 系统（Linux、Max OS X、FreeBSD等）中，路径由若干部分构成，每个部分是一个目录或者文件的名字，相邻两个部分之间用 / 符号分隔。
　　有一个特殊的目录被称为根目录，是整个文件系统形成的这棵树的根节点，用一个单独的 / 符号表示。在操作系统中，有当前目录的概念，表示用户目前正在工作的目录。根据出发点可以把路径分为两类：
　　Ÿ 绝对路径：以 / 符号开头，表示从根目录开始构建的路径。
　　Ÿ 相对路径：不以 / 符号开头，表示从当前目录开始构建的路径。
　　例如，有一个文件系统的结构如下图所示。在这个文件系统中，有根目录 / 和其他普通目录 d1、d2、d3、d4，以及文件 f1、f2、f3、f1、f4。其中，两个 f1 是同名文件，但在不同的目录下。
对于 d4 目录下的 f1 文件，可以用绝对路径 /d2/d4/f1 来指定。如果当前目录是 /d2/d3，这个文件也可以用相对路径 ../d4/f1 来指定，这里 .. 表示上一级目录（注意，根目录的上一级目录是它本身）。还有 . 表示本目录，例如 /d1/./f1 指定的就是 /d1/f1。注意，如果有多个连续的 / 出现，其效果等同于一个 /，例如 /d1///f1 指定的也是 /d1/f1。
　　本题会给出一些路径，要求对于每个路径，给出正规化以后的形式。一个路径经过正规化操作后，其指定的文件不变，但是会变成一个不包含 . 和 .. 的绝对路径，且不包含连续多个 / 符号。如果一个路径以 / 结尾，那么它代表的一定是一个目录，正规化操作要去掉结尾的 /。若这个路径代表根目录，则正规化操作的结果是 /。若路径为空字符串，则正规化操作的结果是当前目录。
输入格式
　　第一行包含一个整数 P，表示需要进行正规化操作的路径个数。
　　第二行包含一个字符串，表示当前目录。
　　以下 P 行，每行包含一个字符串，表示需要进行正规化操作的路径。
输出格式
　　共 P 行，每行一个字符串，表示经过正规化操作后的路径，顺序与输入对应。
样例输入
7
/d2/d3
/d2/d4/f1
../d4/f1
/d1/./f1
/d1///f1
/d1/
///
/d1/../../d2
样例输出
/d2/d4/f1
/d2/d4/f1
/d1/f1
/d1/f1
/d1
/
/d2
评测用例规模与约定
　　1 ≤ P ≤ 10。
　　文件和目录的名字只包含大小写字母、数字和小数点 .、减号 - 以及下划线 _。
　　不会有文件或目录的名字是 . 或 .. ，它们具有题目描述中给出的特殊含义。
　　输入的所有路径每个长度不超过 1000 个字符。
　　输入的当前目录保证是一个经过正规化操作后的路径。
　　对于前 30% 的测试用例，需要正规化的路径的组成部分不包含 . 和 .. 。
　　对于前 60% 的测试用例，需要正规化的路径都是绝对路径。

 题解：判空、模拟

 

 1 from copy import deepcopy
 2 def res_record(path):
 3     index=0
 4     lens=len(path)
 5     while index<lens:
 6         if path[index]=='.':
 7             del path[index]
 8             lens-=1
 9         elif path[index]=='..':
10             del path[index]
11             if index==0:
12                 lens-=1
13             else:
14                 index-=1
15                 del path[index]
16                 lens-=2
17         elif path[index]=='':
18             del path[index]
19             lens-=1
20         else:
21             index+=1
22     return path
23         
24 n=int(input())
25 current_path=input().split('/')
26 res=[]
27 for _ in range(n):
28     tmp=input()
29     if tmp=='': #空
30         tmp=current_path
31     elif tmp[0]=='/': #绝对路径
32         tmp=tmp.split('/')
33     else: #相对路径
34         cur=deepcopy(current_path) #这里注意一下，要用deepcopy，浅copy会改变current_path，影响后面的操作
35         cur.extend(tmp.split('/'))
36         tmp=cur
37     res.append(res_record(tmp))
38 
39 for ele in res:
40     print('/'+'/'.join(ele))

 

 

 

 

 

参考链接

http://ddrv.cn/a/603548

推荐阅读