題目名稱排水系統(tǒng)字符串匹配移球游戲微信步數題目類型傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型目錄可執(zhí)行文件名輸入文件名ball.inwalk.in輸出文件名walk.out每個測試點時限1.0秒1.0秒1.0秒1.0秒內存限制子任務數目測試點是否等分是是是是提交源程序文件名對于C++語言water.cppwalk.cppwater.cball.cwalk.c對于Pascal語言編譯選項對于C++語言對于C語言對于Pascal語言1.文件名(程序名和輸入輸出文件名)必須使用英文小寫。2.C/C++中函數main()的返回值類型必須是int,程序正常結束時的返回值必須是0。5.若無特殊說明，結果的比較方式為全文比較(過濾行末空格及文末回車)。6.程序可使用的棧內存空間限制與題目的內存限制一致。CCF全國青少年信息學奧林匹克聯賽正式賽內存32GB。上述時限以此配置為準。8.只提供Linux格式附加樣例文件。9.評測在當前最新公布的NOILinux下進行，各語言的編譯器版本以其為準。第3頁共13頁【題目描述】對于一個城市來說，排水系統(tǒng)是極其重要的一個部分。有一天，小C拿到了某座城市排水系統(tǒng)的設計圖。排水系統(tǒng)由n個排水結點(它們從1～n編號)和若干個單向排水管道構成。每一個排水結點有若干個管道用于匯集其他排水結點的污水(簡稱為該結點的匯集管道),也有若干個管道向其他的排水結點排出污水(簡稱為該結點的排出管道)。排水系統(tǒng)的結點中有m個污水接收口，它們的編號分別為1,2,…,m,污水只能從這些接收口流入排水系統(tǒng)，并且這些結點沒有匯集管道。排水系統(tǒng)中還有若干個最終排水口，它們將污水運送到污水處理廠，沒有排出管道的結點便可視為一個最終排水口?，F在各個污水接收口分別都接收了1噸污水，污水進入每個結點后，會均等地從當前結點的每一個排出管道流向其他排水結點，而最終排水口將把污水排出系統(tǒng)。現在小C想知道，在該城市的排水系統(tǒng)中，每個最終排水口會排出多少污水。該城市的排水系統(tǒng)設計科學，管道不會形成回路，即不會發(fā)生污水形成環(huán)流的情況?！据斎敫袷健繌奈募ater.in中讀入數據。第一個兩個用單個空格分隔的整數n,m。分別表示排水結點數與接收口數量。接下來n行，第i行用于描述結點i的所有排出管道。其中每行第一個整數d表示其排出管道的數量，接下來d;個用單個空格分隔的整數a?,a?,…,a依次表示管道的目標排水結點。保證不會出現兩條起始結點與目標結點均相同的管道?！据敵龈袷健枯敵龅轿募ater.out中。輸出若干行，按照編號從小到大的順序，給出每個最終排水口排出的污水體積。其中體積使用分數形式進行輸出，即每行輸出兩個用單個空格分隔的整數p,q,表示排出的污水體積為。要求p與q互素，q=1時也需要輸出q。【樣例1輸入】第4頁共13頁5600【樣例1輸出】121號結點是接收口，4、5號結點沒有排出管道，因此是最終排水口。1噸污水流入1號結點后，均等地流向2、3、5號結點，三個結點各流入噸污水。2號結點流入的噸污水將均等地流向4、5號結點，兩結點各流入噸污水。3號結點流入的噸污水將均等地流向4、5號結點，兩結點各流入噸污水。最終，4號結點排出噸污水，5號結點排出噸污水?！緲永?】見選手目錄下的water/water2.in與【樣例3】見選手目錄下的water/water3.in與測試點編號1對于所有測試點，保證1≤n≤10?,1≤m≤10,0≤d≤5。數據保證，污水在從一個接收口流向一個最終排水口的過程中，不會經過超過10個中間排水結點(即接收口和最終排水口不算在內)。第5頁共13頁【題目描述】小C學習完了字符串匹配的相關內容，現在他正在做一道習題。S=ABC,S=ABABC,S=ABAB…ABC,其中A,B,C均是非空字符串，且A中出現奇數次的字符數量不超過C中出現奇數次的字符數量。更具體地，我們可以定義AB表示兩個字符串A,B相連接，例如A=aab,B=ab,并遞歸地定義A1=A,A”=A”-1A(n≥2且為正整數)。例如A=abb,則則小C的習題是求S=(AB)'C的方案數，其中F(A)≤F(C),F(S)表示字符串S中出現奇數次的字符的數量。兩種方案不同當且僅當拆分出的A、B、C中有至少一個字符串不同。小C并不會做這道題，只好向你求助，請你幫幫他。【輸入格式】從文件string.in中讀入數據。本題有多組數據，輸入文件第一行一個正整數T表示數據組數。每組數據僅一行一個字符串S,意義見題目描述。S僅由英文小寫字母構成?！据敵龈袷健枯敵龅轿募tring.out中。對于每組數據輸出一行一個整數表示答案。【樣例1輸入】【樣例1輸出】第6頁共13頁21321389【樣例1解釋】123512345【樣例2輸入】5【樣例2輸出】見選手目錄下的string/string3.in與string/string3.ans。見選手目錄下的string/string4.in與string/string4.ans。【數據范圍】測試點編號特殊性質無無對于所有測試點，保證1≤T≤5,1≤|SI≤220。第8頁共13頁【題目描述】初始時一根柱子上的球可能是五顏六色的，而小C的任務是將所有同種顏色的球移到同一根柱子上，這是唯一的目標，而每種顏色的球最后放置在哪根柱子則沒有小C可以通過若干次操作完成這個目標，一次操作能將一個球從一根柱子移到另一根柱子上。更具體地，將x號柱子上的球移動到y(tǒng)號柱子上的要求為：1.x號柱子上至少有一個球；小C的目標并不難完成，因此他決定給自己加加難度：在完成目標的基礎上，使用的操作次數不能超過820000。換句話說，小C需要使用至多820000次操作完成目標。小C被難住了，但他相信難不倒你，請你給出一個操作方案完成小C的目標。合法的方案可能有多種，你只需要給出任意一種，題目保證一定存在一個合法方案?！据斎敫袷健繌奈募all.in中讀入數據。第一行兩個用空格分隔的整數n,m。分別表示球的顏色數、每種顏色球的個數。接下來n行每行m個用單個空格分隔的整數，第i行的整數按自底向上的順序依次給出了i號柱子上的球的顏色?！据敵龈袷健枯敵龅轿募all.out中。本題采用自定義校驗器(specialjudge)評測。你的輸出的第一行應該僅包含單個整數k,表示你的方案的操作次數。你應保證接下來k行每行你應輸出兩個用單個空格分隔的正整數x,y,表示這次操作將x號柱子最上方的球移動到y(tǒng)號柱子最上方。你應保證1≤x,y≤n+1且x≠y?！緲永?輸入】第9頁共13頁11234567【樣例1輸出】6柱子中的內容為：按自底向上的順序依次給出柱子上每個球的顏色?！緲永?解釋】操作1號柱子3號柱子初始2222【樣例2】見選手目錄下的ball/ball2.in與【樣例3】見選手目錄下的ball/ball3.in與第10頁共13頁【數據范圍】操作1號柱子3號柱子初始2222對于所有測試點，保證2≤n≤50,2≤m≤400?！拘ｒ炂鳌繛榱朔奖氵x手測試，在ball目錄下我們下發(fā)了checker.cpp文件，選手可以編譯該程序，并使用它校驗自己的輸出文件。但請注意它與最終評測時所使用的校驗器并不完全一致。你也不需要關心其代碼的具體內容。編譯命令為：g++checker.cpp-ochecker。checker的使用方式為：checker<iuputfile><outputfile>,參數依次表示輸入文件與你的輸出文件。若你輸出的數字大小范圍不合法，則校驗器會給出相應提示。若你的輸出數字大小范圍正確，但方案錯誤，則校驗器會給出簡要的錯誤信息：1.Ax,表示進行到第x個操作時不合法。2.Bx,表示操作執(zhí)行完畢后第x個柱子上的球不合法。若你的方案正確，校驗器會給出OK。第11頁共13頁【題目描述】小C喜歡跑步，并且非常喜歡在微信步數排行榜上刷榜，為此他制定了一個刷微信步數的計劃。他來到了一處空曠的場地，處于該場地中的人可以用k維整數坐標(a?,a?,…,ak)來表示其位置。場地有大小限制，第i維的大小為w;,因此處于場地中的人其坐標應滿足1≤ai≤w;(1≤i≤k)。小C打算在接下來的P=w?×W?×…×w天中，每天從場地中一個新的位置出發(fā)，開始他的刷步數計劃(話句話說，他將會從場地中每個位置都出發(fā)一次進行計劃)。他的計劃非常簡單，每天按照事先規(guī)定好的路線行進，每天的路線由n步移動構成，每一步可以用c與d表示：若他當前位于(a?,a?,…,ac,…,ak),則這一步他將會走到(a?,a?,…,ag+d,…,ak),其中1≤ci≤k,d?∈{-1,1}。小C將會不斷重復這個路線，直到他走出了場地的范圍才結束一天的計劃。(即走完第n步后，若小C還在場內，他將回到第1步從頭再走一遍)。小C對自己的速度非常有自信，所以他并不在意具體耗費的時間，他只想知道P天之后，他一共刷出了多少步微信步數。請你幫他算一算?！据斎敫袷健繌奈募alk.in中讀入數據。第一行兩個用單個空格分隔的整數n,k。分別表示路線步數與場地維數。接下來一行k個用單個空格分隔的整數w;,表示場地大小。接下來n行每行兩個用單個空格分隔的整數c,d,依次表示每一步的方向，具體意義見題目描述?！据敵龈袷健枯敵龅轿募alk.out中。僅一行一個整數表示答案。答案可能很大，你只需要輸出其對10?+7取模后的值。若小C的計劃會使得他在某一天在場地中永遠走不出來，則輸出一行一個整數-1?！緲永?輸入】12341234第12頁共13頁【樣例1輸出】【樣例1解釋】從(1,1)出發(fā)將走2步，從(1,2)出發(fā)將走4步，從(1,3)出發(fā)將走4步。從(2,1)出發(fā)將走2步，從(2,2)出發(fā)將走3步，從(2,3)出發(fā)將走3步。從(3,1)出發(fā)將走