CSP-S2019第二輪認(rèn)證(原NOIP提高組復(fù)賽)試題

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