信息學(xué)-集訓(xùn)隊(duì)作業(yè)

IOI2008中國(guó)國(guó)家集訓(xùn)隊(duì)第二輪作(截止時(shí)間：200853日：明（包括是否已通過(guò)數(shù)據(jù)50個(gè)通過(guò)測(cè)試數(shù)據(jù)的程作為參考的，所以相信大家會(huì)自覺(jué)的做好榜樣大家去年YY和QRQ的表格，另:（同時(shí)也是準(zhǔn)備CTSCreadme.txt。。ACM/ICPC歐洲賽部分題目提交：(提示：由于上次已經(jīng)過(guò)CERC2004~2006，這次沒(méi)有寫(xiě)在里面。如果準(zhǔn)備填寫(xiě)，請(qǐng)NEERCNEERC題目和測(cè)試數(shù)據(jù)、參考程序：給n個(gè)白點(diǎn)和n個(gè)黑要求每個(gè)白點(diǎn)恰好個(gè)黑點(diǎn)恰好連接一個(gè)白點(diǎn)。BuildingforH層樓，每樓是W*L網(wǎng)格的，每格恰好屬于一個(gè)不同國(guó)家都有一對(duì)同層中有公共邊的設(shè)計(jì)的最多不1,000,000Cactus給一個(gè)n個(gè)點(diǎn)的即兩點(diǎn)距離的最大到為u的結(jié)點(diǎn)，u的兒子結(jié)點(diǎn)的為v定義變量len[u]，len[u]’(len[u]>=len[u]’)，表示當(dāng)前從u到DFS樹(shù)中以u(píng)為根的的所有結(jié)點(diǎn)的最短路徑的最大值以及次大（len[u]與len[u]’不能來(lái)自u(píng)的同一個(gè)兒子；ansu、v：low[v]>dfn[u]len[v]+1len[u]與len[u]len[u]’。當(dāng)對(duì)u所有的兒子都遍歷完之后，再?lài)L試當(dāng)整個(gè)圖都遍歷完之后，ans潛水員需要從深度為d的水里順著繩vs的速度作從繩子一條鯊魚(yú)的距離不vd的速度沿著繩子上移或xy軸，平面上的點(diǎn)表示圓的切線非常麻煩，因我可以將x軸vs倍，這樣所有的橢圓都變成了圓，人移動(dòng)的斜率要求變成[-vd/vs,vd/vs]。x2*w出現(xiàn)一次?？梢宰C明這樣一個(gè)定理：若從一個(gè)圓經(jīng)過(guò)次循環(huán)（2*w的圓）可以到達(dá)另一個(gè)圓（無(wú)論f(x)=0，其中示，包含四則運(yùn)算x最多出現(xiàn)一次。保證不會(huì)出現(xiàn)除以0x，使得ax cxFund你有c但沒(méi)有m間和n支供nkkilot數(shù)都過(guò)k，且最后一天結(jié)束時(shí)第i只的一個(gè)lot是si股，且每天持有的lot數(shù)過(guò)ki已知每個(gè)能買(mǎi)一只或賣(mài)一只的一lot，最后最多能剩多少 ki<=k,1萬(wàn)多。開(kāi)始第k個(gè)人手上人隨機(jī)往左或往右pi所有人至少拿過(guò)一后一個(gè)拿到球的人N個(gè)人pl[i,j,0]ij個(gè)人都拿過(guò)球且當(dāng)前i個(gè)人手里，下一個(gè)拿到球且之前沒(méi)拿過(guò)球i-1的概率；pl[i,j,1]ij個(gè)人都拿過(guò)球且當(dāng)前i個(gè)人手里，下一個(gè)拿到球且之前沒(méi)拿過(guò)球j+1的概率；pr[i,j,0與pr[i,j,1]的定義類(lèi)似與pl[i,j,0pl[i,j,1]jd[i,j,0]表示第i到第j個(gè)人都拿過(guò)球下一個(gè)拿到i-1的概率；HanoiHanoi塔問(wèn)題的構(gòu)造解法：把六種移動(dòng)（A,CB）排序后選擇另外不能連續(xù)移動(dòng)n求解Hanoi問(wèn)題的步以都在B也可以都C不妨定義f(n)，表示對(duì)于當(dāng)前的移動(dòng)序列，f(n)=a*f(n-1)+ba、b均為常數(shù)且a>b。因此可以先通過(guò)模擬求出f(2)與f(3)a和b的I18nIn18后的文章，進(jìn)行展詞必須是以前出現(xiàn)Japanese給一個(gè)字的正確寫(xiě)，判斷某個(gè)寫(xiě)法是否正使得后所有筆且任何兩個(gè)端點(diǎn)的相對(duì)位置（向）mi塊不相交的凸多邊都至少得到了它期n<=30,mi<=30定義recx1,x2表示矩形((x1,inf),(x1,-inf),人所選的區(qū)域都是一個(gè)類(lèi)似于recx1,x2的矩形。然后我示第i個(gè)人得到的凸多邊形土地。每一次，通過(guò)S(areairecinf,x2 ，這里inf可S(areai 土地的右邊界。容易證明，ans是滿(mǎn)足條件的。給一個(gè)n個(gè)字符串個(gè)DNA例如{fix,foo,ox}。n<=5000,串長(zhǎng)均不于每一個(gè)結(jié)點(diǎn)計(jì)算出Trie中以它為根的的hashNWERCbn個(gè)配件的種類(lèi)、質(zhì)類(lèi)型的配件各買(mǎi)一且質(zhì)量的最小值盡 n片荷葉，坐標(biāo)為(xi,yi)，上面ni有mi只企鵝能從上鵝在同一片荷葉上點(diǎn)？一只企鵝每次D給出一個(gè)最大面積8*8在房間的開(kāi)一子對(duì)應(yīng)一個(gè)空位或可以到達(dá)周?chē)?個(gè)最多可以到達(dá)多少8*8，所以可以使用基于連通性狀態(tài)2萬(wàn)多個(gè)。當(dāng)前要放的格子只有兩種情況，因此每個(gè)O(Tn2)，T是狀態(tài)總數(shù)，不過(guò)系數(shù)很大。本題還可以通過(guò)構(gòu)造AC（除非寫(xiě)一個(gè)dpcheck），因此如果不是比賽時(shí)， Enemy在一幅左下角坐標(biāo)為(X,Y)且所有點(diǎn)均標(biāo)位置以及敵軍基求出一條離最近的敵軍最遠(yuǎn)前可以先通過(guò)一次多源BFS，求出地圖中每一個(gè)點(diǎn)離它最近的敵軍的距離，不妨設(shè)為dis[x,y]，dis[x,y]離敵軍的最遠(yuǎn)距離就是dis[x’,y’]，最后再通過(guò)一BFS即可求出最短路徑的長(zhǎng)度。算法的時(shí)間復(fù)雜度O(XY)。Flight（3≤M≤30條線段構(gòu)成的折線大陸的最近距離的先二分答案，然后將每一個(gè)簡(jiǎn)單多邊形都擴(kuò)展為由原簡(jiǎn)單多邊形、圓、矩形組成的圖形，那么的任務(wù)就轉(zhuǎn)化為判斷航線是否被擴(kuò)展后的圖形完全覆蓋。對(duì)于航線中的每一條線段，先求出沒(méi)有被擴(kuò)展后的多邊形中的圓與矩形覆蓋的小線段，然后由于如果當(dāng)前的答案是可行的，它只可能被某一個(gè)原簡(jiǎn)單多邊形完。所以只需判斷是否每一條小線段都會(huì)被一個(gè)原簡(jiǎn)單多邊形完即可判斷出當(dāng)前對(duì)于一個(gè)高度為h度小于等于h-d的點(diǎn)就不能到達(dá)一個(gè)比summit。給出中每個(gè)點(diǎn)的高度以summit。分量中的最大高度。不妨假設(shè)當(dāng)前從點(diǎn)v開(kāi)始遍歷，并且它的高度為h’。利用BFS，對(duì)那些還沒(méi)并且它們相互之間的連通性以及最大高度。若當(dāng)前遍歷到一個(gè)之前已經(jīng)遍歷過(guò)的點(diǎn)，不妨設(shè)為u，那u在之前已經(jīng)被某個(gè)高度大于等于h’的點(diǎn)遍歷過(guò)，因此只需找出u所在連通分量的最大高度，并且判斷該高度與h’的關(guān)系，即可知道v是否是給出n條互不相交，形狀為簡(jiǎn)單多邊形理想的情況下從點(diǎn) (100000,0)，最小的海拔上升總高度與不妨設(shè)點(diǎn)(0,0)為點(diǎn)A，點(diǎn)(100000,0)為點(diǎn)B。對(duì)于A、B均在它的里面或者均在它的外面那么總是存在一個(gè)辦法使得從A可以到達(dá)B并AB的x測(cè)試數(shù)據(jù)、參考程序:給出一個(gè)已經(jīng)填完的數(shù)獨(dú)與一個(gè)未填18027090。。未填完得數(shù)獨(dú)能否成為已經(jīng)填完的數(shù)3columnsegment3row個(gè)rowsegment里的row的變換方案以及每個(gè)column STLTicketto給出一個(gè)無(wú)向邊帶n<=30，邊數(shù)出的4對(duì)點(diǎn)要在該動(dòng)態(tài)規(guī)劃解決該問(wèn)題?？梢杂胒[i,st]表示以i為根，給定的8個(gè)點(diǎn)的連通狀況是一個(gè)2進(jìn)的st。轉(zhuǎn)移O(38n+28n3)。Then<=70本書(shū)放到書(shū)厚度不超過(guò)30，高度不超過(guò)300。要層的寬度的最大值*這是一道背包類(lèi)型的動(dòng)態(tài)規(guī)劃題目不妨將n-1本書(shū)放好。定義f[i][L1][L2]表示將第1到第i本書(shū)放好，且第一層書(shū)架的長(zhǎng)度為L(zhǎng)1，第二層書(shū)架的長(zhǎng)度為L(zhǎng)2同時(shí)為了避免后效性，要先將剩下n-1個(gè)人按寬度從大到小排好序之后（W[2..n]）DP。最后的答案就是時(shí)間復(fù)雜度OnTi2。如果本題就這么結(jié)束5f[i][L1][L2]f[i+1][L1][L2]if[i][0][L2]+Wif[i+1][Ti][L2]if[i][L1][0]+Wif[i+1][L1][Ti]if[i][L1][L2]f[i+1][L1+Ti][L2]if[i][L1][L2]f[i+1][L1][L2+Ti]if[i][L1][L2]f[i+1][L1][L2]都是向f[i][≥L1][≥L2]的轉(zhuǎn)移，因此適當(dāng)?shù)捻樞蚩梢宰?．如果sigma(L2..Ti)=sum，那么4．狀態(tài)的定義是f[2100][2100]，但是3個(gè)特點(diǎn)：Ti比較小（Ti<=30）且比較接近，且Wi在 況下，分別解得最大長(zhǎng)度為總長(zhǎng)的和（ 舉的是較小的兩個(gè)，故不超過(guò)和 2Ti30，因?yàn)楦鶕?jù)性質(zhì) 總可以使每個(gè)5PrinterPrime給出許多座連續(xù)的的數(shù)目n<=要求在群山上建一個(gè)長(zhǎng)度L上的[l,r]時(shí)，且結(jié)束位置都在同一條線段上，那么可存在置換F滿(mǎn)足考慮G那么總可以構(gòu)造出一個(gè)同樣長(zhǎng)度的循環(huán)節(jié)F，使得F2=G2nF，F(xiàn)22個(gè)長(zhǎng)nn為奇數(shù)的情況，只需n為偶數(shù)的情況。顯然，如果循環(huán)節(jié)的長(zhǎng)度是偶G中長(zhǎng)度為偶數(shù)的循環(huán)節(jié)的個(gè)數(shù)，如果存在奇NWERC測(cè)試數(shù)據(jù)、參考程序：n<=5在1~10之間。設(shè)能夠組成糖果盒質(zhì)量為k的方案數(shù)k 給出若干件產(chǎn)品及知道其中一小部分于某種材料它在那間產(chǎn)品中使用的百最小和超過(guò)100%或者最大和小于100%則是的，Pesky n(n<=500)個(gè)人的及一些資料，并且給出了要符合多可以選出多少個(gè)malefemale中的人作為二部圖的XYUptheACM/ICPC亞洲賽部分題目提交：(提示：有很多題目無(wú)法提交。這些題目只需要讀題(對(duì)于我已經(jīng)給出題目大意的題目最好也重新讀題以了解細(xì)節(jié))Japan ThereWasOne幾乎就是Joseph問(wèn)題，第mkPrime素?cái)?shù)和前一個(gè)素?cái)?shù)的差（輸入是素?cái)?shù)時(shí)輸出0）N<=1299709（100000個(gè)素?cái)?shù)N1D棋盤(pán)上玩一個(gè)色子（擲幾點(diǎn)就走幾步T輪成功（Goal）的概的格子。N<=100,之前所有六個(gè)頂點(diǎn)的坐都要為整Geometric銳角的一側(cè)駛過(guò)Slim給一個(gè)n結(jié)點(diǎn)的圖，求的值） w*h網(wǎng)格上有一些（最3種）小寫(xiě)字母（鬼別移動(dòng)它們對(duì)應(yīng)的大寫(xiě)以直接廣搜不過(guò)內(nèi)存承受不了界上都是，所以可以把網(wǎng)格開(kāi)少任何一個(gè)2*2子網(wǎng)格至有一個(gè)格。w,h<=16格Bug界MostDistantPointfromthe給一個(gè)凸n找一個(gè)點(diǎn)界盡量遠(yuǎn)原題并不是很枚舉三條邊再判(n2(kn)，k是二分次數(shù)。順便思考的問(wèn)題有點(diǎn)像01年ldfinal的Helicopt3（點(diǎn)或線段，然后判斷，復(fù)雜度(n)。思q的。我現(xiàn)在的想法是使用模擬退火算用模擬退火的條件想法是先進(jìn)行三然后對(duì)n-2個(gè)三角形分別進(jìn)行模間復(fù)雜度就保證不了了想法是隨機(jī)沒(méi)有計(jì)算的必要攤時(shí)間復(fù)雜下降一維TheTeacher’sSideofMath給一個(gè)數(shù)tmanb，求一個(gè)次數(shù)盡量小的多項(xiàng)FF(t)=0，要F數(shù)。本題中ab是不同的素?cái)?shù)，且m,n>1。可以證明最小次數(shù)為mn，最高次項(xiàng)系數(shù)ad=1。輸保證t<=4mn<=20,答案的各項(xiàng)絕對(duì)值不超過(guò)231.JapanHowIWonderWhatYouAre!判斷(0,0,0)-(x,y,z角度為的無(wú)線大圓錐里有多少個(gè) YouAre!判斷一個(gè)簡(jiǎn)單n邊形是否8數(shù)碼問(wèn)題每個(gè)立的滾動(dòng)使得上表面是一個(gè)給定的顏案有多少種方法可以把n寫(xiě)成k個(gè)不同素?cái)?shù)之和？n<=1120,n*m網(wǎng)格有一些，要求把兩個(gè)2和兩個(gè)3分別用折線連起來(lái)，總長(zhǎng)度盡量狀態(tài)壓縮dp好像有點(diǎn)大材小用?？梢院孟襁@題的狀態(tài)dp很簡(jiǎn)單，怎么確定任何一條路徑呢？這個(gè)問(wèn)題比較難以克服已知x，允許乘法和除法，最少通過(guò)幾次運(yùn)算能得到本題的主要思路是迭代加深搜索+剪枝，具體的剪枝有：1、設(shè)當(dāng)前枚舉到的答案為ans’，當(dāng)前的深度為dep，當(dāng)前狀態(tài)中最大2、若當(dāng)前的maxv>2*n，則剪枝3、為了避免重復(fù)搜索，對(duì)于每次的maxv參與否則可以當(dāng)這個(gè)通過(guò)上面的剪枝已經(jīng)可以通過(guò)本給n條線段的長(zhǎng)在網(wǎng)線段最多有36種方法，那么總的放置366×61．第一條線段可以不用枚舉，the上連接成面積最大的多形。相鄰邊可以共線。每線段恰好用一次。且可以規(guī)定方向在某個(gè)象限90o，時(shí)方案數(shù)為9*365×5方案數(shù)為9*364×5使用的角度一定要比上一條邊大，比(-x,-y)小，這樣發(fā)案數(shù)進(jìn)一步縮小到9*184×5如果當(dāng)前到達(dá)距離比剩余的過(guò)和優(yōu)化3有較大，效果按邊長(zhǎng)從大到小排序此時(shí)程序仍然會(huì)TLE，我另外加這時(shí)程序運(yùn)行的速度就相當(dāng)快了 NameforYour給一個(gè)包含n條規(guī)則的上出該文法能接受的長(zhǎng)度恰L的字典序最小串。n<=50,L<=20義狀態(tài)f[i][j][k]表示第i個(gè)轉(zhuǎn)移方法的前（后）j個(gè)字母能表示的長(zhǎng)度為k的處于不可轉(zhuǎn)移的狀態(tài)的最小的字符串長(zhǎng)j的處于不可轉(zhuǎn)移的狀態(tài)的最小的字符串是什么。那么可以通過(guò)f[i][j和s[str[i][j+1來(lái)轉(zhuǎn)移得f[i][str[i][j+1]][]。但是注意這樣的情“A=’’B=’AB’的時(shí)候需要知道s[‘B’][x]，但只有計(jì)算得到了f[2][2][x]后才能得到s[‘B’][x]這情況，也很難理解，復(fù)雜度可以做到當(dāng)作點(diǎn)、轉(zhuǎn)移看成邊做spfanl2這樣復(fù)雜度要多乘一個(gè)spfa的數(shù)，根據(jù)實(shí)踐這個(gè)常數(shù)大概為7~8。者都能通過(guò)測(cè)不過(guò)使用spfa更容易n結(jié)點(diǎn)有向簡(jiǎn)單圖中的簡(jiǎn)單k（結(jié)點(diǎn)不能重復(fù)經(jīng)n<=50,路徑的長(zhǎng)度加上一個(gè)剩余距離的剪枝信息，這個(gè)剩余距離是dis[k][i]，表示從i到終點(diǎn)只通過(guò)k~N的頂點(diǎn)的最短距離，這個(gè)東西可以通過(guò)Floyd預(yù)處理得還是不錯(cuò)的，當(dāng)然這個(gè)k是要在搜索的過(guò)程中，我覺(jué)得我比搞的好一個(gè)的數(shù)據(jù)讓這個(gè)方法TLE也是另外對(duì)于這一類(lèi)問(wèn)題，有一個(gè)多Japan Colored有n（可以旋轉(zhuǎn)anizeYourx條鐵軌y個(gè)中轉(zhuǎn)線路連接。有一輛由n個(gè)車(chē)廂（用小寫(xiě)，目標(biāo)狀態(tài)。x<=4,n<=10本題如果直接從初始狀態(tài)開(kāi)始搜索的話(huà)，搜索量十分巨大，TLE非常嚴(yán)到題目給出了注明了答案不會(huì)6，因此搜索量就可以大大減少。實(shí)現(xiàn)給出房間的寬度r和s個(gè)掛這題由于數(shù)據(jù)規(guī)模較小,因此是一重量wi，使得一個(gè)盡量寬(但道簡(jiǎn)單的搜索題目。首先枚舉能超過(guò)r)的天平，掛著所有的排列順序，然后搜索出所有墜。平的構(gòu)成方案，對(duì)于某一個(gè)方以用線性的時(shí)間遞歸計(jì)算出長(zhǎng)度O(s!*(s-=O((s!)2) 有n段道路，長(zhǎng)度分別為ai?？梢圆粨Q。換輪胎的時(shí)間為b，越慢題目中給出一個(gè)分段函數(shù))間盡量小。Network給出一個(gè)棵n葉子無(wú)權(quán)樹(shù)兩兩給你nm*m的矩陣，同一個(gè)找一個(gè)最短的叫數(shù)的序列由于每個(gè)矩陣被bingo的方式2*m+2種（m個(gè)橫行、m個(gè)豎行、兩個(gè)對(duì)角線，因此i個(gè)矩陣bingo的時(shí)間不晚于第i＋1個(gè)矩陣（一個(gè)矩陣bingo是指該矩陣某一橫行或某一豎以先枚舉出每個(gè)矩陣被bingo的方式，這樣就可以知道有哪些數(shù)要被叫到，接下來(lái)只需要確行或某一對(duì)角線的數(shù)都被叫是否存在某個(gè)叫數(shù)的順序符合矩到。2<=n<=4，3<=m<=4于判斷是否存在某種叫數(shù)順序符合題設(shè)規(guī)則，可以用位壓來(lái)實(shí)現(xiàn)。具體來(lái)說(shuō)，定義d[(state)2]表示對(duì)于當(dāng)前的狀態(tài)state是否合法，state表示有哪些的判斷可以在預(yù)處理中進(jìn)行需要加入一些優(yōu)化。不妨設(shè)S為當(dāng)前所叫數(shù)的集合，ans為當(dāng)前1、若Sans則直接退出2、若從S中刪去某個(gè)元后，依然能使全部矩陣bingo，則直接3、若對(duì)于每一個(gè)矩陣都存在一個(gè)數(shù)v，使得vv屬于S順序符合題設(shè)規(guī)Shy水平移動(dòng)一個(gè)多邊形A，使得它和另一個(gè)多邊形B的距離不小這題和前面的FlightSafety很相像就沒(méi)寫(xiě)代碼講一下思15，至少有一個(gè)頂點(diǎn)到另一個(gè)多邊形的點(diǎn)或邊的距離為（給出的定值，否則可以移動(dòng)到距離為L(zhǎng)且答案不會(huì)變差，除非兩個(gè)多邊形在y軸上的投影距離大于L，這種情況很判斷的時(shí)候可以將某個(gè)多邊邊形的邊邊、圓邊進(jìn)行度是頂點(diǎn)的六次方級(jí)別Japan不錯(cuò)的一套The LoginDice把一些全等的Dice拼成3*3*3上的數(shù)字未知，用0表示，求（9之和即可Colorthe平面圖。最多10個(gè)面 空間里有n個(gè)球有一條平行于z平面的掃描平面從上到下掃離散掃描行于xOz平面它和它在xOy平面內(nèi)旋轉(zhuǎn)90o后的棱柱的交的這個(gè)提煉后容易知道新多面體的因此可以枚舉y方向的棱柱的之相交的部分在yOz截面上的面以該斜面與yOz平面的余弦值就是實(shí)際面當(dāng)然當(dāng)夾角為Japan 網(wǎng)格上有一個(gè)簡(jiǎn)單N和多邊形的相交面積為正的單 你有兩個(gè)房n個(gè)預(yù)定請(qǐng)求(i,j,w)，表示ij租用一個(gè)房間，出價(jià)為w。接受一些請(qǐng)求使得總收益盡量大意時(shí)間有的請(qǐng)求不能占只有兩個(gè)房間也是最小費(fèi)用動(dòng)態(tài)規(guī)劃狀態(tài)的定義是。。同一個(gè)房間。(i<=j)表示兩間房間分別用了i和ji=j時(shí)，要么兩間房間同時(shí)出租，要么只出租一間轉(zhuǎn)移到f[i+1][t]，t情況下是O(n2)。當(dāng)所有轉(zhuǎn)移拓?fù)溆行蚯曳秦?fù)間房間就是找一個(gè)從時(shí)刻0到時(shí)刻使用SPFA實(shí)現(xiàn)的理論代價(jià)為事實(shí)證明求費(fèi)用流的速度大大優(yōu)于動(dòng)態(tài)規(guī)劃，而且易于Monster給平面上n條線段組成一個(gè)迷無(wú)（逃離迷宮4個(gè)距離線段端點(diǎn)放兩個(gè)可以到的點(diǎn)之間連一條邊可以假BFS就是人可以走到的點(diǎn)。最后要判斷哪些點(diǎn)走到就可線段覆蓋的角度然后排個(gè)序判斷覆蓋情況?？倧?fù)雜度為O(n3logn)Bitwise比 Bitwise所有題目都有分析和參考資料，請(qǐng)有的同學(xué)查閱后整理在表格中請(qǐng)?zhí)畋砬跋劝杨}目大意寫(xiě)下來(lái)。1 CoinSafe(100)N*2M（N,要求給它鋪1*2的條橫線和豎線上至少被一條多米諾骨造的基礎(chǔ)是5*66*8的情況（6*6的不能推2 開(kāi)關(guān)動(dòng)一下j個(gè)始開(kāi)關(guān)全是1，要求1過(guò)問(wèn)題的關(guān)鍵在于這題的未知數(shù)有800之大，Gauss-Elimination的瓶頸在于消元過(guò)程，而本題的系數(shù)非0即1，因此可以位壓后，是O(n3)，但是常數(shù)可以減小約30倍3 Delivery(200)一對(duì)邊都有一個(gè)公本題是一個(gè)經(jīng)典問(wèn)題，易知對(duì)于一棵樹(shù)來(lái)說(shuō)，必然存在這樣一個(gè)分拆，因此對(duì)圖中的頂點(diǎn)進(jìn)行拆點(diǎn)，使得每條邊在新樹(shù)中對(duì)應(yīng)一條邊。此時(shí)遞歸地求出樹(shù)的分拆，問(wèn)題就解決了4ADatewithScrooge一個(gè)n*n個(gè)格子都有n個(gè)候使得每個(gè)格子選出構(gòu)造方法比較復(fù)雜，地址marimhtml/dinitz.tm上本題直接采用隨機(jī)調(diào)整的方法就可以取得不錯(cuò)的效果了。5OpeningaStall3t+1pa,bSolution中給出了構(gòu)造方法，比較沒(méi)意思這里就不說(shuō)了6TheSecretofSirRoastMcDuck(100)有一個(gè)k(k<=1600)次多項(xiàng)式q(x)，最高次項(xiàng)系數(shù)=1，已知a[i]q(a[i])modp(1<=i<=k)。求常數(shù)直接套用日差值多項(xiàng)式即可7TheJourneyofBubbaDuck(200)有一 a[i]表示排在i前面的比i大的數(shù)有多少個(gè)。已知a[i]，要求這題實(shí)際上就是一個(gè)貪心放置的過(guò)程，查詢(xún)時(shí)可以使用一個(gè)類(lèi)似于nnng-te的數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行優(yōu)化，不過(guò)注意要寫(xiě)成非遞歸的形式，否則會(huì)超時(shí)。8 給一堆點(diǎn)（<=105像這種算法性非常強(qiáng)的題目，數(shù)據(jù)往往很不過(guò)既然是填表，那么有確定性的方法當(dāng)然應(yīng)該介紹一下。首先找到最低的一A，然后找一條不經(jīng)過(guò)任何其他點(diǎn)的直線（設(shè)為直線1，并將存在某個(gè)角度上只有則記錄每個(gè)角度上最鄰兩條直線上最高的與最低的點(diǎn)的連錄與直線1的交點(diǎn)中與點(diǎn)A距離最近的直線，離點(diǎn)A最近的直線，但是卻經(jīng)過(guò)左邊直線上的第三個(gè)點(diǎn)，那么左邊的點(diǎn)與中間的直線上的下方的點(diǎn)一定距離點(diǎn)A更近9 一個(gè)棋盤(pán)上每個(gè)格操作可以對(duì)于朝上的棋子(x,y（n或者(a,y)，并且b<y,這題的棋盤(pán)和向上的棋子數(shù)（）有15之大，因此輸出每個(gè)向上的棋子的必勝移動(dòng)要做到(1的處理復(fù)雜度。SG函數(shù)值按定義求出來(lái)顯然是不現(xiàn)實(shí)用筆列出一個(gè)小的表格，容易發(fā)現(xiàn)格子(x,y)SG值其實(shí)就是xXORy，這點(diǎn)也容易證明（可以通過(guò)下面的求解過(guò)程證明。因此可以O(shè)(n)的時(shí)間內(nèi)得到當(dāng)前局面SG（設(shè)為sum如果當(dāng)前局面必勝的話(huà)，總共的獲勝方案不超過(guò)n(x,y和(x,b，必然滿(mǎn)足：sumXOR(xXORy)XOR(xXORb=sumXORy。當(dāng)b<y時(shí)方案合法。同理可以求出另一類(lèi)必勝方案(x,y)和(a,y)算法總復(fù)雜度為O(n) 循環(huán)最長(zhǎng)遞增子序列（15000能的最長(zhǎng)遞增子序列。輸入為隨機(jī)數(shù)本題和8有類(lèi)似的地方，由于數(shù)據(jù)是隨機(jī)給出的是一個(gè)O(n1.5logn)的概率算法。二分的方法做一個(gè)S（考慮反證法S必然包含最少一個(gè)鏈尾處的線性表中的元素。然后再用“平衡思想，分情況：若線性表中的元素小于05個(gè)，那么對(duì)于每一個(gè)元素，可以分別將該元素前后斷開(kāi)成鏈做一定包括這個(gè)元素的S，再掃描一次，求得長(zhǎng)度不超過(guò)n的段（列）的S并更新答案。若線性表中的元素大于等于0（設(shè)為m）個(gè)，那么每個(gè)元素出現(xiàn)在答案中的概率就1/05正確解的概率1(m-)/))05，當(dāng)=15000時(shí)，成功的概率只有70%。但是注意到線性表（不是由其他元素推出來(lái)的）不超過(guò)(2n05的Bitwise1A Mary-Jane2 有一些硬幣i個(gè)不用要么至少用bi問(wèn)組成S分錢(qián)少要多少硬幣參考解法太慢……時(shí)間復(fù)雜度可以低一階3Schedulingfor4 5 Vault(200)對(duì)于奇素?cái)?shù)pordp(k)kemodp=1的最小有ordp(k)之和6 n*n01矩1（歐）。同POI的scarefrog7 給一個(gè)長(zhǎng)度為n的小于L的連續(xù)子序有元素總和除以元解時(shí)左端點(diǎn)應(yīng)盡量N<=231L<=n所有元素在[-100,100]間這個(gè)231中可以andm舍棄一些狀態(tài)，但是讀入怎么跳過(guò)呢？這么高深的方法當(dāng)然要趕緊學(xué)習(xí)。誰(shuí)料原來(lái)是題目的數(shù)據(jù)范圍寫(xiě)錯(cuò)了，官方解答的復(fù)雜度是(nlogn的……這還不簡(jiǎn)單……二分答案然后掃用棧來(lái)，查詢(xún)時(shí)使用二分。不過(guò)04年周源里那種O(n)的方法貌似8 使得它們的和恰好為S，且總價(jià)格盡量小。價(jià)格都不超過(guò)9PlayingwiththeDestinyreloaded7.這里是填寫(xiě)了WC后Ural比賽的所有題目USUalContestn架飛機(jī)的初始坐標(biāo)以及它們的速出現(xiàn)兩架飛機(jī)的距d的時(shí)刻以及這兩架飛機(jī)的。d的時(shí)刻，然后利用這兩架飛機(jī)的初始位置以及速度列一個(gè)關(guān)于t的二次方t后再更新答案即可。給出的規(guī)則將它規(guī)給出你下樓梯的速一個(gè)電梯的升降情n層大樓的頂樓到第一層所需的最短時(shí)給出一個(gè)4*4的矩1個(gè)否能在矩陣中找到使得格子上的字母對(duì)于每個(gè)單詞，使用化搜索，分別記錄這16個(gè)格Countryofk種限速標(biāo)志，你要將這N個(gè)標(biāo)志放得駛過(guò)該道路的人O(NlogN)。當(dāng)然這題還可以直接O(NlogN)。Devil's已知X0=0，X1=1，計(jì)Xn的小數(shù)位中有6。X(1)j i是偶數(shù)的時(shí)候。設(shè)hi2，，1j 令A(yù)j(4 ，SjAk，kX21S2 2 3 210a 3 ahlog52i是奇數(shù)的情況。答案為ailog2 給你N(<=50000)這道題多數(shù)人的想法是使用動(dòng)態(tài)規(guī)劃。首先將N個(gè)點(diǎn)按y坐標(biāo)從大到小排序，然后定義L[i]表示端點(diǎn)為i且滿(mǎn)足條件的拐彎次數(shù)最多的折線的拐彎數(shù)，并且該折線與點(diǎn)i相連的點(diǎn)在點(diǎn)i的右邊；R[i]的定義類(lèi)似容使用線，因此時(shí)間復(fù)雜度為O(NlogN)。其實(shí)這題還有一個(gè)很優(yōu)美的解法。將N個(gè)點(diǎn)按yy且左拐與右拐交替已知兩人剛開(kāi)始的格高的人每次減價(jià)UralChampionshipm不妨count(i)1i中有多l(xiāng)ucky如何計(jì)算count(i)。對(duì)于一個(gè)數(shù)m不妨定義n表示它的長(zhǎng)度，那著重小于等于m并且長(zhǎng)度為n的數(shù)里面有多少個(gè)luckynumbernumberdn+1-i，其中i≠n+1-LuckyTicketsd1d2…dn 到 之間b<=1018)有多少luckynumber不妨定義f[i][0]表示前i位等于d1d2…di并且符f[i][1]id1d2…dinluckynumberii<=(n+1)div2，則：i>(n+1)div2，則：若di>dn-i+1f[i][1]=f[i-1][1]*9+f[i-1][0]*(di-若di<=dn-i+1，則f[i][1]=f[i-1][1]*9+f[i-。最終長(zhǎng)度為且小于等于m的luckynumber的個(gè)數(shù)為f[n][0]+f[n][1]。綜合上述就可以在O(n)count(i)。n*m(n,1*2n