資源簡介 noip2019第十年全國青少年信息學奧林匹克聯賽普及組復賽試題 〔普及組三小時完成〕 【一】不高興的津津 【問題描述】 津津上初中了。媽媽認為津津應該更加用功學習,所以津津除了上學之外,還要參加媽媽為她報名的各科復習班。另外每周媽媽還會送她去學習朗誦、舞蹈和鋼琴。但是津津如果一天上課超過八個小時就會不高興,而且上得越久就會越不高興。假設津津不會因為其它事不高興,并且她的不高興不會持續到第二天。請你幫忙檢查一下津津下周的日程安排,看看下周她會不會不高興;如果會的話,哪天最不高興。 【輸入文件】 輸入文件unhappy.in包括七行數據,分別表示周一到周日的日程安排。每行包括兩個小于10的非負整數,用空格隔開,分別表示津津在學校上課的時間和媽媽安排她上課的時間。 【輸出文件】 輸出文件unhappy.out包括一行,這一行只包含一個數字。如果不會不高興那么輸出0,如果會那么輸出最不高興的是周幾〔用1,2,3,4,5,6,7分別表示周一,周二,周三,周四,周五,周六,周日〕。如果有兩天或兩天以上不高興的程度相當,那么輸出時間最靠前的一天。 【樣例輸入】 53 62 72 53 54 04 06 【樣例輸出】 3 【二】花生采摘(peanuts.pas/dpr/c/cpp) 【問題描述】 魯賓遜先生有一只寵物猴,名叫多多。這天,他們兩個正沿著鄉間小路散步,突然發現路邊的告示牌上貼著一張小小的紙條:“歡迎免費品嘗我種的花生!——熊字”。 魯賓遜先生和多多都很開心,因為花生正是他們的最愛。在告示牌背后,路邊真的有一塊花生田,花生植株整齊地排列成矩形網格〔如圖1〕。有經驗的多多一眼就能看出,每棵花生植株下的花生有多少。為了訓練多多的算術,魯賓遜先生說:“你先找出花生最多的植株,去采摘它的花生;然后再找出剩下的植株里花生最多的,去采摘它的花生;依此類推,不過你一定要在我限定的時間內回到路邊。” 我們假定多多在每個單位時間內,可以做以下四件事情中的一件: 1)從路邊跳到最靠近路邊〔即第一行〕的某棵花生植株; 2)從一棵植株跳到前后左右與之相鄰的另一棵植株; 3)采摘一棵植株下的花生; 4)從最靠近路邊〔即第一行〕的某棵花生植株跳回路邊。 現在給定一塊花生田的大小和花生的分布,請問在限定時間內,多多最多可以采到多少個花生?注意可能只有部分植株下面長有花生,假設這些植株下的花生個數各不相同。 例如在圖2所示的花生田里,只有位于(2,5),(3,7),(4,2),(5,4)的植株下長有花生,個數分別為13,7,15,9。沿著圖示的路線,多多在21個單位時間內,最多可以采到37個花生。 【輸入文件】 輸入文件peanuts.in的第一行包括三個整數,M,N和K,用空格隔開;表示花生田的大小為M*N〔1<=M,N<=20〕,多多采花生的限定時間為K〔0<=K<=1000〕個單位時間。接下來的M行,每行包括N個非負整數,也用空格隔開;第i+1行的第j個整數Pij〔0<=Pij<=500〕表示花生田里植株(i,j)下花生的數目,0表示該植株下沒有花生。 【輸出文件】 輸出文件peanuts.out包括一行,這一行只包含一個整數,即在限定時間內,多多最多可以采到花生的個數。 【樣例輸入1】 6721 0000000 00001300 0000007 01500000 0009000 0000000 【樣例輸出1】 37 【樣例輸入2】 6720 0000000 00001300 0000007 01500000 0009000 0000000 【樣例輸出2】 28 【三】FBI樹(fbi.pas/dpr/c/cpp) 【問題描述】 我們可以把由“0”和“1”組成的字符串分為三類:全“0”串稱為B串,全“1”串稱為I串,既含“0”又含“1”的串那么稱為F串。 FBI樹是一種二叉樹[1],它的結點類型也包括F結點,B結點和I結點三種。由一個長度為2N的“01”串S可以構造出一棵FBI樹T,遞歸的構造方法如下: 1)T的根結點為R,其類型與串S的類型相同; 2)假設串S的長度大于1,將串S從中間分開,分為等長的左右子串S1和S2;由左子串S1構造R的左子樹T1,由右子串S2構造R的右子樹T2。 現在給定一個長度為2N的“01”串,請用上述構造方法構造出一棵FBI樹,并輸出它的后序遍歷[2]序列。 【輸入文件】 輸入文件fbi.in的第一行是一個整數N〔0<=N<=10〕,第二行是一個長度為2N的“01”串。 【輸出文件】 輸出文件fbi.out包括一行,這一行只包含一個字符串,即FBI樹的后序遍歷序列。 【樣例輸入】 3 10001011 【樣例輸出】 IBFBBBFIBFIIIFF 【數據規模】 對于40%的數據,N<=2; 對于全部的數據,N<=10。 【四】火星人(martian.pas/dpr/c/cpp) 【問題描述】 人類終于登上了火星的土地并且見到了神秘的火星人。人類和火星人都無法理解對方的語言,但是我們的科學家發明了一種用數字交流的方法。這種交流方法是這樣的,首先,火星人把一個非常大的數字告訴人類科學家,科學家破解這個數字的含義后,再把一個很小的數字加到這個大數上面,把結果告訴火星人,作為人類的回答。 火星人用一種非常簡單的方式來表示數字——掰手指。火星人只有一只手,但這只手上有成千上萬的手指,這些手指排成一列,分別編號為1,2,3……。火星人的任意兩根手指都能隨意交換位置,他們就是通過這方法計數的。 一個火星人用一個人類的手演示了如何用手指計數。如果把五根手指——拇指、食指、中指、無名指和小指分別編號為1,2,3,4和5,當它們按正常順序排列時,形成了5位數12345,當你交換無名指和小指的位置時,會形成5位數12354,當你把五個手指的順序完全顛倒時,會形成54321,在所有能夠形成的120個5位數中,12345最小,它表示1;12354第二小,它表示2;54321最大,它表示120。下表展示了只有3根手指時能夠形成的6個3位數和它們代表的數字: 三進制數 123 132 213 231 312 321 代表的數字 1 2 3 4 5 6 現在你有幸成為了第一個和火星人交流的地球人。一個火星人會讓你看他的手指,科學家會告訴你要加上去的很小的數。你的任務是,把火星人用手指表示的數與科學家告訴你的數相加,并根據相加的結果改變火星人手指的排列順序。輸入數據保證這個結果不會超出火星人手指能表示的范圍。 【輸入文件】 輸入文件martian.in包括三行,第一行有一個正整數N,表示火星人手指的數目〔1<=N<=10000〕。第二行是一個正整數M,表示要加上去的小整數〔1<=M<=100〕。下一行是1到N這N個整數的一個排列,用空格隔開,表示火星人手指的排列順序。 【輸出文件】 輸出文件martian.out只有一行,這一行含有N個整數,表示改變后的火星人手指的排列順序。每兩個相鄰的數中間用一個空格分開,不能有多余的空格。 【樣例輸入】 5 3 12345 【樣例輸出】 12453 【數據規模】 對于30%的數據,N<=15;對于60%的數據,N<=50;對于全部的數據,N<=10000; -------------------------------------------------------------------------------- [1]二叉樹:二叉樹是結點的有限集合,這個集合或為空集,或由一個根結點和兩棵不相交的二叉樹組成。這兩棵不相交的二叉樹分別稱為這個根結點的左子樹和右子樹。 [2]后序遍歷:后序遍歷是深度優先遍歷二叉樹的一種方法,它的遞歸定義是:先后序遍歷左子樹,再后序遍歷右子樹,最后訪問根。 NOIP普及組復賽參考程序-NOIP2004普及組解題參考 第一題:不高興的津津 方法:枚舉 程序: programunhappy;{writenbylxq2004.11.20} vara,i,x,y,d,max:byte; begin assign(input,'unhappy.in');reset(input); assign(output,'unhappy.out');rewrite(output); d:=0;max:=8; fori:=1to7dobegin readln(x,y); a:=x+y; ifa>maxthen begin max:=a;d:=i; end; end; writeln(d); close(input);close(output); end. 第二題:花生采摘 方法:排個序,然后迭代遞推 程序: programpeanuts;{writenbylxq2004.11.20} typemytype=record x,y,d:integer; end; vartime,all,num,i,j,m,n,k,u,v,z:integer; q:array[1..400]ofmytype; t:mytype; begin all:=0; assign(input,'peanuts.in'); reset(input); readln(m,n,k); fori:=1tomdo begin forj:=1tondo begin read(u); ifu>0then begin inc(all); q[all].x:=i;q[all].y:=j;q[all].d:=u; ifall>1then begin v:=1; whileq[v].d>udoinc(v); t:=q[all]; forz:=alldowntov+1doq[z]:=q[z-1]; q[v]:=t; end; end; end; readln; end; close(input); num:=0;time:=0;u:=0;v:=q[1].y; fori:=1toalldo begin iftime+abs(q[i].x-u)+abs(q[i].y-v)+1+q[i].x<=k thenbegin inc(num,q[i].d); time:=time+abs(q[i].x-u)+abs(q[i].y-v)+1; u:=q[i].x;v:=q[i].y; end elsebreak; end; assign(output,'peanuts.out'); rewrite(output); writeln(num); close(output); end. 第三題FBI樹 方法:遞歸即可,按后序遍歷直接邊生成邊打印。 程序: programfbi;{writenbylxq2004.11.20} varf:array[1..1024]ofchar; i,k,n:integer; c:char; functionlastorder(i,j,n:integer):char; varlc,rc:char; begin ifn=0thenlastorder:=f[i] elsebegin lc:=lastorder(i,(i+j)div2,n-1); write(lc); rc:=lastorder((i+j)div2+1,j,n-1); write(rc); iflc=rcthenlastorder:=lcelselastorder:='F'; end; end; begin assign(input,'fbi.in'); reset(input); readln(n); k:=1; fori:=1tondok:=k*2; fori:=1tokdo begin read(c); ifc='0'thenf[i]:='B'elsef[i]:='I' end; readln; close(input); assign(output,'fbi.out'); rewrite(output); writeln(lastorder(1,k,n)); close(output); end. 第四題火星人 方法:排列生成法,直接從指定序列用排列產生方法順序生成到后面M個。 程序: programmartian;{writenbylxq2004.11.20} constmaxn=10000; vara:array[1..maxn+1]ofinteger; b:array[1..maxn+1]ofboolean; n,m,i,p,k:integer; begin assign(input,'martian.in'); reset(input); readln(n); readln(m); fillchar(b,sizeof(b),false); fori:=1tondobeginread(a[i]);b[a[i>:=trueend;p:=n+1; k:=-1; whiletruedo begin ifp>nthenbegin dec(p); inc(k); b[a[i>:=false; ifk=mthenbreak; end; repeatinc(a[i]);untilnotb[a[i]];b[a[i]]:=true; ifa[i]>nthen beginb[a[i]]:=false;dec(p);b[a[i>:=falseend else begininc(p);a[i]:=0end; end; assign(output,'martian.out'); rewrite(output); fori:=1ton-1dowrite(a[i],'');writeln(a[n]); close(output) end. 展開更多...... 收起↑ 資源預覽 縮略圖、資源來源于二一教育資源庫