年CCF非专业级软件能力认证第二轮提高级
CCFCSP-S2
day1
注意事项与提醒（请选手务必仔细阅读）
1、文件名（程序名和输入输出文件名）必须使用英文小写。2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。3、提交的程序代码文件的放置位置请参照各省的具体要求。4、因违反以上三点而出现的错误或问题，申诉时一律不予受理。5、若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。6、程序可使用的栈内存空间限制与题目的内存限制一致。7、全国统一评测时采用的机器配置为：Intel(R)Core(TM)i7-KCPU
3.70GHz，内存32GB。上述时限以此配置为准。8、只提供Linux格式附加样例文件。9、评测在当前最新公布的NOILinux下进行，各语言的编译器版本以其为准。最终评测时所用的编译命令中不含任何优化开关。∑是求和运算符，∑nai的值等于a1+a2++an。i=1格雷码（code）
通常，人们习惯将所有n位二进制串按照字典序排列，例如所有2位二进制串按字典序从小到大排列为：00，01，10，11。格雷码（GrayCode）是一种特殊的n位二进制串排列法，它要求相邻的两个二进制串间恰.好.有一位不.同.，特别地，第一个串与最后一个串也算作相邻。所有2位二进制串按格雷码排列的一个例子为：00，01，11，10。
位格雷码不止一种，下面给出其中一种格雷码的生成算法：1、位格雷码由两个1位二进制串组成，顺序为：0，1。2、+1位格雷码的前2n个二进制串，可以由依此算法生成的n位格雷码（总共2n个n位二进制串）按顺序排列，再在每个串前加一个前缀0构成。3、+1位格雷码的后2n个二进制串，可以由依此算法生成的n位格雷码（总共2n个n位二进制串）按逆.序.排列，再在每个串前加一个前缀1构成。综上，n+1位格雷码，由n位格雷码的2n个二进制串按顺序排列再加前缀0，和按逆序排列再加前缀1构成，共2n+1个二进制串。另外，对于n位格雷码中的2n个二进制串，我们按上述算法得到的排列顺序将它们从02n1编号。按该算法，2位格雷码可以这样推出：已知1位格雷码为0，1。前两个格雷码为00，01。后两个格雷码为11，10。合并得到00，01，11，10，编号依次为03。同理，3位格雷码可以这样推出：已知2位格雷码为：00，01，11，10。前四个格雷码为：，，，。后四个格雷码为：，，，。合并得到：，，，，，，，，编号依次为07。现在给出n;k，请你求出按上述算法生成的n位格雷码中的k号二进制串。
从文件code.in中读入数据。仅一行两个整数n;k，意义见题目描述。
输出到文件code.out中。仅一行一个n位二进制串表示答案。
位格雷码为：00，01，11，10，编号从03，因此3号串是10。位格雷码为：，，，，，，，，编号从07，因此5号串是。见选手目录下的code/code3.in与code/code3.ans。
对于50%的数据：n10对于80%的数据：k对于95%的数据：k对于%的数据：1n64,0k2n
括号树（brackets）
本题中合法括号串的定义如下：()是合法括号串。如果A是合法括号串，则(A)是合法括号串。如果A，B是合法括号串，则AB是合法括号串。本题中串与不同的子串的定义如下：
字符串S的子串是S中连.续.的任意个字符组成的字符串。S的子串可用起始位置l与终止位置r来表示，记为S(l;r)（1lrjSj，jSj表示S的长度）。
S的两个子串视作不同当且仅当它们在S中的位置不同，即l不同或r不同。
一个大小为n的树包含n个结点和n1条边，每条边连接两个结点，且任意两个结点间有且仅有一条简单路径互相可达。
Q是一个充满好奇心的小朋友，有一天他在上学的路上碰见了一个大小为n的树，树上结点从1n编号，1号结点为树的根。除1号结点外，每个结点有一个父亲结点，u（2un）号结点的父亲为fu（1fuu）号结点。Q发现这个树的每个结点上恰有.一个括号，可能是(或)。小Q定义si为：将根结点到i号结点的简单路径上的括号，按结点经过顺序依次排列组成的字符串。
显然si是个括号串，但不一定是合法括号串，因此现在小Q想对所有的（i1in）求出，si中有多少个互不相同的子串是合法括号串。这个问题难倒了小Q，他只好向你求助。设si共有ki个不同子串是合法括号串，你只需要告诉小Q所有iki的异或和，即：(1k1)xor(2k2)xor(3k3)xorxor(nkn)其中xor是位异或运算。
从文件brackets.in中读入数据。第一行一个整数n，表示树的大小。第二行一个长为n的由(与)组成的括号串，第i个括号表示i号结点上的括号。第三行包含n1个整数，第i（1in）个整数表示i+1号结点的父亲编号fi+1。输出到文件brackets.out中。仅一行一个整数表示答案。5(()()树的形态如下图：
将根到1号结点的简单路径上的括号，按经过顺序排列所组成的字符串为(，子串是合法括号串的个数为0。将根到2号结点的简单路径上的括号，按经过顺序排列所组成的字符串为((，子串是合法括号串的个数为0。将根到3号结点的简单路径上的括号，按经过顺序排列所组成的字符串为()，子串是合法括号串的个数为1。将根到4号结点的简单路径上的括号，按经过顺序排列所组成的字符串为(((，子串是合法括号串的个数为0。将根到5号结点的简单路径上的括号，按经过顺序排列所组成的字符串为(()，子串是合法括号串的个数为1。
见选手目录下的brackets/brackets2.in与brackets/brackets2.ans。见选手目录下的brackets/brackets3.in与brackets/brackets3.ans。
树上的数（tree）
给定一个大小为n的树，它共有n个结点与n1条边，结点从1n编号。初始时每个结点上都有一个1n的数字，且每个1n的数字都只在恰.好.一个结点上出现。接下来你需要进行恰好1次删边操作，每次操作你需要选一条未被删去的边，此时这条边所连接的两个结点上的数字将会交换，然后这条边将被删去。1次操作过后，所有的边都将被删去。此时，按数字从小到大的顺序，将数字1n所在的结点编号依次排列，就得到一个结点编号的排列Pi。现在请你求出，在最优操作方案下能得到的字.典.序.最.小.的Pi。
如上图，蓝圈中的数字15一开始分别在结点2、1、3、5、4。按照(1)(4)(3)(2)的顺序删去所有边，树变为下图。按数字顺序得到的结点编号排列为，该排列是所有可能的结果中字典序最小的。
从文件tree.in中读入数据。本题输入包含多组测试数据。第一行一个正整数T，表示数据组数。对于每组测试数据：第一行一个整数n，表示树的大小。第二行n个整数，第i（1in）个整数表示数字i初始时所在的结点编号。接下来n1行每行两个整数x;y，表示一条连接x号结点与y号结点的边。输出到文件tree.out中。对于每组测试数据，输出一行共n个用空格隔开的整数，表示最优操作方案下所能得到的字典序最小的Pi。
152345789667788993见选手目录下的tree/tree2.in与tree/tree2.ans。
年CCF非专业级软件能力认证第二轮提高级
CCFCSP-S2
day2
注意事项与提醒（请选手务必仔细阅读）
1、文件名（程序名和输入输出文件名）必须使用英文小写。2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。3、提交的程序代码文件的放置位置请参照各省的具体要求。4、因违反以上三点而出现的错误或问题，申诉时一律不予受理。5、若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。6、程序可使用的栈内存空间限制与题目的内存限制一致。7、全国统一评测时采用的机器配置为：Intel(R)Core(TM)i7-KCPU
3.70GHz，内存32GB。上述时限以此配置为准。只提供Linux格式附加样例文件。评测在当前最新公布的NOILinux下进行，各语言的编译器版本以其为准。8、最终评测时所用的编译命令中不含任何优化开关。∑是求和运算符，∑nai的值等于a1+a2++an。i=1
Emiya家今天的饭（meal）
Emiya是个擅长做菜的高中生，他共掌握n种烹.饪.方.法.，且会使用m种主.要.食.材.做菜。为了方便叙述，我们对烹饪方法从1n编号，对主要食材从1m编号。
Emiya今天要准备一桌饭招待Yazid和Rin这对好朋友，然而三个人对菜的搭配有不同的要求，更具体地，对于一种包含k道菜的搭配方案而言：Emiya不会让大家饿肚子，所以将做至少一道菜，即k≥1Rin希望品尝不同烹饪方法做出的菜，因此她要求每道菜的烹饪方法互不相同Yazid不希望品尝太多同一食材做出的菜，因此他要求每种主要食材至多在一半的菜（即k2道菜）中被使用
–这里的x为下取整函数，表示不超过x的最大整数
这些要求难不倒Emiya，但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同，当且仅当存在至少一道菜在一种方案中出现，而不在另一种方案中出现。Emiya找到了你，请你帮他计算，你只需要告诉他符合所有要求的搭配方案数对质数,,取模的结果。
从文件meal.in中读入数据。第1行两个用单个空格隔开的整数n,m。第2行至第n+1行，每行m个用单个空格隔开的整数，其中第i+1行的m个数依次为ai,1,ai,2,...,ai,m。输出到文件meal.out中。仅一行一个整数，表示所求方案数对,,取模的结果。23
3由于在这个样例中，对于每组i,j，Emiya都最多只会做一道菜，因此我们直接通过给出烹饪方法、主要食材的编号来描述一道菜。符合要求的方案包括：做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材2的菜做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材3的菜做一道用烹饪方法1、主要食材3的菜和一道用烹饪方法2、主要食材2的菜因此输出结果为3mod,,=3。需要注意的是，所有只包含一道菜的方案都是不符合要求的，因为唯一的主要食材在超过一半的菜中出现，这不满足Yazid的要求。33123450690Emiya必须至少做2道菜。做2道菜的符合要求的方案数为。做3道菜的符合要求的方案数为90。因此符合要求的方案数为+90=。551742见选手目录下的meal/meal4.in与meal/meal4.ans。见选手目录下的meal/meal5.in与meal/meal5.ans。
划分（partition）
年，第三十届CSP认证的考场上，作为选手的小明打开了第一题。这个题的样例有n组数据，数据从1n编号，i号数据的规模为ai。小明对该题设计出了一个暴力程序，对于一组规模为u的数据，该程序的运行时间为u2。然而这个程序运行完一组规模为u的数据之后，它将在任何一组规模小于u的数据上运行错误。样例中的ai不一定递增，但小明又想在不修改程序的情况下正确运行样例，于是小明决定使用一种非常原始的解决方案：将所有数据划分成若干个数据段，段内数据编号连续，接着将同一段内的数据合并成新数据，其规模等于段内原数据的规模之和小明将让新数据的规模能够递增。也就是说，小明需要找到一些分界点1k1k2kpn，使得
从文件partition.in中读入数据。由于本题的数据范围较大，部分测试点的ai将在程序内生成。第一行两个整数n,type。n的意义见题目描述，type表示输入方式。1.若type=0，则该测试点的ai直接给出。输入文件接下来：第二行n个以空格分隔的整数ai，表示每组数据的规模。2.若type=1，则该测试点的ai将特殊生成，生成方式见后文。输入文件接下来：第二行六个以空格分隔的整数x,y,z,b1,b2,m。接下来m行中，第i（1≤i≤m）行包含三个以空格分隔的正整数pi,li,ri。对于type=1的号测试点，ai的生成方式如下：给定整数x,y,z,b1,b2,m，以及m个三元组(pi,li,ri)。保证n≥2。若n2，则3≤i≤n，bi=(x×bi1+y×bi2+z)mod。保证1≤pi≤n，pm=n。令p0=0，则pi还满足0≤im有pipi+1。对于所有1≤j≤m，若下标值i（1≤i≤n）满足pj1i≤pj，则有
ai=(bimod(rjlj+1))+lj
上述数据生成方式仅是为了减少输入量大小，标准算法不依赖于该生方式.。输出到文件partition.out中。输出一行一个整数，表示答案。最优的划分方案为{5,1},{7},{9},{9}。由5+1≤7≤9≤9知该方案合法。答案为(5+1)2+72+92+92=。虽然划分方案{5},{1},{7},{9},{9}对应的运行时间比小，但它不是一组合法方案，因为51。虽然划分方案{5},{1,7},{9},{9}合法，但该方案对应的运行时间为，比大。567746213最优的划分方案为{5},{6},{7},{7},{4,6,2},{13},{19,9}。123789321234567876543217543219104567891235见选手目录下的partition/partition4.in与partition/partition4.ans。见选手目录下的partition/partition5.in与partition/partition5.ans。
所有测试点满足：type∈{0,1},2≤n≤4×,1≤ai≤,1≤m≤,1≤li≤ri≤,0≤x,y,z,b1,b2。
树的重心（centroid）
小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：1.一个大小为n的树由n个结点与n1条无向边构成，且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个子树；而在树中删去一条边（保留关联结点，下同），树将分裂为恰好两个子树。2.对于一个大小为n的树与任意一个树中结点c，称c是该树的重心当且仅当在树中删去c及与它关联的边后，分裂出的所有子树的大小均不超过n2（其中x是下取整函数）。对于包含至少一个结点的树，它的重心只可能有1或2个。课后老师给出了一个大小为n的树S，树中结点从1n编号。小简单的课后作业是求出S单独删去每条边后，分裂出的两个子树的重心编号和之和。即：
从文件centroid.in中读入数据。本题输入包含多组测试数据。第一行一个整数T表示数据组数。接下来依次给出每组输入数据，对于每组数据：第一行一个整数n表示树S的大小。接下来n1行，每行两个以空格分隔的整数ui,vi，表示树中的一条边(ui,vi)。输出到文件centroid.out中。共T行，每行一个整数，第i行的整数表示：第i组数据给出的树单独删去每条边后，分裂出的两个子树的重心编号和之和。223243571213146673对于第一组数据：删去边(1,2)，1号点所在子树重心编号为{1}，2号点所在子树重心编号为{2,3}。删去边(2,3)，2号点所在子树重心编号为{2}，3号点所在子树重心编号为{3,5}。删去边(2,4)，2号点所在子树重心编号为{2,3}，4号点所在子树重心编号为{4}。删去边(3,5)，3号点所在子树重心编号为{2}，5号点所在子树重心编号为{5}。因此答案为1+2+3+2+3+5+2+3+4+2+5=32。见选手目录下的centroid/centroid2.in与centroid/centroid2.ans。见选手目录下的centroid/centroid3.in与centroid/centroid3.ans。该数据满足特殊性质A，具体信息见数据范围中的描述。见选手目录下的centroid/centroid4.in与centroid/centroid4.ans。该数据满足特殊性质B，具体信息见数据范围中的描述。
表中特殊性质一栏，两个变量的含义为存在一个1n的排列pi（1≤i≤n），使得：A：树的形态是一条链。即1≤in，存在一条边(pi,pi+1)。B：树的形态是一个完美二叉树。即1≤i≤n12，存在两条边(pi,p2i)与(pi,p2i+1)。对于所有测试点：1≤T≤5,1≤ui,vi≤n。保证给出的图是一个树。
百度搜索（西安信奥赛集训营）
了解信奥赛历年真题、了解各高校加分政策、了解比赛时间、了解陕西学员获奖名单