NOIP復賽普及組試題精編版

1、CCF全國信息學奧林匹克聯(lián)賽（ NOIP2013 ）復賽（請選手務必仔細閱讀本頁內(nèi)容）題目概況中文題目名稱計數(shù)問題表送式求但小朋友的數(shù)字車站分級英文題目與子目錄名countexprnumberlevel可執(zhí)行文件名countexprnumberlevel輸入文件名count.inexpr.innumber.inlevel.in輸出文件名count.outexpr.outnumber.outlevel.out每個測試點時限1秒1秒1秒1秒測試點數(shù)目10101010每個測試點分值10101010附加樣例文件有有有有結果比較方式全文比較（過濾行末空格及文末回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)傳統(tǒng)運行內(nèi)存上限1

2、28M128M128M128M.提交源程序文件名對于C+語百count.cppexpr.cppnumber.cpplevel.cpp對于C語百umber.clevel.c對于pascal語百count.pasexpr.pasnumber.paslevel.pas三.編譯命令(不包含任何優(yōu)化開關)對于C+語百g+ - o count count.cpp -lmg+ - o expr expr.cpp -lmg+ - o number number.cpp -lmg+ - o level level.cpp -lm對于C語百gcc - o count count.c -

3、lmgcc-o expr expr.c -lmgcc- o number number.c -lmgcc - o level level.c -lm對于pascal語百fpc count.pasfpc expr.pasfpc number.pasfpc level.pas注意事項：1、文件名(程序名和輸入輸出文件名)必須使用英文小寫。2、C/C+中函數(shù)main()的返回值類型必須是 int,程序正常結束時的返回值必須是0。3、全國統(tǒng)一評測時采用的機器配置為：CPU AMD Athlon(tm) 64x2 Dual Core CPU 5200+2.71GHz,內(nèi)存2G,上述時限以此配置為準。4、

4、只提供Linux格式附加樣例文件。5、特別提醒：評測在 NOI Linux下進行。1 .記數(shù)問題(count.cpp/c/pas)【問題描述】試計算在區(qū)間1到n的所有整數(shù)中，數(shù)字 x (0 w x言 共出現(xiàn)了多少次？例如，在 1 到 11 中，即在 1、2、3、4、5、6、7、8、9、10、11 中，數(shù)字 1 出現(xiàn)了 4 次?！据斎搿枯斎胛募麨?count.in。輸入共1行，包含2個整數(shù)n、x,之間用一個空格隔開。【輸出】輸出文件名為 count.out。輸出共1行，包含一個整數(shù)，表示 x出現(xiàn)的次數(shù)?！据斎胼敵鰳永縞ount.incount.out11 14【數(shù)據(jù)說明】對于 100%的數(shù)據(jù)

5、，1w n w 1,000,000 < x o< 92 .表達式求值(expr.cpp/c/pas)【問題描述】給定一個只包含加法和乘法的算術表達式，請你編程計算表達式的值?！据斎搿枯斎胛募閑xpr.in。輸入僅有一行，為需要你計算的表達式，表達式中只包含數(shù)字、加法運算符“+”和乘法運算符“ *”，且沒有括號，所有參與運算的數(shù)字均為0到231-1之間的整數(shù)。輸入數(shù)據(jù)保證這一行只有0 9、+、*這12種字符。【輸出】輸出文件名為expr.out。輸出只有一行，包含一個整數(shù)，表示這個表達式的值。注意：當答案長度多于4位時,請只輸出最后4位，前導0不輸出?！据斎胼敵鰳永?】expr.i

6、nexpr.out1+1*3+48【輸入輸出樣例 2】expr.inexpr.out1+1234567890*17891【輸入輸出樣例3】expr.inexpr.out1+1000000003*14【輸入輸出樣例說明】樣例1計算的結果為8,直接輸出8。樣例2計算的結果為1234567891,輸出后4位，即7891。樣例3計算的結果為1000000004,輸出后4位，即4?！緮?shù)據(jù)范圍】對于 30%的數(shù)據(jù)，0砧達式中加法運算符和乘法運算符的總 數(shù)W 100對于80%的數(shù)據(jù)，0送達式中加法運算符和乘法運算符的總 數(shù) w 100。對于100%的數(shù)據(jù)，0砧達式中加法運算符和乘法運算符的總數(shù)< 10

7、00003 .小朋友的數(shù)字（number.cpp/c/pas）【問題描述】有n個小朋友排成一列。每個小朋友手上都有一個數(shù)字，這個數(shù)字可正可負。規(guī)定每個 小朋友的特征值等于排在他前面（包括他本人）的小朋友中連續(xù)若干個（最少有一個）小朋 友手上的數(shù)字之和的最大值。作為這些小朋友的老師，你需要給每個小朋友一個分數(shù)，分數(shù)是這樣規(guī)定的：第一個小 朋友的分數(shù)是他的特征值，其它小朋友的分數(shù)為排在他前面的所有小朋友中（不包括他本人） 小朋友分數(shù)加上其特征值的最大值。請計算所有小朋友分數(shù)的最大值，輸出時保持最大值的符號，將其絕對值對p取模后輸出?！据斎搿枯斎胛募閚umber.in。第一行包含兩個正整數(shù) n、p

8、,之間用一個空格隔開。第二行包含n個數(shù)，每兩個整數(shù)之間用一個空格隔開，表示每個小朋友手上的數(shù)字?！据敵觥縫取模的結果。輸出文件名為 number.outo輸出只有一行，包含一個整數(shù)，表示最大分數(shù)對【輸入輸出樣例1】number.innumber.out5 9971 2 3 4 521【輸入輸出樣例說明】小朋友的特征值分別為 1、3、6、10、15 ,分數(shù)分別為1、2、5、11、21 ,最大值21對997的模是21?！据斎胼敵鰳永?2】number.innumber.out5 7-1 -1 -1 -1 -1-1【輸入輸出樣例說明】小朋友的特征值分別為-1、-1、-1、-1、-1 ,分數(shù)分別為-1

9、、-2、-2、-2、-2 ,最大值-1對7的模為-1 ,輸出-1?！緮?shù)據(jù)范圍】對于 50%的數(shù)據(jù)，1 w n w 1,000 w p & 1顧0W字的絕對值不超過 1000;對于100%的數(shù)據(jù)，1 w n w 1,000,000 w p 卷其他數(shù)字的絕對值均不超過109。4.車站分級(level.cpp/c/pas)【問題描述】一條單向的鐵路線上，依次有編號為1, 2,，n的n個火車站。每個火車站都有一個級別，最低為1級。現(xiàn)有若干趟車次在這條線路上行駛，每一趟都滿足如下要求：如果這趟車次停靠了火車站 x,則始發(fā)站、終點站之間所有級別大于等于火車站x的都必須停靠。（注意：起始站和終點站自

10、然也算作事先已知需要?？康恼军c）例如，下表是5趟車次的運行情況。其中，前4趟車次均滿足要求，而第 5趟車次由于?？苛?3號火車站（2級）卻未?？客窘?jīng)的 6號火車站（亦為2級）而不滿足要求。車站編號123456789W|OiJ車次3121321131始停停終23始始停停終終4始停停停停終5始停終現(xiàn)有m趟車次的運行情況（全部滿足要求），試推算這n個火車站至少分為幾個不同的級別?！据斎搿枯斎胛募閘evel.in。第一行包含2個正整數(shù)n, m,用一個空格隔開。第i + 1行（1條wm）中，首先是一個正整數(shù) Si （2奇wn）,表示第i趟車次有s個停靠站；接下來有Si個正整數(shù)，表示所有停靠站的編號，從小到大排列。每兩個數(shù)之間用一個空格隔開。輸入保證所有的車次都滿足要求。【輸出】輸出文件為level.outo輸出只有一行，包含一個正整