NOIP2017提高组复赛试题.docx

《NOIP2017提高组复赛试题.docx》由会员分享，可在线阅读，更多相关《NOIP2017提高组复赛试题.docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、NOIP2017提高组复赛试题CCF全国信息学奥林匹克联赛NOIP2017复赛提高组day1请选手务必仔细浏览本页内容注意事项：1、文件名程序名和输入输出文件名必须使用英文小写。2、C/C+中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。3、全国统一评测时采用的机器配置为：CPUAMDAthlon(tm)IIx2240processor，2.8GHz，内存4G，上述时限以此配置为准。4、只提供Linux格式附加样例文件。5、提交的程序代码文件的放置位置请参照各省的详细要求。6、十分提醒：评测在当前最新公布的NOILinux下进行，各语言的编译器版本以其为准。1小凯的

2、疑惑(math.cpp/c/pas)【问题描绘】小凯手中有两种面值的金币，两种面值均为正整数且相互互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。如今小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在小凯无法准确支付的商品。【输入格式】输入文件名为math.in。输入数据仅一行，包含两个正整数a和b，它们之间用一个空格隔开，表示小凯手中金币的面值。【输出格式】输出文件名为math.out。输出文件仅一行，一个正整数N，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。math/math1.inmath/m

3、ath1.ans【输入输出样例1讲明】小凯手中有面值为3和7的金币无数个，在不找零的前提下无法准确支付价值为1、2、4、5、8、11的物品，其中最贵的物品价值为11，比11贵的物品都能买到，比方：12=3*4+7*013=3*2+7*114=3*0+7*215=3*5+7*0【输入输出样例2】见选手目录下的math/math2.in和math/math2.ans。【数据规模与约定】对于30%的数据：1a，b50。对于60%的数据：1a，b10,000。对于100%的数据：1a，b1,000,000,000。2时间复杂度(complexity.cpp/c/pas)【问题描绘】小明正在学习一种新的

4、编程语言A+，刚学会循环语句的他冲动地写了好多程序并给出了他本人算出的时间复杂度，可他的编程教师实在不想一个一个检查小明的程序，于是你的时机来啦！下面请你编写程序来判定小明对他的每个程序给出的时间复杂度能否正确。A+语言的循环构造如下：其中“Fixy表示新建变量i变量i不可与未被销毁的变量重名并初始化为x，然后判定i和y的大小关系，若i小于等于y则进入循环，否则不进入。每次循环结束后i都会被修改成i+1，一旦i大于y终止循环。x和y能够是正整数x和y的大小关系不定或变量n。n是一个表示数据规模的变量，在时间复杂度计算中需保留该变量而不能将其视为常数，该数远大于100。“E表示循环体结束。循环体

5、结束时，这个循环体新建的变量也被销毁。注：此题中为了书写方便，在描绘复杂度时，使用大写英文字母“O表示通常意义下“的概念。【输入格式】输入文件名为complexity.in。输入文件第一行一个正整数t，表示有tt10个程序需要计算时间复杂度。每个程序我们只需抽取其中“Fixy和“E即可计算时间复杂度。注意：循环构造允许嵌套。接下来每个程序的第一行包含一个正整数L和一个字符串，L代表程序行数，字符串表示这个程序的复杂度，“O(1)表示常数复杂度，“O(nw)表示复杂度为nw，其中w是一个小于100的正整数输入中不包含引号，输入保证复杂度只要O(1)和O(nw)两种类型。接下来L行代表程序中循环构

6、造中的“Fixy或者“E。程序行若以“F开始，表示进入一个循环，之后有空格分离的三个字符串ixy，其中i是一个小写字母保证不为“n，表示新建的变量名，x和y可能是正整数或n，已知若为正整数则一定小于100。程序行若以“E开始，则表示循环体结束。【输出格式】输出文件名为complexity.out。输出文件共t行，对应输入的t个程序，每行输出“Yes或“No或者“ERR输出中不包含引号，若程序实际复杂度与输入给出的复杂度一致则输出“Yes，不一致则输出“No，若程序有语法错误其中语法错误只要:F和E不匹配新建的变量与已经存在但未被销毁的变量重复两种情况，则输出“ERR。注意：即便在程序不会执行的

7、循环体中出现了语法错误也会编译错误，要输出“ERR。complexity/complexity1.in和complexity/complexity1.ans。【输入输出样例1讲明】第一个程序i从1到1是常数复杂度。第二个程序x从1到n是n的一次方的复杂度。第三个程序有一个F开启循环却没有E结束，语法错误。第四个程序二重循环，n的平方的复杂度。第五个程序两个一重循环，n的一次方的复杂度。第六个程序第一重循环正常，但第二重循环开场即终止由于n远大于100，100大于4。第七个程序第一重循环无法进入，故为常数复杂度。第八个程序第二重循环中的变量x与第一重循环中的变量重复，出现语法错误，输出ERR。【

8、输入输出样例2】见选手目录下的complexity/complexity2.in和complexity/complexity2.ans。【数据规模与约定】对于30%的数据：不存在语法错误，数据保证小明给出的每个程序的前L/2行一定为以F开始的语句，第L/2+1行至第L行一定为以E开始的语句，L见选手目录下的park/park1.in和park/park1.ans。对于第一组数据，最短路为3。15,1245,1235为3条合法途径。全国信息学奥林匹克联赛NOIP2017复赛提高组day1对于100%的数据,1P109,1ai,biN,0ci1000。数据保证：至少存在一条合法的道路。Karoo7152017-11-111608该文档是极速PDF编辑器生成，假如想去掉该提示,请访问并下载：:/doczj/doc/e3ee942edcccda38376baf1ffc4ffe473268fd4d.html/