CSP-S2019第二輪認證(原NOIP提高組復賽)試題

2019年CCF非專業(yè)級軟件能力認證第二輪提高級時間：2019年11月16日08:30～12:00題目名稱格雷碼括號樹樹上的數(shù)題目類型傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型目錄可執(zhí)行文件名輸入文件名brackets.in輸出文件名每個測試點時限1.0秒1.0秒2.0秒內(nèi)存限制子任務數(shù)目測試點是否等分是是是提交源程序文件名code.c對于Pascal語言編譯選項對于C語言對于Pascal語言1.文件名(程序名和輸入輸出文件名)必須使用英文小寫。2.C/C++中函數(shù)main()的返回值類型必須是int,程序正常結束時的返回值必須3.提交的程序代碼文件的放置位置請參照各省的具體要求。4.因違反以上三點而出現(xiàn)的錯誤或問題，申訴時一律不予受理。5.若無特殊說明，結果的比較方式為全文比較(過濾行末空格及文末回車)。2019年CCF非專業(yè)級軟件能力認證第二輪提高級6.程序可使用的棧內(nèi)存空間限制與題目的內(nèi)存限制一致。7.全國統(tǒng)一評測時采用的機器配置為：Intcl(R)Corc(TM)i7-8700KCPU@3.70GHz,內(nèi)存32GB。上述時限以此配置為準。9.評測在當前最新公布的NOILinux下進行，各語言的編譯器版本以其為準。10.最終評測時所用的編譯命a。【題目描述】通常，人們習慣將所有n位二進制串按照字典序排列，例如所有2位二進制串按字典序從小到大排列為：00,01,10,11。格雷碼(GrayCodc)是一種特殊的n位二進制串排列法，它要求相鄰的兩個二進所有2位二進制串按格雷碼排列的一個例子為：00,01,11,10。n位格雷碼不止一種，下面給出其中一種格雷碼的生成算法：1.1位格雷碼由兩個1位二進制串組成，順序為：0,1。2.n+1位格雷碼的前2”個二進制串，可以由依此算法生成的n位格雷碼(總共2”個n位二進制串)按順序排列，再在每個串前加一個前綴0構成。3.n+1位格雷碼的后2”個二進制串，可以由依此算法生成的n位格雷碼(總共2”個n位二進制串)按逆序排列，再在每個串前加一個前綴1構成。綜上，n+1位格雷碼，由n位格雷碼的2"個二進制串按順序排列再加前綴0,和按逆序排列再加前綴1構成，共2n+1個二進制串。另外，對于n位格雷碼中的2"個二進制串，我們按上述算法得到的排列順序將它們從0～2"-1編號。按該算法，2位格雷碼可以這樣推出：1.已知1位格雷碼為0,1。2.前兩個格雷碼為00,01。后兩個格雷碼為11,10。合并得到00,01,11,10,編號依次為0～3。同理，3位格雷碼可以這樣推出：1.已知2位格雷碼為：00,01,11,10。2.前四個格雷碼為：000,001,011,010。后四個格雷碼為：110,111,101,100。合并得到：000,001,011,010,110,111,101,100,編號依次為0～7?，F(xiàn)在給出n,k,請你求出按上述算法生成的n位格雷碼中的k號二進制串?！据斎敫袷健績H一行兩個整數(shù)n,k,意義見題目描述?！据敵龈袷健枯敵龅轿募ode.out中。僅一行一個n位二進制串表示答案。【樣例1輸入】【樣例1輸出】【樣例1解釋】2位格雷碼為：00,01,11,10,編號從0～3,因此3號串是10。【樣例2輸入】【樣例2輸出】【樣例2解釋】3位格雷碼為：000,001,011,010,110,111,101,100,編號從0～7,因此5號串是111。【樣例3】對于80%的數(shù)據(jù)：k≤5×10?對于95%的數(shù)據(jù)：k≤263-1對于100%的數(shù)據(jù)：1≤n≤64,0≤k<2"【題目背景】1.()是合法括號串。2.如果A是合法括號串，則(A)是合法括號串。3.如果A,B是合法括號串，則AB是合法括號串。1.字符串S的子串是S中連續(xù)的任意個字符組成的字符串。S的子串可用起始位置1與終止位置r來表示，記為S(l,r)(1≤l≤r≤|S|,|S|表示S的長度)。2.S的兩個子串視作不同當且僅當它們在S中的位置不同，即1不同或r不同。【題目描述】一個大小為n的樹包含n個結點和n-1條邊，每條邊連接兩個結點，且任意兩個小Q是一個充滿好奇心的小朋友，有一天他在上學的路上碰見了一個大小為n的樹，樹上結點從1～n編號，1號結點為樹的根。除1號結點外，每個結點有一個父親根結點到i號結點的簡單路徑上的括號，按結點經(jīng)過順序依次排列組成的字符串。這個問題難倒了小Q,他只好向你求助。設s;共有k;個不同子串是合法括號串，你只需要告訴小Q所有i×k;的異或和，即：【輸入格式】第一行一個整數(shù)n,表示樹的大小。第三行包含n-1個整數(shù)，第i(1≤i<n)個整數(shù)表示i+1號結點的父親編號fi+1。2019年CCF非專業(yè)級軟件能力認證第二輪提高級1括y(brackets)【輸出格式】【樣例1輸入】5【樣例1輸出】6【樣例1解釋】將根到1號結點的簡單路徑上的括號，按經(jīng)過順序排列所組成的字符串為(,子串是合法括號串的個數(shù)為0。將根到2號結點的簡單路徑上的括號，按經(jīng)過順序排列所組成的字符串為((,子串是合法括號串的個數(shù)為0。將根到3號結點的簡單路徑上的括號，按經(jīng)過順序排列所組成的字符串為(),子串是合法括號串的個數(shù)為1。將根到4號結點的簡單路徑上的括號，按經(jīng)過順序排列所組成的字符串為(((,子串是合法括號串的個數(shù)為0。將根到5號結點的簡單路徑上的括號，按經(jīng)過順序排列所組成的字符串為((),子串是合法括號串的個數(shù)為1。【樣例2】見選手目錄下的brackets/brackets2.in與brackets/brackets2.ans?！緲永?】見選手目錄下的brackets/brackets3.in與brackets/brackets3.ans。【數(shù)據(jù)范圍】測試點編號特殊性質(zhì)8無無樹上的數(shù)(tree)【題目描述】給定一個大小為n的樹，它共有n個結點與n-1條邊，結點從1～n編號。初始時每個結點上都有一個1～n的數(shù)字，且每個1～n的數(shù)字都只在恰好一個結點上出現(xiàn)。接下來你需要進行恰好n-1次刪邊操作，每次操作你需要選一條未被刪去的邊，此時這條邊所連接的兩個結點上的數(shù)字將會交換，然后這條邊將被刪去。n-1次操作過后，所有的邊都將被刪去。此時，按數(shù)字從小到大的順序，將數(shù)字1～n所在的結點編號依次排列，就得到一個結點編號的排列P;。現(xiàn)在請你求出，在最的順序刪去所有邊，樹變?yōu)橄聢D。按數(shù)字順序得到的結點編號排列為①③④②⑥,該【輸入格式】第一行一個正整數(shù)T,表示數(shù)據(jù)組數(shù)。第二行n個整數(shù)，第i(1≤i≤n)個整數(shù)表示數(shù)字i初始時所在的結點編號。接下來n-1行每行兩個整數(shù)x,y,表示一條連接x號結點與y號結點的邊。2019年CCF【輸出格式】對于每組測試數(shù)據(jù)，輸出一行共n個用空格隔開的整數(shù)，表示最優(yōu)操作方案下所【樣例1輸入】45552019年【樣例1輸出】【樣例2】【數(shù)據(jù)范圍】測試點編號特殊性質(zhì)無樹的形態(tài)是一條鏈存在度數(shù)為n-1的結點無對于所有測試點：1≤T≤10,保證給出的是一個樹。2019年CCF非專業(yè)級軟件能力認證第二輪提高級時間：2019年11月17日08:30～12:00題目名稱Emiya家今天的飯劃分樹的重心題目類型傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型目錄可執(zhí)行文件名輸入文件名meal.inpartition.in輸出文件名meal.out每個測試點時限1.0秒2.0秒3.0秒內(nèi)存限制子任務數(shù)目測試點是否等分是是是提交源程序文件名meal.c對于Pascal語言編譯選項對于C語言對于Pascal語言1.文件名(程序名和輸入輸出文件名)必須使用英文小寫。2.C/C++中函數(shù)main()的返回值類型必須是int,程序正常結束時的返回值必須3.提交的程序代碼文件的放置位置請參照各省的具體要求。4.因違反以上三點而出現(xiàn)的錯誤或問題，申訴時一律不予受理。5.若無特殊說明，結果的比較方式為全文比較(過濾行末空格及文末回車)。2019年CCF非專業(yè)級軟件能力認證第二輪提高級6.程序可使用的棧內(nèi)存空間限制與題目的內(nèi)存限制一致。7.全國統(tǒng)一評測時采用的機器配置為：Intcl(R)Corc(TM)i7-8700KCPU@3.70GHz,內(nèi)存32GB。上述時限以此配置為準。9.評測在當前最新公布的NOILinux下進行，各語言的編譯器版本以其為準。10.最終評測時所用的編譯命令中不含任何優(yōu)化開關。Emiya家今天的飯(meal)【題目描述】Emiya是個擅長做菜的高中生，他共掌握n種烹飪方法，且會使用m種主要食材做菜。為了方便敘述，我們對烹飪方法從1～n編號，對主要食材從1～m編號。Emiya做的每道菜都將使用恰好一種烹飪方法與恰好一種主要食材。更具體地，Emiya會做a,;道不同的使用烹飪方法i和主要食材j的菜(1≤i≤n,1≤j≤m),這也意味著Emiya總共會做道不同的菜。Emiya今天要準備一桌飯招待Yazid和Rin這對好朋友，然而三個人對菜的搭配有不同的要求，更具體地，對于一種包含k道菜的搭配方案而言：●Eniya不會讓大家餓肚子，所以將做●Rin希望品嘗不同烹飪方法做出的菜，因此她要求每道菜的烹飪方法互不相同●Yazid不希望品嘗太多同一食材做出的菜，因此他要求每種主要食材至多在一半的菜(即L道菜)中被使用-這里的Lx」為下取整函數(shù)，表示不超過x的最大整數(shù)這些要求難不倒Emiya,但他想知道共有多少種不同的符合要求的搭配方案。兩種方案不同，當且僅當存在至少一道菜在一種方案中出現(xiàn)，而不在另一種方案中出現(xiàn)。Emiya找到了你，請你幫他計算，你只需要告訴他符合所有要求的搭配方案數(shù)對質(zhì)數(shù)998,244,353取模的結果?！据斎敫袷健康?行兩個用單個空格隔開的整數(shù)n,m。第2行至第n+1行，每行m個用單個空格隔開的整數(shù)，其中第i+1行的m個【輸出格式】輸出到文件meal.out中。僅一行一個整數(shù)，表示所求方案數(shù)對998,244,353取模的結果?！緲永?輸入】【樣例1輸出】3【樣例1解釋】由于在這個樣例中，對于每組i,j,Emiya都最多只會做一道菜，因此我們直接通過給出烹飪方法、主要食材的編號來描述一道菜。符合要求的方案包括：●做一道用烹飪方法1、主要食材1的菜和一道用烹飪方法2、主要食材2的菜●做一道用烹飪方法1、主要食材1的菜和一道用烹飪方法2、主要食材3的菜●做一道用烹飪方法1、主要食材3的菜和一道用烹飪方法2、主要食材2的菜因此輸出結果為3mod998,244,353=3。需要注意的是，所有只包含一道菜的方案都是不符合要求的，因為唯一的主要食材在超過一半的菜中出現(xiàn)，這不滿足Yazid的要求?！緲永?輸入】【樣例2輸出】【樣例2解釋】Emiya必須至少做2道菜。做2道菜的符合要求的方案數(shù)為100。做3道菜的符合要求的方案數(shù)為90。因此符合要求的方案數(shù)為100+90=190?！緲永?輸入】2019年CCF非專業(yè)級軟件能力認證第二輪提高級day2Emiya家今天的飯(meal)第5頁共11頁【樣例3輸出】【樣例4】【樣例5】【數(shù)據(jù)范圍】測試點編號n=122223352435263728323對于所有測試點，保證1≤n≤100,1≤m≤2000,O≤ajj<998,244,353。2019年【題目描述】小明對該題設計出了一個暴力程序，對于一組規(guī)模為u的數(shù)據(jù)，該程序的運行時間為u2。然而這個程序運行完一組規(guī)模為u的數(shù)據(jù)之后，它將在任何一組規(guī)模小于u的數(shù)據(jù)上運行錯誤。樣例中的a;不一定遞增，但小明又想在不修改程序的情況下正確也就是說，小明需要找到一些分界點1≤k?<k?<…<kp<n,注意p可以為0且此時k?=0,也就是小明可以將所有數(shù)據(jù)合并在一起運行。【輸入格式】1.若type=0,則該測試點的a;直接給出。輸入文件接下來：第二行n個以空格第二行六個以空格分隔的整數(shù)x,y,z,b?,b?,m。接下來m行中，第i(1≤i≤m)行包含三個以空格分隔的正整數(shù)p,l,r。對于type=1的23～25號測試點，a;的生成方式如下：給定整數(shù)x,y,z,b?,bz,m,以及m個三元組(pr,l,ri)。保證n≥2。若n>2,則V3≤i保證1≤P?≤n,Pm=n。令po=0,則p;還滿足VO≤i<m有p?<p?+1。對于所有1≤j≤m,若下標值i(1≤i≤n)滿足Pj-1<i≤Pj,則有【樣例1輸入】【樣例1輸出】【樣例1解釋】答案為(5+1)2+72+92+92=247。方案，因為5>1?！緲永?輸入】【樣例2輸出】【樣例2解釋】2019年CCF非專業(yè)級軟件能力認證第二輪提高級2劃yd(partition)【樣例3輸入】【樣例3輸出】【樣例4】【樣例5】見選手目錄下的partition/partition5.in【數(shù)據(jù)范圍】測試點編號01所有測試點滿足：type∈{0,1},2≤n≤4×10?,1≤a;≤10°,1≤m≤10?樹的重心(centroid)【題目描述】小簡單正在學習離散數(shù)學，今天的內(nèi)容是圖論基礎，在課上他做了如下兩條筆記：1.一個大小為n的樹由n個結點與n-1條無向邊構成，且滿足任意兩個結點間有且僅有一條簡單路徑。在樹中刪去一個結點及與它關聯(lián)的邊，樹將分裂為若干個子樹；而在樹中刪去一條邊(保留關聯(lián)結點，下同),樹將分裂為恰好兩個子樹。2.對于一個大小為n的樹與任意一個樹中結點c,稱c是該樹的重心當且僅當在樹是下取整函數(shù))。對于包含至少一個結點的樹，它的重心只可能有1或2個。課后老師給出了一個大小為n的樹S,樹中結點從1～n編號。小簡單的課后作業(yè)是求出S單獨刪去每條邊后，分裂出的兩個子樹的重心編號和之和。即：上式中，E表示樹S的邊集，(u,v)表示一條連接u號點和v號點的邊。S?與S?分別表示樹S刪去邊(u,v)后，u號點與v號點所在的被分裂出的子樹。小簡單覺得作業(yè)并不簡單，只好向你求助，請你教教他?！据斎敫袷健勘绢}輸入包含多組測試數(shù)據(jù)。第一行一個整數(shù)T表示數(shù)據(jù)組數(shù)。接下來依次給出每組輸入數(shù)據(jù)，對于每組數(shù)據(jù)：第一行一個整數(shù)n表示樹S的大小。接下來n-1行，每行兩個