2019 csp s day1.pdf

所需积分/C币:5 2019-11-16 164KB PDF
评分

noip2019提高组真题 第一天 PDF 完整版,新鲜出炉 包含考试说明注意事项等等
2019年CCF非专业级软件能力认证第二轮提高级 dav1格雷杩(code) 格雷码(code) 题目描述】 通常,人们习惯将所有η位二进制串按照字典序排列,例如所有2位二进制串按 字典序从小到人排列为:00,01,10,11 格雷码( Gray code)是种特殊的n位二进制串排列法,它要求相邻的两个二进 制串间恰好有一位不同,特别地,第一个串与最后一个串也算作相邻 所有2位二进制牛按格雷码排列的一个例子为:00,01,11,10。 n位格雷码不止一种,下面给出其中一种格畫码的生成算法 1.1位格雷码由两个1位二进制组成,顺序为:0,1。 2.n+1位格雷码的前αn个二进制串,可以由依此算法生成的n位格雷码(总共 2个n位二进制中)按顺序排列,再在每个串前加一个前缀0构成。 3.n+1位格雷码的后2n个二进制串,可以由依此算法生成的n位格雷码(总共 2"个n位二进制串)按逆序排列,再在每个串前加一个前缀1构成 综上,η+1位格雷码,由n位格雷码的2个二进制串按顺序排列再加前缀O,和 按逆序排列再加前缀1构成,共2+1个二进制串。另外,对于n位格雷码中的2个 二进制串,我们按上述算法得刭的排列顺序将它们从0~2n-1编号。 按该算法,2位格雷码可以这样推出: 1.已知1位格雷码为0,1。 2.前两个格雷码为00,01。后两个格雷码为11,10。合并得到00,01,11,10, 编号依次为0~3。 同理,3位格雷码可以这样推出 已知2位格雷码为:00,01,11,10。 2.前四个格雷码为:000,001,O11,O10。后四个格雷码为:10,111,101, 100。合并得到:000,001,011,010,110,111,101,100,编号依次为0~7。 现在给出n,k,请你求出按上述算法生成的n位格雷码中的k号二进制串。 【输入格式】 从文件code.m中读入数据。 仅一行两个整数n,k,意义见题目描述 【输出格式】 输出到文件code.ot中。 仅一行一个n位二进制串表示答案 第3页共10页 2019年CCF非专业级软件能力认证第二轮提高级 lav1格雷杩(code) 【样例1输入】 【样例1输出】 【样例1解释】 2位格雷码为:00,01,11,10,编号从0~3,因此3号串是10。 【样例2输入】 35 【样例2输出】 111 【样例2解释】 3位格雷码为:000,001,011,010,110,111,101,100,编号从0~7,因此5 号串是111 【样例3】 见选于日录下的code/code3.im与code/code3,.ms 【数据范围】 对于50%的数据:n≤10 对于80%的数据:k≤5×106 对于95%的数据:k≤263-1 对于100%的数据:1≤n≤64.0≤k<2n 第4页共10页 2019年CCF非专业级软件能力认证第二轮提高级 day1括号树( brackets) 括号树( brackets) 题目背景】 本题中合法括号串的定义如下: 1.()是合法括号串 2.如果A是合法括号串,则(A)是合法括号串。 3.如果A,B是合法括号串,则AB是合法括号串。 本题中子串与不同的子串的定义如下: 1.字符串S的子串是S中连续的任意个字符组成的字符串。S的子串可用起始位 冒l与终止位置r来表示,记为S(l,r)(1≤l≤r≤S,S表示S的长度)。 2.S的两个子串视作不同当且仅当它们在S中的位置不同,即不同或r不同。 题目描述】 个大小为n的树包含n个结点和n-1条边,每条边连接两个结点,且任意两个 结点间有且仅有一条简单路径互相可达。 Q是一个充满好奇心的小朋友,有一天他在上学的路上碰见了一个大小为n的 树,树上结点从1~n编号,1号结点为树的根。除1号结点外,每个结点有一个父亲 结点,(2≤u≤n)号结点的父亲为f(1≤f<u)号结点 小Q发现这个树的每个结点上恰有一个括号,可能是(或)小Q定义s;为:将 根结点到讠号结点的简单路径上的括号,按结点经过顺序依次排列组成的字符串。 显然s是个括号串,但不一定是合法括号串,因此现在小Q想对所有的i(1≤i≤n) 求出,s;中有多少个互不相同的子串是合法括号串。 这个问题难倒了小Q,他只好向你求助。设s;共有k;个不同子串是合法括号串, 你只需要告诉小Q所有ixk的异或和,即: (1×k1)xor(2×k2)xor(3×k3)xor…xor(n×k) 其中ⅹor是位异或运算。 【输入格式】 从文件 brackets.i中读入数据 第一行一个整数n,表示树的大小。 第二行一个长为n的由(与)组成的括号串,第i个括号表示i号结点上的括号 第三行包含n-1个整数,第i(1≤i<n)个整数表小i+1号结点的父亲编号f+1 第5页共10页 2019年CCF非专业级软件能力认证第二轮提高级 day1括号树( brackets) 【输出格式】 输出到文件 brackets.out中 仅一行一个整数表示答案。 【样例1输入】 (()() 1122 【样例1输出】 【样例1解释】 树的形态如下图: 将根到1号结点的简单路径上的拈号,按绛过顺序排列所组成的字符串为(,子串 是合法括号串的个数为0 将根到2号结点的简单路径上的括号,按绎过顺序排列所组成的字符串为(,子 串是合法括号串的个数为0。 将根到3号结点的简单路径上:的括号,按绎过顺序排列所组成的字符串为(,子 串是合法括号串的个数为1。 将根到4号结点的简单路径上的拈号,按终过顺序排列所组成的字符串为((,子 串是合法括号串的个数为0。 将根到5号结点的简单路径上的括号,按经过顺序排列所组成的字符串为(,子 串是合法括号串的个数为1。 【样例2】 见选手目录下的 brackets/ brackets. in与 brackets/ brackets2am8 第6页共10页 2019年CCF非专业级软件能力认证第二轮提高级 day1括号树( brackets) 【样例3】 见选手目录下的 brackets/ brackets.9in与 brackets/ brackets9ams 数据范围】 测试点编号n≤特殊性质 3~4 200J 5~7 2000 8~10 无 11~14 fi= i 10 15~16 无 17~205×10 第7页共10页 2019年CCF非专业级软件能力认证第二轮提高级 day1树上的数(tree) 树上的数(tree) 【题目描述】 给定一个大小为n的树,它共有n个结点与n-1条边,结点从1~n编号。初始 时每个结点上都有一个1~n的数字,且每个1~n的数字都只在恰好一个结点上出现 接下来你需要进行恰好η-1次删边操作,每次操作你需要选一条未被删去的边, 此时这条边所连接的两个结点上的数字将会交换,然后这条边将被删去。 n-1次操作过后,所有的边都将被删去。此时,按数字从小到大的顺序,将数字 1~n所在的结点编号依次排列,就得到一个结点编号的排列P。现在请你求出,在最 优操作方案下能得到的字典序最小的P 2 3 5 如上图,蓝圈中的数字1~5一廾始分别在结点②、①、③、⑤、④。按照(1)(4)(3)(2 的顺序删去所有边,树变为下图。按数字顺序得到的结点编号排列为①③④②⑤,该 排列是所有可能的结果中字典序最小的。 1 【输入格式】 从文件tre.i中读入数据。 本题输入包含多组测试数据 第一行一个正整数T,表示数据组数。 对于每组测试数据 第一行一个整数n,表示树的大小。 第二行n个整数,第i(1≤i≤n)个整数表示数字i初始时所在的结点编号。 接下来n-1行每行两个整数x,y,表示一条连接x号结点与y号结点的边 第8页共10页 2019年CCF非专业级软件能力认证第二轮提高级 day1树上的数(tree) 【输出格式】 输出到文件tree.out中 对于每组测试数据,输出一行共n个用空格隔开的整数,表示最优操作方案下所 能得到的字典序最小的P2 【样例1输入】 21354 13 14 24 45 34215 12 23 34 45 5 12534 13 14 15 18 12345789196 12 14 15 67 78 919 第9页共10页 2019年CCF非专业级软件能力认证第二轮提高级 day1树上的数(tree) 【样例1输出】 13425 13524 23145 23456178916 【样例2】 见选手目录下的 tree/ trees.in与 tree/ trees.ams 数据范围】 测试点编号n≤ 特殊性质 10 无 160 树的形态是一条链 5~7 2000 160 10-12200存在度数为n-1的结点 13~16 160 无 17~202000 对于所有测试点:1≤T<10,保证给出的是一个树。 第10页共10页

...展开详情
立即下载 最低0.43元/次 身份认证VIP会员低至7折
举报 举报 收藏 收藏
分享
427KB
2019 CSP-J 第一轮 答案解析.pdf

2019 CSP-J 第一轮 答案解析

2019-10-19 立即下载
3.09MB
2019CSP-S A卷初赛真题及答案.docx

2019CSP-S A卷初赛真题及答案2019CSP-S A卷初赛真题及答案2019CSP-S A卷初赛真题及答案

2019-10-20 立即下载
2.63MB
2019CSP-S提高组C++试题A卷.pdf

2019CSP-S提高组C++试题A卷

2019-10-19 立即下载
3.27MB
CSP-J、CSP-S初赛知识点1_计算机结构与组成原理(2019-10-10).pdf

CSP-J、CSP-S初赛知识点2_线性表、查找算法、排序算法

2019-10-20 立即下载
751KB
CSP-J、CSP-S学习进阶-2019-10-20.pdf

CSP-J、CSP-S学习进阶-2019-10-20 CSP-J、CSP-S学习进阶-2019-10-20

2019-10-20 立即下载
327KB
浙江j组(2019CSP-J初赛).xlsx

浙江j组(2019CSP-J初赛) 浙江j组(2019CSP-J初赛) 浙江j组(2019CSP-J初赛)

2019-10-26 立即下载
125KB
2019CCF CSP-S第一轮答案 解析.pdf

2019CCF CSP-S第一轮答案 解析

2019-10-19 立即下载
3.09MB
CSP-J、CSP-S初赛知识点4_图及其应用(2019-10-17).pdf

CSP-J、CSP-S初赛知识点4_图及其应用(2019-10-17) CSP-J、CSP-S初赛知识点4_图及其应用(2019-10-17)

2019-10-20 立即下载
1.77MB
CSP-J、CSP-S初赛知识点-信息学竞赛中的数学知识_2019_10_15.pdf

CSP-J、CSP-S初赛知识点-信息学竞赛中的数学知识_2019_10_15

2019-10-16 立即下载
3KB
csp认证考试2019.3-2

2019年3月csp考试中的第二道代码题,二十四点。二十四点是一款著名的纸牌游戏,其游戏的目标是使用三个加减乘除运算使得4张纸牌上数字的运算结果为二十四

2019-11-19 立即下载
2.45MB
2019CSP-J A卷初赛真题及答案.docx

CCF CSP-J 2019 入门级 C++ 语言试题及答案 CCF CSP-J 2019 入门级 C++ 语言试题及答案

2019-10-20 立即下载
66KB
湖南长沙CSP-S A类.xlsx

湖南长沙CSP-S A类 湖南长沙CSP-S A类 湖南长沙CSP-S A类

2019-10-26 立即下载
4.44MB
NOIP2019csp-j 初赛普及组 C++试题及答案.rar

NOIP CSP-J/S 全国青少年信息学奥林匹克联赛历年初赛真题

2019-10-28 立即下载
453KB
AE-2M-3001 GC2023 CSP 模组设计指南_release_Rev1.0_20160401.pdf

AE-2M-3001 GC2023 CSP 模组设计指南_release_Rev1.0_20160401.pdf

2019-07-23 立即下载
633KB
附件2:CSP-S提高组成绩公示-北京.pdf

附件2:CSP-S提高组成绩公示-北京 附件2:CSP-S提高组成绩公示-北京

2019-10-26 立即下载
629KB
CSP-J初赛复习资料---NOIP普及组初赛相关资料(2019-10-15).pdf

CSP-J初赛复习资料---NOIP普及组初赛相关资料(2019-10-15)

2019-10-15 立即下载
19KB
2019 CSP-J答案及解析

CSP-J/S是由CCF主办的计算机非专业级别的软件能力认证。认证包括CSP-J(Junior,入门级)和CSP-S(Senior,提高级)两个级别,认证内容均包括算法设计能力和编程能力。

2020-02-08 立即下载
420KB
1543:【例 3】与众不同-2019.12.09.pdf

1543:【例 3】与众不同-2019.12.09

2019-12-10 立即下载
259KB
CCF关于CSP-JS2019第二轮认证证书发放的公告.pdf

CCF关于CSP-JS2019第二轮认证证书发放的公告

2019-12-16 立即下载
2.16MB
HPE6-A45 ACSP 题库2019.pdf

HPE6-A45 ACSP 题库2019

2020-04-21 立即下载
img
chenndao

关注 私信 TA的资源

上传资源赚积分,得勋章
相关内容推荐