時(shí)間：2024年11月30日08:30～13:00題目名稱編輯字符串遺失的賦值樹的遍歷樹上查詢題目類型傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型目錄可執(zhí)行文件名輸入文件名輸出文件名每個(gè)測(cè)試點(diǎn)時(shí)限1.0秒1.0秒1.0秒2.0秒內(nèi)存限制測(cè)試點(diǎn)數(shù)目測(cè)試點(diǎn)是否等分是是是是提交源程序文件名編譯選項(xiàng)對(duì)于C++語(yǔ)言注意事項(xiàng)(請(qǐng)仔細(xì)閱讀)1.文件名(程序名和輸入輸出文件名)必須使用英文小寫。2.main函數(shù)的返回值類型必須是int,程序正常結(jié)束時(shí)的返回值必須是0。3.提交的程序代碼文件的放置位置請(qǐng)參考各省的具體要求。4.因違反以上三點(diǎn)而出現(xiàn)的錯(cuò)誤或問題，申訴時(shí)一律不予受理。5.若無(wú)特殊說(shuō)明，結(jié)果的比較方式為全文比較(過濾行末空格及文末回車)。6.選手提交的程序源文件必須不大于100KB。7.程序可使用的棧空間內(nèi)存限制與題目的內(nèi)存限制一致。內(nèi)存32GB。上述時(shí)限以此配置為準(zhǔn)。9.只提供Linux格式附加樣例文件。10.評(píng)測(cè)在當(dāng)前最新公布的NOILinux下進(jìn)行，各語(yǔ)言的編譯器版本以此為準(zhǔn)。編輯字符串(edit)【題目描述】小M有兩個(gè)長(zhǎng)度為n且字符集為{0,1}的字符串s1,S2。小M希望兩個(gè)字符串中對(duì)應(yīng)位置字符相同的出現(xiàn)次數(shù)盡可能多，即滿足S1,i=82,i的i(1≤i≤n)盡可能多。為此小M有一個(gè)字符串編輯工具，這個(gè)工具提供的基本操作是在一個(gè)字符串中交換兩個(gè)相鄰的字符。為了保持字符串的可辨識(shí)性，規(guī)定兩個(gè)字符串中的部分字符不能參與交換。小M可以用工具對(duì)s?或s?進(jìn)行多次字符交換，其中可以參與交換的字符能夠交換任意多次?，F(xiàn)在小M想知道，在使用編輯工具后，兩個(gè)字符串中對(duì)應(yīng)位置字符相同的出現(xiàn)次數(shù)最多能有多少?！据斎敫袷健繌奈募dit.in中讀入數(shù)據(jù)。輸入的第一行包含一個(gè)整數(shù)T,表示測(cè)試數(shù)據(jù)的組數(shù)。接下來(lái)包含T組數(shù)據(jù)，每組數(shù)據(jù)的格式如下：·第一行包含一個(gè)整數(shù)n,表示字符串長(zhǎng)度?！さ诙邪粋€(gè)長(zhǎng)度為n且字符集為{0,1}的字符串s1?！さ谌邪粋€(gè)長(zhǎng)度為n且字符集為{0,1}的字符串s??！さ谒男邪粋€(gè)長(zhǎng)度為n且字符集為{0,1}的字符串t?,其中t1,;為1表示S1,i可以參與交換，t1,為0表示81,;不可以參與交換。·第五行包含一個(gè)長(zhǎng)度為n且字符集為{0,1}的字符串t?,其中t?,;為1表示s2,i【輸出格式】輸出到文件edit.out中。對(duì)于每組測(cè)試數(shù)據(jù)輸出一行，包含一個(gè)整數(shù)，表示對(duì)應(yīng)的答案?！緲永?輸出】【樣例1解釋】最開始時(shí)，s?=011101,第4和第6個(gè)字符第5個(gè)字符不能參與交換。110101,最后交換s2,3與s2,4得到s?=110110。此時(shí)s?與s?的前4個(gè)位置上的字符【樣例2】該樣例共有10組測(cè)試數(shù)據(jù)，其中第i(1≤i≤10)組測(cè)試數(shù)據(jù)滿足數(shù)據(jù)范圍中描述的測(cè)試點(diǎn)2i-1的限制。測(cè)試點(diǎn)編號(hào)特殊性質(zhì)無(wú)ABC無(wú)特殊性質(zhì)B:保證t?=t?。特殊性質(zhì)C:保證t?和t?中各自恰有一個(gè)字符'θ'。第4頁(yè)共15頁(yè)CCF全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽CCFNOIP2024【題目描述】小F有n個(gè)變量x?,T?,…·,Tn。每個(gè)變量可以取1至v的整數(shù)取值。小F在這n個(gè)變量之間添加了n-1條二元限制，其中第i(1≤i≤n-1)條限制為：若xi=ai,則要求i+1=b;,且ai與bi為1到v之間的整數(shù)；當(dāng)xi≠a;時(shí)，第i條限制對(duì)Ti+1的值不做任何約束。除此之外，小F還添加了m條一元限制，其中第j(1≤j≤m)條限制為：xc,=dj。小F記住了所有c;和d;的值，但把所有a;和b;的值都忘了。同時(shí)小F知道：存在給每一個(gè)變量賦值的方案同時(shí)滿足所有這些限制?，F(xiàn)在小F想知道，有多少種ai,b;(1≤i≤n-1)取值的組合，使得能夠確保至少存在一種給每個(gè)變量xi賦值的方案可以同時(shí)滿足所有限制。由于方案數(shù)可能很大，小F只需要你輸出方案數(shù)對(duì)10?+7取模的結(jié)果?！据斎敫袷健繌奈募ssign.in中讀入數(shù)據(jù)。本題包含多組測(cè)試數(shù)據(jù)。輸入的第一行包含一個(gè)整數(shù)T,表示測(cè)試數(shù)據(jù)的組數(shù)。接下來(lái)包含T組數(shù)據(jù)，每組數(shù)據(jù)的格式如下：第一行包含三個(gè)整數(shù)n,m,v,分別表示變量個(gè)數(shù)、一元限制個(gè)數(shù)和變量的取值上限。接下來(lái)m行，第j行包含兩個(gè)整數(shù)cj,d;,描述一個(gè)一元限制?！据敵龈袷健枯敵龅轿募ssign.out中。對(duì)于每組測(cè)試數(shù)據(jù)輸出一行，包含一個(gè)整數(shù)，表示方案數(shù)對(duì)10?+7取模的結(jié)果。第5頁(yè)共15頁(yè)912123430【樣例1解釋】·對(duì)于第二組測(cè)試數(shù)據(jù)，只有(x?,T?)=(1,2)一種可能的變量賦值，因此只有【樣例2】該樣例共有10組測(cè)試數(shù)據(jù)，其中第i(1【樣例3】該樣例共有10組測(cè)試數(shù)據(jù)，其中第i(1≤i≤10)組測(cè)試數(shù)據(jù)滿足數(shù)據(jù)范圍中描述【數(shù)據(jù)范圍】·對(duì)于任意的j(1≤j≤m),都有1≤cj≤n,1≤dj≤v。測(cè)試點(diǎn)特殊性質(zhì)662無(wú)39967AB無(wú)特殊性質(zhì)A:保證m=n,且對(duì)于任意的j(1≤j≤m),都有c;=j。特殊性質(zhì)B:保證d;=1。2.假設(shè)當(dāng)前訪問的結(jié)點(diǎn)為u,尋找任意一個(gè)與u相鄰且未標(biāo)記的結(jié)點(diǎn)v,將v作為3.假設(shè)在第2步中，與u相鄰的結(jié)點(diǎn)都已被標(biāo)記，如果u=s則遍歷過程結(jié)束，否則將u設(shè)為遍歷u之前的上一個(gè)結(jié)點(diǎn)并再進(jìn)入第2步。·選取1作為遍歷起始結(jié)點(diǎn)，并把1打上標(biāo)記；·2與1相鄰且未標(biāo)記，將2設(shè)為當(dāng)前訪問結(jié)點(diǎn)，并把2打上標(biāo)記?！?與3相鄰且未標(biāo)記，將3設(shè)為當(dāng)前訪問結(jié)點(diǎn)，并把3打上標(biāo)記。·3所有相鄰的結(jié)點(diǎn)都被標(biāo)記，將當(dāng)前訪問結(jié)點(diǎn)設(shè)為遍歷結(jié)點(diǎn)3之前的結(jié)點(diǎn)2?！?與4相鄰且未標(biāo)記，將4設(shè)為當(dāng)前訪問結(jié)點(diǎn)，并把4打上標(biāo)記?！?所有相鄰的結(jié)點(diǎn)都被標(biāo)記，將當(dāng)前訪問結(jié)點(diǎn)設(shè)為遍歷結(jié)點(diǎn)4之前的結(jié)點(diǎn)2。·2所有相鄰的結(jié)點(diǎn)都被標(biāo)記，將當(dāng)前訪問結(jié)點(diǎn)設(shè)為遍歷結(jié)點(diǎn)2之前的結(jié)點(diǎn)1?！?所有相鄰的結(jié)點(diǎn)都被標(biāo)記，且1是遍歷起始結(jié)點(diǎn)，故遍歷結(jié)束。12434圖1:樣例1中的樹2.假設(shè)當(dāng)前訪問邊為e,尋找任意一條與e相鄰且未標(biāo)記的邊f(xié),將f作為新的當(dāng)3.假設(shè)在第2步中，與e相鄰的邊都已被標(biāo)記，如果e=b則遍歷過程結(jié)束，否則將e設(shè)為遍歷e之前的上一條邊并再進(jìn)入第2步。例如在上面的樹中，一種可能的遍歷過程如下(定義{u,v}表示連接結(jié)點(diǎn)u和v的邊):·選取{1,2}作為遍歷起始邊，并把{1,2}打上標(biāo)記；·{1,2}與{2,3}相鄰且未標(biāo)記，將{2,3}設(shè)為當(dāng)前訪問邊，并把{2,3}打上標(biāo)記。·{2,3}與{2,4}相鄰且未標(biāo)記，將{2,4}設(shè)為當(dāng)前訪問邊，并把{2,4}打上標(biāo)記?！2,4}所有相鄰的邊都被標(biāo)記，將當(dāng)前訪問邊設(shè)為遍歷{2,4}之前的邊{2,3}?！2,3}所有相鄰的邊都被標(biāo)記，將當(dāng)前訪問邊設(shè)為遍歷{2,3}之前的邊{1,2}?！1,2}所有相鄰的邊都被標(biāo)記，且{1,2}是遍歷起始邊，故遍歷結(jié)束。小Q驚奇的發(fā)現(xiàn)，在這個(gè)新的樹的遍歷過程中，如果將每條邊看作一個(gè)新的結(jié)點(diǎn)，將步驟2中的所有新結(jié)點(diǎn)e和f連接一條新邊，就會(huì)生成一棵由n-1個(gè)新結(jié)點(diǎn)和n-2條新邊連接成的新樹。例如上述遍歷過程得到的新樹如下(新的結(jié)點(diǎn)和新邊都用紅色表示):112圖2:一種可能的新樹現(xiàn)在小Q在n-1條邊中選擇了k條關(guān)鍵邊。小Q想知道，以任意一條關(guān)鍵邊作為起始遍歷邊，通過上述遍歷過程能夠生成多少種不同的新樹。這里兩棵樹被認(rèn)為是不同的，當(dāng)且僅當(dāng)至少存在某一對(duì)新的結(jié)點(diǎn)，它們僅在其中一棵樹中連有新邊。由于結(jié)果可能很大，你只需要輸出其對(duì)10?+7取模的結(jié)果即可。第9頁(yè)共15頁(yè)CCF全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽CCFNOIP2024樹的遍歷(traverse)【輸入格式】從文件traverse.in中讀入數(shù)據(jù)。本題有多組測(cè)試數(shù)據(jù)。輸入的第一行包含兩個(gè)整數(shù)c,T,表示測(cè)試點(diǎn)的編號(hào)和測(cè)試數(shù)據(jù)的組數(shù)。在樣例中，c表示該樣例與測(cè)試點(diǎn)c的數(shù)據(jù)范圍相同。接下來(lái)包含T組數(shù)據(jù)，每組數(shù)據(jù)的格式如下：·第一行包含兩個(gè)整數(shù)n,k,表示樹的結(jié)點(diǎn)數(shù)以及小Q選擇的關(guān)鍵邊的數(shù)量?！そ酉聛?lái)一行包含k個(gè)整數(shù)e?,e2,...,ek,表示小Q選擇的關(guān)鍵邊的編號(hào)。保證關(guān)鍵邊的編號(hào)互不相同?！据敵龈袷健枯敵龅轿募raverse.out中。對(duì)于每組測(cè)試數(shù)據(jù)輸出一行，包含一個(gè)整數(shù)，表示結(jié)果對(duì)10?+7取模的結(jié)果。121234561【樣例1輸出】2【樣例1解釋】?jī)煞N可能的新樹如下：·新結(jié)點(diǎn){1,2}和新結(jié)點(diǎn){2,3}連新邊，新結(jié)點(diǎn){2,3}和新結(jié)點(diǎn){2,4}連新邊?！ば陆Y(jié)點(diǎn){1,2}和新結(jié)點(diǎn){2,4}連新邊，新結(jié)點(diǎn){2,4}和新結(jié)點(diǎn){2,3}連新邊。CCF全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽CCFNOIP2024樹的遍歷(traverse)第10頁(yè)共15頁(yè)123456712345671313·新結(jié)點(diǎn){1,2}和{1,3},{1,2}和{2,4},{2,4}和{2,5}之間分別連新邊。該新樹可以選擇{1,2}作為起始遍歷邊得到?！ば陆Y(jié)點(diǎn){1,2}和{1,3},{1,2}和{2,5},{2,5}和{2,4}之間分別連新邊。該新樹可以選擇{1,2}或{2,4}作為起始遍歷邊得到?！ば陆Y(jié)點(diǎn){1,2}和{1,3},{1,2}和{2,4},{1,2}和{2,5}之間分別連新邊。該新樹可以選擇{2,4}作為起始遍歷邊得到?！緲永?】【樣例4】見選手目錄下的traverse/traverse4.in與traverse/traverse4.ans。該組樣例滿足c=7?！緲永?】第11頁(yè)共15頁(yè)【樣例6】【樣例7】見選手目錄下的traverse/traverse7.in【樣例8】【樣例9】見選手目錄下的traverse/traverse9.in【樣例10】見選手目錄下的traverse/traverse10.in【樣例11】見選手目錄下的traverse/traverse11.in【樣例12】見選手目錄下的traverse/traverse12.in【數(shù)據(jù)范圍】第12頁(yè)共15頁(yè)CCF全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽CCFNOIP2024樹的遍歷(traverse)·對(duì)于任意的i(1≤i≤n-1),都有1≤ui,Ui≤n,且構(gòu)成一顆合法的樹?！?duì)于任意的i(1≤i≤k),都有1≤ei<n,且兩兩不同。測(cè)試點(diǎn)nk特殊性質(zhì)無(wú)AB無(wú)·特殊性質(zhì)A:對(duì)于任意的i(1≤i≤n-1),·特殊性質(zhì)B:對(duì)于任意的i(1≤i≤n-1),都有ui=1,vi=i+1?！咎崾尽繑?shù)據(jù)輸入的規(guī)模可能較大，請(qǐng)選手注意輸入讀取方式的效率。CCF全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽CCFNOIP2024樹上查詢(query)第13頁(yè)共15頁(yè)【題目描述】有一天小S和她的朋友小N一起研究一棵包含了n個(gè)結(jié)點(diǎn)的樹。這是一棵有根樹，根結(jié)點(diǎn)編號(hào)為1,每個(gè)結(jié)點(diǎn)u的深度depu定義為u到1的簡(jiǎn)單除此之外，再定義LCA*(1,r)為編號(hào)在[1,r]中所有結(jié)點(diǎn)的最近公共祖先，即1,l+小N對(duì)這棵樹提出了q個(gè)詢問。在每個(gè)詢問中，小N都會(huì)給出三個(gè)參數(shù)1,r,k,表示他想知道[1,r]中任意長(zhǎng)度大于等于k的連續(xù)子區(qū)間的最近公共祖先深度的最大值，即你的任務(wù)是幫助小S來(lái)回答這些詢問?！据斎敫袷健繌奈募uery.in中讀入數(shù)據(jù)。輸入的第一行包含一個(gè)正整數(shù)n,表示樹的結(jié)點(diǎn)數(shù)。接下來(lái)n-1行，每行包含兩個(gè)正整數(shù)u,v,表示存在一條從結(jié)點(diǎn)u到結(jié)點(diǎn)v的邊。第n+1行包含一個(gè)正整數(shù)q,表示詢問的數(shù)量。接下來(lái)q行，每行包含三個(gè)正整數(shù)1.r,k,描述了一次詢問?！据敵龈袷健枯敵龅轿募uer