初赛、复赛试题csp-js2019第二轮认证

2019CCFCSP-时间：2019111708:30∼题目Emiya家今天划树的题目传统可执行文输入文输出文每个测试1.02.03.0内存2561256子任务测试点是是是是提交源程对于 语对于 语Pascal编译选对于 语-对于 语-Pascal文件名（程序名和输入输出文件名）C/C++main()int，程序正常结束时的返回值必须是0。提交的程序代码文件的放置位置请参照的具体要求因以上三点而出现的错误或问题，申诉时一律不予受理若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车PAGEPAGE2NUMPAGES122019年CCF非专业级软件能力认证第二轮提高 统一评测时采用的机器配置为：In (R)Core(TM)i7-8700KCPU3.70GHz，内存32GB。上述时限以此配置为准。只提供Linux评测在当前公布的NOILinux下进行，各语言的编译器版本以其为准 是求和运算符 ai的值等于a1+a2+···+an20192019CCFPAGEPAGE3NUMPAGES12Emiya家今天的饭Emiyan种....m种....做菜。为了方便叙述，我们对烹饪方法从1∼n1∼m编号。Emiya做的每道菜都将使用....烹饪方法与....Emiyaai,jij的菜（1in，1≤jm）也意味着Emiya总共会做 m i=1Emiya今天要准备一桌饭招待Yazid和Rin这对好朋友，然而三个人对有不同的要求，更具体地，对于一种包含 道菜的搭配方案而言Emiya不会让大家饿肚子，所以将做.....k≥Rin希望品尝不同烹饪方法做出的菜，因此她要求每道菜的.......Yazid不希望品尝太多同一食材做出的菜，因此他要求每种至多在.的菜（即⌊k⌋道菜）中被使用2–⌊x⌋x这些要求难不倒Emiya，但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同，当且仅当存在至少一道菜在案中出现，而不在另案中出现。Emiya找到了你，请你帮他计算，你只需要符合所有要求的搭配方案数对质998244353从文件meal.in中读入数1行两个用单个空格隔开的整数n,m2n+1mi+1m个数依次为ai,1,ai,2,...,ai,m。输出到文件meal.out998244353121001131ij，Emiya都最多只会做一道菜，因此我们直接通符合要求的方案包做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材2做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材31322的菜因此输出结果为3mod998,244,353=3。超过一半的菜中出现，这不满Yazid的要求。2312456022Emiya22100。390因此符合要求的方案数为100+90 【样 输入010111111010011034见选 下的meal/meal4.in与meal/meal4.ans5见选 下的meal/meal5.in与meal/meal5.ans测试点nmai,j122223352435263728323998,244,1≤n≤100，1≤m≤2000，0≤ai,j<99824435320192019CCFday2划分PAGEPAGE6NUMPAGES12划分2048年，第三十届CSP认证的考场上，作为选手的打开了第一题。这个题的n1∼n编号，iai。对该题设计出了一 程序，对于一组规模为u的数据，该程序的...u2u的数据之后，它将在任何一组规模..的数据上运行错误。样例中的 不一定递增，但又想在不修改程序的情况下正运行样例，于是决定使用一种非常原始的解决方案：将所有数据划分成若干个数据段，段内数据编号..，接着将同一段内的数据合并成新数据，其规模等于段内原数据的.... 将让新数据的规模能够递增也就是说，需要找到一些分界点1≤k1<k2<···<kp<n，使

ai

ai≤··· 注意p可以为0且此时k0=0，也就是可以将所有数据合并在一起运行。希望他的程序在正确运行样例情况下，运行时间也能尽量小，也就是 (

ai)2+

ai)2+···+

nai，请你求出最优划分方案下，的程序的最小运行时间。从文件partition.in中读入数据................ ai.......第一行两个整数n,type。n的意义见题目描述，type表示输入方type=0ai....n个以空格分隔的整数ai，表示每组数据的规模。type=1ai将....，生成方式见后文。输入文件接下来：xyzb1b2mmi（1im）行包含三个以空格分隔的正整数pi,li,ri。type=12325号测试点，ai的生成方式如下：给定整数x,y,z,b1,b2,m，以及m个三元组(pi,li,ri)。n2n2∀3in，bi=(xbi−1ybi−2z)mod2300p+1PAGEPAGE7NUMPAGES1220192019CCFday2划分PAGEPAGE8NUMPAGES121≤j≤mi（1≤i≤n）pj−1<i≤pj ai= mod(rj−lj+1)+l................................输出到文件partition.out中。输出一行一个整数，表示答案。15517911最优的划分方{5,1},{7},{9},{9}。由51≤7≤9≤9知该方案合法(51)2729292247虽然划分方案{5},{1},{7},{9},{9}对应的运247小，但它不是一组合法方案，因为5>1。{5},{1,7},{9},{9}251247210567746【样 输出【样 解释最优的划分方案 {5},{6},{7},{7},{4,6,2},{13},{19,9}3112345678912345678934见选 下的 与partition/partition4.ans5见选 下的 与partition/partition5.ans测试点编naitype1∼04∼7∼10~5×23∼4×1所有测试点满足：type∈{01},2≤n≤4107,1≤ai≤109,1≤m≤1051liri109,0xyzb1b223020192019CCFday2树的重心PAGEPAGE10NUMPAGES12树的重心小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：nnn1条无向边构成，且满足任意两个结点间....一条简单路径。在树中删去一个结点及与它关联的边，树将为若干个子树；而在树中删去一条边（保留关联结点，下同，树将为..两个子树。ncc是该树的.2c及与它关联的边后，出的所有子树的大小均...n⌋（2是下取整函数。对于包含至少一个结点的树，它的重心只可能有1或2个。nS1n是求出 单独删去每条边后，出的两个子树的重心编号和之和。即 x 且x号点是S′的重 uuv上式中，ES的边集，(uv)uv号点的边。S′与Suv分别表示树S删去边(u,v)后，u号点与v号点所在的被出的子树。从文件centroid.in中读入数据。............T第一行一个整数n表示树S的大小。n−1uivi(uivi)输出到文件centroid.out后，出的两个子树的重心编号和之和。12512232435712【样 输出1对于第一删去边(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。2见选 下的centroid/centroid2.in与centroid/centroid2.ans3 下的centroid/centroid3.in与centroid/centroid3.ans。该数据满足特殊性质A，具体信息见数据范围中的描述。4 下的centroid/centroid4.in与centroid/centroid