noip2017提高組復(fù)賽解題報(bào)告

1、noip2017 提高組復(fù)賽解題報(bào)告 定期推送帳號(hào)信息學(xué)新聞，競(jìng)賽自主招生，信息學(xué)專業(yè)知識(shí)，信息學(xué)疑難解答，融科教育信息學(xué)競(jìng)賽培訓(xùn)等諸多優(yōu)質(zhì)內(nèi)容的微信平臺(tái)，歡迎分享文章給你的朋友或者朋友圈！以下解題思路及代碼未經(jīng)官方評(píng)測(cè)，僅供參考，復(fù)賽成績(jī)以官方（CCF）評(píng)測(cè)結(jié)果為準(zhǔn)。 Day1 1.小凱的疑惑 (math.cpp/c/pas)【問(wèn)題描述】小凱手中有兩種面值的金幣，兩種面值均為正整數(shù)且彼此互素。每種金幣小凱都有無(wú)數(shù)個(gè)。在不找零的情況下，

2、僅憑這兩種金幣，有些物品他是無(wú)法準(zhǔn)確支付的?，F(xiàn)在小凱想知道在無(wú)法準(zhǔn)確支付的物品中，最貴的價(jià)值是多少金幣?注意:輸入數(shù)據(jù)保證存在小凱無(wú)法準(zhǔn)確支付的商品。 【輸入格式】輸入文件名為 math.in。輸入數(shù)據(jù)僅一行，包含兩個(gè)正整數(shù) a 和 b，它們之間用一個(gè)空格隔開(kāi)，表示小凱手中金幣的面值。 【輸出格式】輸出文件名為 math.out。輸出文件僅一行，一個(gè)正整數(shù) N，表示不找零的情況下，小凱用手中的金幣不能準(zhǔn)確支付的最貴的物品的價(jià)值。 【輸入

3、輸出樣例 1】math.in3 7 math.out11 【數(shù)據(jù)規(guī)模與約定】 對(duì)于 30%的數(shù)據(jù): 1 ≤ a， b ≤ 50。對(duì)于 60%的數(shù)據(jù): 1 ≤ a，b ≤ 10,000。對(duì)于 100%的數(shù)據(jù):1 ≤ a，b ≤ 1,000,000,000。 數(shù)學(xué)太差只找規(guī)律吧。寫(xiě)英文字母“O”表示通常意義下“Θ” 的概念。 【輸入格式】輸入文件名為 complexity.in。 輸入文件第一行一個(gè)正整數(shù) t，表示有 t(t ≤ 10)個(gè)

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

5、構(gòu)中的“F i x y”或者 “E” 。程序行若以“F”開(kāi)頭，表示進(jìn)入一個(gè)循環(huán)，之后有空格分離的三個(gè)字符(串)i x y，其中 i 是一個(gè)小寫(xiě)字母(保證不為 “n” )， 表示新建的變量名， x 和 y 可能是正整數(shù)或 n ，已知若為正整數(shù)則一定小于 100。程序行若以“E”開(kāi)頭，則表示循環(huán)體結(jié)束。 【輸出格式】輸出文件名為 complexity.out。輸出文件共 t 行，對(duì)應(yīng)輸入的 t 個(gè)程序，每行輸出“Yes”或“No”或者“ER