noip2017提高組試題(day1+day2)-word版

1、全國(guó)信息學(xué)奧林匹克聯(lián)賽（NOIP2017）復(fù)賽 提高組 day1 第 1 頁共 7 頁 CCF 全國(guó)信息學(xué)奧林匹克聯(lián)賽（NOIP2017）復(fù)賽 提高組 day1 （請(qǐng)選手務(wù)必仔細(xì)閱讀本頁內(nèi)容） 一．題目概況 一．題目概況 中文題目名稱 小凱的疑惑 時(shí)間復(fù)雜度 逛公園 英文題目與子目錄名 math complexity park 可執(zhí)行文件名 math complexity park 輸入文件名 math.in c

2、omplexity.in park.in 輸出文件名 math.out complexity.out park.out 每個(gè)測(cè)試點(diǎn)時(shí)限 1 秒 1 秒 3 秒 測(cè)試點(diǎn)數(shù)目 20 10 10 每個(gè)測(cè)試點(diǎn)分值 5 10 10 附加樣例文件 有 有 有 結(jié)果比較方式 全文比較（過濾行末空格及文末回車） 題目類型 傳統(tǒng) 傳統(tǒng) 傳統(tǒng) 運(yùn)行內(nèi)存上限 256M 256M 512M 二．提交源程序文件名 二

3、．提交源程序文件名 對(duì)于 C++語言 math.cpp complexity.cpp park.cpp 對(duì)于 C 語言 math.c complexity.c park.c 對(duì)于 pascal 語言 math.pas complexity.pas park.pas 三．編譯命令（不包含任何優(yōu)化開關(guān)） 三．編譯命令（不包含任何優(yōu)化開關(guān)） 對(duì)于 C++語言 g++ -o math math.cpp -lm g++ -o

4、complexity complexity.cpp -lm g++ -o park park.cpp -lm 對(duì)于 C 語言 gcc -o math math.c -lm gcc -o complexity complexity.c -lm gcc -o park park.c -lm 對(duì)于 pascal 語言 fpc math.pas fpc complexity.pas fpc park.pas 注意事項(xiàng)： 注意事項(xiàng)： 1、

5、文件名（程序名和輸入輸出文件名）必須使用英文小寫。 2、C/C++中函數(shù) main()的返回值類型必須是 int，程序正常結(jié)束時(shí)的返回值必須是 0。 3、全國(guó)統(tǒng)一評(píng)測(cè)時(shí)采用的機(jī)器配置為：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz， 內(nèi)存 4G，上述時(shí)限以此配置為準(zhǔn)。 4、只提供 Linux 格式附加樣例文件。 5、提交的程序代碼文件的放置位置請(qǐng)參照各省的具體要求。 6、特別提醒：評(píng)測(cè)在當(dāng)前

6、最新公布的 、特別提醒：評(píng)測(cè)在當(dāng)前最新公布的 NOI Linux 下進(jìn)行，各語言的編譯器版本以其為準(zhǔn)。 下進(jìn)行，各語言的編譯器版本以其為準(zhǔn)。 全國(guó)信息學(xué)奧林匹克聯(lián)賽（NOIP2017）復(fù)賽 提高組 day1 第 3 頁共 7 頁 【問題描述】 2．時(shí)間復(fù)雜度 ．時(shí)間復(fù)雜度 (complexity.cpp/c/pas) 小明正在學(xué)習(xí)一種新的編程語言 A++，剛學(xué)會(huì)循環(huán)語句的他激動(dòng)地寫了好多程序并給出了他自己算出的時(shí)間復(fù)雜度，可他的編程老

7、師實(shí)在不想一個(gè)一個(gè)檢查小明的程序， 于是你的機(jī)會(huì)來啦！下面請(qǐng)你編寫程序來判斷小明對(duì)他的每個(gè)程序給出的時(shí)間復(fù)雜度是否正確。 A++語言的循環(huán)結(jié)構(gòu)如下： 其 中 “F i x y” 表示新建變量 （ i 變量 i 不可與未被銷毀的變量重名） 并初始化為 x， 然后判斷 i 和 y 的大小關(guān)系，若 i 小于等于 y 則進(jìn)入循環(huán)，否則不進(jìn)入。每次循環(huán)結(jié)束后 i 都會(huì)被修改成 i +1，一旦 i 大于 y 終止循環(huán)。 x 和 y 可以是正整

8、數(shù)（x 和 y 的大小關(guān)系不定）或變量 n。n 是一個(gè)表示數(shù)據(jù)規(guī)模的變量，在時(shí)間復(fù)雜度計(jì)算中需保留該變量而不能將其視為常數(shù)，該數(shù)遠(yuǎn)大于 遠(yuǎn)大于 100。 “E”表示循環(huán)體結(jié)束。循環(huán)體結(jié)束時(shí)，這個(gè)循環(huán)體新建的變量也被銷毀。 注：本題中為了書寫方便，在描述復(fù)雜度時(shí)，使用大寫英文字母“O”表示通常意義下“Θ”的概念。 【輸入格式】 輸入文件名為 complexity.in。 輸入文件第一行一個(gè)正整數(shù) t，表示有 t（t ≤ 10）個(gè)程序需要計(jì)

9、算時(shí)間復(fù)雜度。每個(gè)程序我們只需抽取其中 “F i x y”和“E”即可計(jì)算時(shí)間復(fù)雜度。注意：循環(huán)結(jié)構(gòu) 。注意：循環(huán)結(jié)構(gòu)允許嵌套。 允許嵌套。 接下來每個(gè)程序的第一行包含一個(gè)正整數(shù) L 和一個(gè)字符串，L 代表程序行數(shù)，字符串表示這個(gè)程序的復(fù)雜度， “ O(1)”表示常數(shù)復(fù)雜度， “ O(n^w)”表示復(fù)雜度為𝑛𝑤，其中w 是一個(gè)小于100 的正整數(shù)（輸入中不包含引號(hào)） ，輸入保證復(fù)雜度只有O(1)和O(

10、n^w) 兩種類型。 接下來 L 行代表程序中循環(huán)結(jié)構(gòu)中的“F i x y”或者 “E” 。程序行若以“F”開頭，表示進(jìn)入一個(gè)循環(huán)，之后有空格分離的三個(gè)字符（串）i x y， 其中 i 是一個(gè)小寫字母（保證不為“n” ） ，表示新建的變量名，x 和 y 可能是正整數(shù)或 n ，已知若為正整數(shù)則一定小于 100。 程序行若以“E”開頭，則表示循環(huán)體結(jié)束。 【輸出格式】 輸出文件名為 complexity.out。 輸出文件共 t