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

2019年CCF非专业级软件能力认证第二轮提高级2019CCFCSP-S2day1时间：2019年11月16日08:3012:00题目名称格雷码括号树树上的数题目类型传统型传统型传统型目录codebracketstree可执行文件名codebracketstree输入文件名code.inbrackets.intree.in输出文件名code.outbrackets.outtree.out每个测试点时限1.0秒1.0秒2.0秒内存限制256MiB256MiB256MiB子任务数目202020测试点是否等分是是是提交源程序文件名对于C++语言code.cppbrackets.cpptree.cpp对于C语言code.cbrackets.ctree.c对于Pascal语言code.pasbrackets.pastree.pas编译选项对于C++语言-lm对于C语言-lm对于Pascal语言注意事项与提醒（请选手务必仔细阅读）1.文件名（程序名和输入输出文件名）必须使用英文小写。2.C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。3.提交的程序代码文件的放置位置请参照各省的具体要求。4.因违反以上三点而出现的错误或问题，申诉时一律不予受理。5.若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。2019年CCF非专业级软件能力认证第二轮提高级day16.程序可使用的栈内存空间限制与题目的内存限制一致。7.全国统一评测时采用的机器配置为：Intel(R)Core(TM)i7-8700KCPU@3.70GHz，内存32GB。上述时限以此配置为准。8.只提供Linux格式附加样例文件。9.评测在当前最新公布的NOILinux下进行，各语言的编译器版本以其为准。10.最终评测时所用的编译命令中不含任何优化开关。11.∑是求和运算符，n∑i=1ai的值等于a1+a2+


+an。第2页共10页2019年CCF非专业级软件能力认证第二轮提高级day1格雷码（code）格雷码（code）【题目描述】通常，人们习惯将所有n位二进制串按照字典序排列，例如所有2位二进制串按字典序从小到大排列为：00，01，10，11。格雷码（GrayCode）是一种特殊的n位二进制串排列法，它要求相邻的两个二进制串间.恰.好有一位.不.同，特别地，第一个串与最后一个串也算作相邻。所有2位二进制串按格雷码排列的一个例子为：00，01，11，10。n位格雷码不止一种，下面给出其中一种格雷码的生成算法：1.1位格雷码由两个1位二进制串组成，顺序为：0，1。2.n+1位格雷码的前2n个二进制串，可以由依此算法生成的n位格雷码（总共2n个n位二进制串）按.顺.序排列，再在每个串前加一个前缀0构成。3.n+1位格雷码的后2n个二进制串，可以由依此算法生成的n位格雷码（总共2n个n位二进制串）按.逆.序排列，再在每个串前加一个前缀1构成。综上，n+1位格雷码，由n位格雷码的2n个二进制串按顺序排列再加前缀0，和按逆序排列再加前缀1构成，共2n+1个二进制串。另外，对于n位格雷码中的2n个二进制串，我们按上述算法得到的排列顺序将它们从02n1编号。按该算法，2位格雷码可以这样推出：1.已知1位格雷码为0，1。2.前两个格雷码为00，01。后两个格雷码为11，10。合并得到00，01，11，10，编号依次为03。同理，3位格雷码可以这样推出：1.已知2位格雷码为：00，01，11，10。2.前四个格雷码为：000，001，011，010。后四个格雷码为：110，111，101，100。合并得到：000，001，011，010，110，111，101，100，编号依次为07。现在给出n;k，请你求出按上述算法生成的n位格雷码中的k号二进制串。【输入格式】从文件code.in中读入数据。仅一行两个整数n;k，意义见题目描述。【输出格式】输出到文件code.out中。仅一行一个n位二进制串表示答案。第3页共10页2019年CCF非专业级软件能力认证第二轮提高级day1格雷码（code）【样例1输入】23【样例1输出】10【样例1解释】2位格雷码为：00，01，11，10，编号从03，因此3号串是10。【样例2输入】35【样例2输出】111【样例2解释】3位格雷码为：000，001，011，010，110，111，101，100，编号从07，因此5号串是111。【样例3】见选手目录下的code/code3.in与code/code3.ans。【数据范围】对于50%的数据：n10对于80%的数据：k5106对于95%的数据：k2631对于100%的数据：1n64,0k2n第4页共10页2019年CCF非专业级软件能力认证第二轮提高级day1括号树（brackets）括号树（brackets）【题目背景】本题中.合.法.括.号.串的定义如下：1.()是合法括号串。2.如果A是合法括号串，则(A)是合法括号串。3.如果A，B是合法括号串，则AB是合法括号串。本题中.子.串与.不.同.的.子.串的定义如下：1.字符串S的子串是S中.连.续的任意个字符组成的字符串。S的子串可用起始位置l与终止位置r来表示，记为S(l;r)（1lrjSj，jSj表示S的长度）。2.S的两个子串视作不同.当.且.仅.当它们在S中的位置不同，即l不同或r不同。【题目描述】一个大小为n的树包含n个结点和n1条边，每条边连接两个结点，且任意两个结点间.有.且.仅.有一条简单路径互相可达。小Q是一个充满好奇心的小朋友，有一天他在上学的路上碰见了一个大小为n的树，树上结点从1n编号，1号结点为树的根。除1号结点外，每个结点有一个父亲结点，u（2un）号结点的父亲为fu（1fuu）号结点。小Q发现这个树的每个结点上.恰.有一个括号，可能是’(’或’)’。小Q定义si为：将根结点到i号结点的简单路径上的括号，按结点经过顺序依次排列组成的字符串。显然si是个括号串，但不一定是合法括号串，因此现在小Q想对所有的i（1in）求出，si中有多少个.互.不.相.同.的.子.串是.合.法.括.号.串。这个问题难倒了小Q，他只好向你求助。设si共有ki个不同子串是合法括号串，你只需要告诉小Q所有iki的异或和，即：(1k1)xor(2k2)xor(3k3)xor


xor(nkn)其中xor是位异或运算。【输入格式】从文件brackets.in中读入数据。第一行一个整数n，表示树的大小。第二行一个长为n的由’(’与’)’组成的括号串，第i个括号表示i号结点上的括号。第三行包含n1个整数，第i（1in）个整数表示i+1号结点的父亲编号fi+1。第5页共10页2019年CCF非专业级软件能力认证第二轮提高级day1括号树（brackets）【输出格式】输出到文件brackets.out中。仅一行一个整数表示答案。【样例1输入】5(()()1122【样例1输出】6【样例1解释】树的形态如下图：将根到1号结点的简单路径上的括号，按经过顺序排列所组成的字符串为(，子串是合法括号串的个数为0。将根到2号结点的简单路径上的括号，按经过顺序排列所组成的字符串为((，子串是合法括号串的个数为0。将根到3号结点的简单路径上的括号，按经过顺序排列所组成的字符串为()，子串是合法括号串的个数为1。将根到4号结点的简单路径上的括号，按经过顺序排列所组成的字符串为(((，子串是合法括号串的个数为0。将根到5号结点的简单路径上的括号，按经过顺序排列所组成的字符串为(()，子串是合法括号串的个数为1。【样例2】见选手目录下的brackets/brackets2.in与brackets/brackets2.ans。第6页共10页2019年CCF非专业级软件能力认证第二轮提高级day1括号树（brackets）【样例3】见选手目录下的brackets/brackets3.in与brackets/brackets3.ans。【数据范围】测试点编号n特殊性质128fi=i134200572000810无1114105fi=i11516无17205105第7页共10页2019年CCF非专业级软件能力认证第二轮提高级day1树上的数（tree）树上的数（tree）【题目描述】给定一个大小为n的树，它共有n个结点与n1条边，结点从1n编号。初始时每个结点上都有一个1n的数字，且每个1n的数字都只在.恰.好一个结点上出现。接下来你需要进行.恰.好n1次删边操作，每次操作你需要选一条.未.被.删.去的边，此时这条边所连接的两个结点上的数字将会.交.换，然后这条边将被删去。n1次操作过后，所有的边都将被删去。此时，按数字从小到大的顺序，将数字1n所在的结点编号依次排列，就得到一个结点编号的排列Pi。现在请你求出，在最优操作方案下能得到的.字.典.序.最.小的Pi。如上图，蓝圈中的数字15一开始分别在结点2⃝、1⃝、3⃝、5⃝、4⃝。按照(1)(4)(3)(2)的顺序删去所有边，树变为下图。按数字顺序得到的结点编号排列为1⃝3⃝4⃝2⃝5⃝，该排列是所有可能的结果中字典序最小的。【输入格式】从文件tree.in中读入数据。.本.题.输.入.包.含.多.组.测.试.数.据。第一行一个正整数T，表示数据组数。对于每组测试数据：第一行一个整数n，表示树的大小。第二行n个整数，第i（1in）个整数表示数字i初始时所在的结点编号。接下来n1行每行两个整数x;y，表示一条连接x号结点与y号结点的边。第8页共10页2019年CCF非专业级软件能力认证第二轮提高级day1树上的数（tree）【输出格式】输出到文件tree.out中。对于每组测试数据，输出一行共n个用空格隔开的整数，表示最优操作方案下所能得到的字典序最小的Pi。【样例1输入】452135413142445534215122334455125341213141510123457891061213141556677889910第9页共10页2019年CCF非专业级软件能力认证第二轮提高级day1树上的数（tree）【样例1输出】13425135242314523456178910【样例2】见选手目录下的tree/tree2.in与tree/tree2.ans。【数据范围】测试点编号n特殊性质1210无34160树的形态是一条链57200089160存在度数为n1的结点101220001316160无17202000对于所有测试点：1T10，保证给出的是一个树。第10页共10页2019年CCF非专业级软件能力认证第二轮提高级2019CCFCSP-S2day2时间：2019年11月17日08:3012:00题目名称Emiya家今天的饭划分树的重心题目类型传统型传统型传统型目录mealpartitioncentroid可执行文件名mealpartitioncentroid输入文件名meal.inpartition.incentroid.in输出文件名meal.outpartition.outcentroid.out每个测试点时限1.0秒2.0秒3.0秒内存限制256MiB1GiB256MiB子任务数目252520测试点是否等分是是是提交源程序文件名对于C++语言meal.cpppartition.cppcentroid.cpp对于C语言meal.cpartition.ccentroid.c对于Pascal语言meal.paspartition.pascentroid.pas编译选项对于C++语言-lm对于C语言-lm对于Pascal语言注意事项与提醒（请选手务必仔细阅读）1.文件名（程序名和输入输出文件名）必须使用英文小写。2.C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。3.提交的程序代码文件的放置位置请参照各省的具