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

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

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

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

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

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

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

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

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

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

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