第十九全國(guó)信息學(xué)奧林匹克聯(lián)賽NOIP解題報(bào)告題解

1、第十九屆全國(guó)信息學(xué)奧林匹克聯(lián)賽（noip2013）解題報(bào)告（普及組）寧波市鎮(zhèn)海蛟川書(shū)院 郁庭第一題：記數(shù)(count)【分析】直接用最樸素的模擬來(lái)做，時(shí)間復(fù)雜度小于(數(shù)的個(gè)數(shù)*每個(gè)數(shù)位數(shù))， 1千萬(wàn)以內(nèi)的運(yùn)算次數(shù)是肯定不會(huì)超時(shí)的。代碼：var n,x,i,temp,j,count:longint;begin assign(input,'count.in');reset(input); assign(output,'count.out');rewrite(output); readln(n,x); for i:=1 to n do begin temp:=i; w

2、hile temp>0 do begin j:=temp mod 10; temp:=temp div 10; if j=x then inc(count);end;end;writeln(count);close(input);close(output);end.【再分析】這樣虐題目是會(huì)跌人品的，這段時(shí)間是非?？简?yàn)人品的時(shí)候（當(dāng)時(shí)數(shù)據(jù)、成績(jī)未公布，提心吊膽啊），于是就產(chǎn)生了下面的程序（時(shí)間復(fù)雜度就是數(shù)的位數(shù)），用幾個(gè)手算來(lái)說(shuō)明問(wèn)題：輸入：10134 1 （n=10134 x=1便于后面的描述）輸出：4204規(guī)律總結(jié)（從個(gè)位到高位用a1.ai來(lái)表示）：在第i位上固定x，把原數(shù)分成兩段，然

3、后考慮ai和x大小的關(guān)系，對(duì)應(yīng)了上面013的分析，不難發(fā)現(xiàn)：ai>x時(shí)，種數(shù)=（左段值+1）*（右段位數(shù)）ai=x時(shí)，種數(shù)=（左段值）*（右段位數(shù)）+（右段值+1）ai<x時(shí)，種數(shù)=（左段值）*（右段位數(shù)）別高興太早，如果x=0時(shí)，規(guī)律又有點(diǎn)不一樣，最高位不需要考慮、中左段值減1就行了，附上代碼varn,x,m,i,count,left,right,ans:longint;a,b:array0.7 of longint;begin assign(input,'count.in');reset(input); assign(output,'count.out&

4、#39;);rewrite(output); readln(m,x); b0:=1;n:=m;while m>0 do begininc(count); bcount:=bcount-1*10;acount:=m mod 10;m:=m div 10;end; bcount+1:=bcount*10; if x=0 then dec(count);for i:=1 to count do beginif ai<x then beginleft:=n div bi;right:=bi-1;inc(ans,left*right);endelse if ai=x then begin l

5、eft:=n div bi; if x=0 then dec(left); right:=bi-1;inc(ans,left*right+(n mod bi-1)+1);endelse beginleft:=n div bi+1; if x=0 then dec(left); right:=bi-1;inc(ans,left*right);end;end; if (x=0) and (n<10) then writeln(0) else if x=0 then writeln(ans) else writeln(ans); close(input);close(output);end.第

6、二題：表達(dá)式求值(expr)【分析】可以說(shuō)方法很多，又可以說(shuō)方法很少的題目，萬(wàn)變不離其中的模擬，但實(shí)現(xiàn)方法人各有異，我寫(xiě)得很樸素，一邊讀入一邊操作，省得ansistring操作，利用一個(gè)棧存放乘法加法，各種地方mod反正都不影響結(jié)果，于是代碼出爐了，寫(xiě)得比較快，沒(méi)有美感，請(qǐng)見(jiàn)諒。var i,j,k:longint; flag:boolean; c:char; tot,temp:qword; a:array0.100000 of longint;procedure add;begin inc(i);ai:=temp;temp:=0;end;procedure jisuan;beginif fla

7、g then begin ai-1:=(ai-1*ai) mod 10000;dec(i); end;end;begin assign(input,'expr.in');reset(input); assign(output,'expr.out');rewrite(output); while not eoln do beginread(c);case c of '+':begin add; jisuan; flag:=false; end; '*': begin add; jisuan; flag:=true; end; els

8、e begin val(c,k); temp:=temp*10+k; end end;end; inc(i); ai:=temp;tot:=0;if flag then begin inc(tot,ai*ai-1mod 10000); i:=i-2; end;while i>0 do begin inc(tot,ai); tot:=tot mod 10000; dec(i);end;writeln(tot); close(input);close(output);end.第三題：小朋友的數(shù)字(number)【本段吐槽可以無(wú)視】聯(lián)賽趕上自己評(píng)職稱(chēng)，沒(méi)隨隊(duì)過(guò)去，回來(lái)聽(tīng)說(shuō)第三題難懂，趕緊瞄了下

9、題目，孩子們啊，我不是和你們說(shuō)過(guò)的嗎，聯(lián)賽普及組就是考讀題目的啊，讀懂后簡(jiǎn)單有木有啊，本題就是最好的證明，再普通不過(guò)的遞推了，狀態(tài)轉(zhuǎn)移都沒(méi)有?！绢}目簡(jiǎn)述】給你n個(gè)數(shù)，讓你求對(duì)應(yīng)的n個(gè)特征值（前面的最大連續(xù)和，o(n)的掃描，滾瓜爛熟了），根據(jù)特征值求分?jǐn)?shù)值（前面的單個(gè)(分?jǐn)?shù)值+特征值)的最大值），題目需要輸出n個(gè)分?jǐn)?shù)值的最大值。【我的思路】o(n)掃描最大連續(xù)和，求出特征值，然后o(n)計(jì)算分?jǐn)?shù)值，同時(shí)用（分?jǐn)?shù)值+特征值）更新max。這個(gè)思路有一個(gè)需要注意的地方，分?jǐn)?shù)值+特征值會(huì)超過(guò)longint、int64（高精度可以解決），這里采用計(jì)算max時(shí)執(zhí)行mod p操作，于是就產(chǎn)生了如下問(wèn)題： 輸

10、入：5 981-409 -401 97 -96 -301特征值：-409 -409 -312 97 97分?jǐn)?shù)值：-409 -818 -818 -721 -624max ：-818 不變 -721 -624最終max停留在了-624，但明顯-409才是最大的分?jǐn)?shù)值，這個(gè)問(wèn)題其實(shí)就是max初值兩個(gè)-409惹的禍，必須要在后面所有特征值中判斷有沒(méi)有絕對(duì)值大于409的，否則max需要考慮第一個(gè)分?jǐn)?shù)值，以免出現(xiàn)這樣的錯(cuò)誤。附上代碼：vari,n,p:longint;a:array0.1000000 of longint;f,b:array0.1000000 of int64;max,temp:int64

11、; flag:boolean;begin assign(input,'number.in');reset(input); assign(output,'number.out');rewrite(output); readln(n,p); for i:=1 to n do beginread(ai);end;max:=-maxlongint; for i:=1 to n do begininc(temp,ai);if temp>max then max:=temp;if temp<0 then temp:=0; bi:=max;end; f1:=b1;

12、max:=f1+b1;if b1<0 then flag:=false;for i:=2 to n-1 do begin fi:=max; if bi>0 then begin if not flag and (bi>-b1) then flag:=true; max:=(fi+bi) mod p; end; end; if not flag and (max<f1) then max:=f1; writeln(max); close(input);close(output);end.第四題：車(chē)站分級(jí)(level)【本段吐槽可以無(wú)視】很基礎(chǔ)的拓?fù)渑判虬?，我看完題目首先想

13、了個(gè)貪心，發(fā)現(xiàn)有反例，于是畫(huà)了下圖就知道是用拓?fù)渥隽?，但腦中的思維定式（普及組貌似從來(lái)沒(méi)有過(guò)絕對(duì)的圖論題）讓我糾結(jié)了一下，想想有沒(méi)有其他巧方法，這個(gè)問(wèn)題也留給大家?！痉治雎詭虏邸窟@個(gè)程序沒(méi)什么難點(diǎn)，第一遍就過(guò)了樣例，但為什么只有我校念祖一人做對(duì)？難道是拓?fù)鋵?xiě)殘了，沒(méi)有用隊(duì)列存儲(chǔ)？這要問(wèn)幾個(gè)90分的同學(xué)了，應(yīng)該是超時(shí)丟的分吧。【解題思路】畫(huà)個(gè)圖，我手稿找不到了（估計(jì)是評(píng)完職稱(chēng)后隨那一大堆紙進(jìn)了垃圾桶了），不然可以掃描下省得畫(huà)var n,m,i,j,count,k,w,h,t:longint; get:array0.1000 of boolean; hav:array0.1000,0.1000

14、of boolean; jin,b,chu,a:array0.1000 of longint; next:array0.1000,0.1000 of longint; eq:array0.2000 of longint;procedure deal(j:longint);var i,k,te:longint;beginfor i:=1 to j do begin te:=jineqh; for k:=1 to te do begin dec(chunexteqh,k);/斷邊 if chunexteqh,k=0 then begineqt:=nexteqh,k;inc(t);end end;i

15、nc(h);end;end;begin assign(input,'level.in');reset(input); assign(output,'level.out');rewrite(output); readln(n,m);for i:=1 to m do beginread(j);count:=0;fillchar(get,sizeof(get),false);for k:=1 to j do beginread(ak);getak:=true;inc(count);bcount:=ak;end;readln;for k:=b1 to bcount doif not getk thenfor w:=1 to count doif not havk,bw then beginhavk,bw:=true;inc(jink);nextk,jink:=bw; /出去邊的指向inc(chubw); end; end;count:=0;h:=1;t:=1;for k:=