CSP-S2019第二轮认证(原NOIP提高组复赛)试题

2019年CCF非专业级软件能力认证第二轮提高级时间：2019年11月16日08:30～12:00题目名称格雷码括号树树上的数题目类型传统型传统型传统型目录可执行文件名输入文件名brackets.in输出文件名每个测试点时限1.0秒1.0秒2.0秒内存限制子任务数目测试点是否等分是是是提交源程序文件名code.c对于Pascal语言编译选项对于C语言对于Pascal语言1.文件名(程序名和输入输出文件名)必须使用英文小写。2.C/C++中函数main()的返回值类型必须是int,程序正常结束时的返回值必须3.提交的程序代码文件的放置位置请参照各省的具体要求。4.因违反以上三点而出现的错误或问题，申诉时一律不予受理。5.若无特殊说明，结果的比较方式为全文比较(过滤行末空格及文末回车)。2019年CCF非专业级软件能力认证第二轮提高级6.程序可使用的栈内存空间限制与题目的内存限制一致。7.全国统一评测时采用的机器配置为：Intcl(R)Corc(TM)i7-8700KCPU@3.70GHz,内存32GB。上述时限以此配置为准。9.评测在当前最新公布的NOILinux下进行，各语言的编译器版本以其为准。10.最终评测时所用的编译命a。【题目描述】通常，人们习惯将所有n位二进制串按照字典序排列，例如所有2位二进制串按字典序从小到大排列为：00,01,10,11。格雷码(GrayCodc)是一种特殊的n位二进制串排列法，它要求相邻的两个二进所有2位二进制串按格雷码排列的一个例子为：00,01,11,10。n位格雷码不止一种，下面给出其中一种格雷码的生成算法：1.1位格雷码由两个1位二进制串组成，顺序为：0,1。2.n+1位格雷码的前2”个二进制串，可以由依此算法生成的n位格雷码(总共2”个n位二进制串)按顺序排列，再在每个串前加一个前缀0构成。3.n+1位格雷码的后2”个二进制串，可以由依此算法生成的n位格雷码(总共2”个n位二进制串)按逆序排列，再在每个串前加一个前缀1构成。综上，n+1位格雷码，由n位格雷码的2"个二进制串按顺序排列再加前缀0,和按逆序排列再加前缀1构成，共2n+1个二进制串。另外，对于n位格雷码中的2"个二进制串，我们按上述算法得到的排列顺序将它们从0～2"-1编号。按该算法，2位格雷码可以这样推出：1.已知1位格雷码为0,1。2.前两个格雷码为00,01。后两个格雷码为11,10。合并得到00,01,11,10,编号依次为0～3。同理，3位格雷码可以这样推出：1.已知2位格雷码为：00,01,11,10。2.前四个格雷码为：000,001,011,010。后四个格雷码为：110,111,101,100。合并得到：000,001,011,010,110,111,101,100,编号依次为0～7。现在给出n,k,请你求出按上述算法生成的n位格雷码中的k号二进制串。【输入格式】仅一行两个整数n,k,意义见题目描述。【输出格式】输出到文件code.out中。仅一行一个n位二进制串表示答案。【样例1输入】【样例1输出】【样例1解释】2位格雷码为：00,01,11,10,编号从0～3,因此3号串是10。【样例2输入】【样例2输出】【样例2解释】3位格雷码为：000,001,011,010,110,111,101,100,编号从0～7,因此5号串是111。【样例3】对于80%的数据：k≤5×10⁶对于95%的数据：k≤263-1对于100%的数据：1≤n≤64,0≤k<2"【题目背景】1.()是合法括号串。2.如果A是合法括号串，则(A)是合法括号串。3.如果A,B是合法括号串，则AB是合法括号串。1.字符串S的子串是S中连续的任意个字符组成的字符串。S的子串可用起始位置1与终止位置r来表示，记为S(l,r)(1≤l≤r≤|S|,|S|表示S的长度)。2.S的两个子串视作不同当且仅当它们在S中的位置不同，即1不同或r不同。【题目描述】一个大小为n的树包含n个结点和n-1条边，每条边连接两个结点，且任意两个小Q是一个充满好奇心的小朋友，有一天他在上学的路上碰见了一个大小为n的树，树上结点从1～n编号，1号结点为树的根。除1号结点外，每个结点有一个父亲根结点到i号结点的简单路径上的括号，按结点经过顺序依次排列组成的字符串。这个问题难倒了小Q,他只好向你求助。设s;共有k;个不同子串是合法括号串，你只需要告诉小Q所有i×k;的异或和，即：【输入格式】第一行一个整数n,表示树的大小。第三行包含n-1个整数，第i(1≤i<n)个整数表示i+1号结点的父亲编号fi+1。2019年CCF非专业级软件能力认证第二轮提高级1括y(brackets)【输出格式】【样例1输入】5【样例1输出】6【样例1解释】将根到1号结点的简单路径上的括号，按经过顺序排列所组成的字符串为(,子串是合法括号串的个数为0。将根到2号结点的简单路径上的括号，按经过顺序排列所组成的字符串为((,子串是合法括号串的个数为0。将根到3号结点的简单路径上的括号，按经过顺序排列所组成的字符串为(),子串是合法括号串的个数为1。将根到4号结点的简单路径上的括号，按经过顺序排列所组成的字符串为(((,子串是合法括号串的个数为0。将根到5号结点的简单路径上的括号，按经过顺序排列所组成的字符串为((),子串是合法括号串的个数为1。【样例2】见选手目录下的brackets/brackets2.in与brackets/brackets2.ans。【样例3】见选手目录下的brackets/brackets3.in与brackets/brackets3.ans。【数据范围】测试点编号特殊性质8无无树上的数(tree)【题目描述】给定一个大小为n的树，它共有n个结点与n-1条边，结点从1～n编号。初始时每个结点上都有一个1～n的数字，且每个1～n的数字都只在恰好一个结点上出现。接下来你需要进行恰好n-1次删边操作，每次操作你需要选一条未被删去的边，此时这条边所连接的两个结点上的数字将会交换，然后这条边将被删去。n-1次操作过后，所有的边都将被删去。此时，按数字从小到大的顺序，将数字1～n所在的结点编号依次排列，就得到一个结点编号的排列P;。现在请你求出，在最的顺序删去所有边，树变为下图。按数字顺序得到的结点编号排列为①③④②⑥,该【输入格式】第一行一个正整数T,表示数据组数。第二行n个整数，第i(1≤i≤n)个整数表示数字i初始时所在的结点编号。接下来n-1行每行两个整数x,y,表示一条连接x号结点与y号结点的边。2019年CCF【输出格式】对于每组测试数据，输出一行共n个用空格隔开的整数，表示最优操作方案下所【样例1输入】45552019年【样例1输出】【样例2】【数据范围】测试点编号特殊性质无树的形态是一条链存在度数为n-1的结点无对于所有测试点：1≤T≤10,保证给出的是一个树。2019年CCF非专业级软件能力认证第二轮提高级时间：2019年11月17日08:30～12:00题目名称Emiya家今天的饭划分树的重心题目类型传统型传统型传统型目录可执行文件名输入文件名meal.inpartition.in输出文件名meal.out每个测试点时限1.0秒2.0秒3.0秒内存限制子任务数目测试点是否等分是是是提交源程序文件名meal.c对于Pascal语言编译选项对于C语言对于Pascal语言1.文件名(程序名和输入输出文件名)必须使用英文小写。2.C/C++中函数main()的返回值类型必须是int,程序正常结束时的返回值必须3.提交的程序代码文件的放置位置请参照各省的具体要求。4.因违反以上三点而出现的错误或问题，申诉时一律不予受理。5.若无特殊说明，结果的比较方式为全文比较(过滤行末空格及文末回车)。2019年CCF非专业级软件能力认证第二轮提高级6.程序可使用的栈内存空间限制与题目的内存限制一致。7.全国统一评测时采用的机器配置为：Intcl(R)Corc(TM)i7-8700KCPU@3.70GHz,内存32GB。上述时限以此配置为准。9.评测在当前最新公布的NOILinux下进行，各语言的编译器版本以其为准。10.最终评测时所用的编译命令中不含任何优化开关。Emiya家今天的饭(meal)【题目描述】Emiya是个擅长做菜的高中生，他共掌握n种烹饪方法，且会使用m种主要食材做菜。为了方便叙述，我们对烹饪方法从1～n编号，对主要食材从1～m编号。Emiya做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地，Emiya会做a,;道不同的使用烹饪方法i和主要食材j的菜(1≤i≤n,1≤j≤m),这也意味着Emiya总共会做道不同的菜。Emiya今天要准备一桌饭招待Yazid和Rin这对好朋友，然而三个人对菜的搭配有不同的要求，更具体地，对于一种包含k道菜的搭配方案而言：●Eniya不会让大家饿肚子，所以将做●Rin希望品尝不同烹饪方法做出的菜，因此她要求每道菜的烹饪方法互不相同●Yazid不希望品尝太多同一食材做出的菜，因此他要求每种主要食材至多在一半的菜(即L道菜)中被使用-这里的Lx」为下取整函数，表示不超过x的最大整数这些要求难不倒Emiya,但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同，当且仅当存在至少一道菜在一种方案中出现，而不在另一种方案中出现。Emiya找到了你，请你帮他计算，你只需要告诉他符合所有要求的搭配方案数对质数998,244,353取模的结果。【输入格式】第1行两个用单个空格隔开的整数n,m。第2行至第n+1行，每行m个用单个空格隔开的整数，其中第i+1行的m个【输出格式】输出到文件meal.out中。仅一行一个整数，表示所求方案数对998,244,353取模的结果。【样例1输入】【样例1输出】3【样例1解释】由于在这个样例中，对于每组i,j,Emiya都最多只会做一道菜，因此我们直接通过给出烹饪方法、主要食材的编号来描述一道菜。符合要求的方案包括：●做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材2的菜●做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材3的菜●做一道用烹饪方法1、主要食材3的菜和一道用烹饪方法2、主要食材2的菜因此输出结果为3mod998,244,353=3。需要注意的是，所有只包含一道菜的方案都是不符合要求的，因为唯一的主要食材在超过一半的菜中出现，这不满足Yazid的要求。【样例2输入】【样例2输出】【样例2解释】Emiya必须至少做2道菜。做2道菜的符合要求的方案数为100。做3道菜的符合要求的方案数为90。因此符合要求的方案数为100+90=190。【样例3输入】2019年CCF非专业级软件能力认证第二轮提高级day2Emiya家今天的饭(meal)第5页共11页【样例3输出】【样例4】【样例5】【数据范围】测试点编号n=122223352435263728323对于所有测试点，保证1≤n≤100,1≤m≤2000,O≤ajj<998,244,353。2019年【题目描述】小明对该题设计出了一个暴力程序，对于一组规模为u的数据，该程序的运行时间为u²。然而这个程序运行完一组规模为u的数据之后，它将在任何一组规模小于u的数据上运行错误。样例中的a;不一定递增，但小明又想在不修改程序的情况下正确也就是说，小明需要找到一些分界点1≤k₁<k₂<…<kp<n,注意p可以为0且此时k₀=0,也就是小明可以将所有数据合并在一起运行。【输入格式】1.若type=0,则该测试点的a;直接给出。输入文件接下来：第二行n个以空格第二行六个以空格分隔的整数x,y,z,b₁,b₂,m。接下来m行中，第i(1≤i≤m)行包含三个以空格分隔的正整数p,l,r。对于type=1的23～25号测试点，a;的生成方式如下：给定整数x,y,z,b₁,bz,m,以及m个三元组(pr,l,ri)。保证n≥2。若n>2,则V3≤i保证1≤P₁≤n,Pm=n。令po=0,则p;还满足VO≤i<m有p₁<p₁+1。对于所有1≤j≤m,若下标值i(1≤i≤n)满足Pj-1<i≤Pj,则有【样例1输入】【样例1输出】【样例1解释】答案为(5+1)²+7²+9²+9²=247。方案，因为5>1。【样例2输入】【样例2输出】【样例2解释】2019年CCF非专业级软件能力认证第二轮提高级2划yd(partition)【样例3输入】【样例3输出】【样例4】【样例5】见选手目录下的partition/partition5.in【数据范围】测试点编号01所有测试点满足：type∈{0,1},2≤n≤4×10⁷,1≤a;≤10°,1≤m≤10⁵树的重心(centroid)【题目描述】小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：1.一个大小为n的树由n个结点与n-1条无向边构成，且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个子树；而在树中删去一条边(保留关联结点，下同),树将分裂为恰好两个子树。2.对于一个大小为n的树与任意一个树中结点c,称c是该树的重心当且仅当在树是下取整函数)。对于包含至少一个结点的树，它的重心只可能有1或2个。课后老师给出了一个大小为n的树S,树中结点从1～n编号。小简单的课后作业是求出S单独删去每条边后，分裂出的两个子树的重心编号和之和。即：上式中，E表示树S的边集，(u,v)表示一条连接u号点和v号点的边。S?与S?分别表示树S删去边(u,v)后，u号点与v号点所在的被分裂出的子树。小简单觉得作业并不简单，只好向你求助，请你教教他。【输入格式】本题输入包含多组测试数据。第一行一个整数T表示数据组数。接下来依次给出每组输入数据，对于每组数据：第一行一个整数n表示树S的大小。接下来n-1行，每行两个