協(xié)會歷屆acm實習

第一 教學內(nèi) 第二 OJ上題目的解題報 動態(tài)規(guī) 數(shù)論相 圖論相 組合數(shù) 博弈 計算幾 第三章心得體 韋心得體 參考文 第一章學內(nèi)喻老師教學內(nèi)一個圖是一個三元組<V(G),E(G),φG>，其中V(G)是一個非空的結(jié)點集合，E(G)稱為邊集，φG是從邊集合E(G)到結(jié)點無序偶(有序偶）集合上的函數(shù)。子圖：設(shè)圖G=<V,E>,如果有圖 G‘,其頂點集合為G的頂點集的子集，邊集合為G的邊集的子集，則稱G’為G的子圖。路徑：從結(jié)點出發(fā)v0的交替序列 envn稱為聯(lián)結(jié)v0到vn回路：v0vnnv0=vnGuvu連通圖無向圖G是平凡圖或G中任意兩頂點都是連通的則稱G是連通圖。有向圖G中，略去各有向邊的方向后所得無向圖G是連通圖，則稱G為弱連通圖；若G中任意兩頂點一個可達另一個，則稱G為單向連通圖；若G中任意兩頂點相互可達，則稱G鄰接矩陣：用一個矩陣頂點之間是否直接有邊相連這個二元關(guān)系，設(shè)圖GnV={v1,v2,···，vn},nA(G)=(aij)Gadj，nadj1341340101110001000111010111110缺點不能隨機任意兩個頂點的關(guān)系一定要通過順序查找鏈表才能確//nGsturctEdge{intdest; intvalue; Edge* Edge*edge=newEdge[n];inti,u,v;}Edge*（u,vl=newEdge;ul->link=edge[u].link;edge[u].link=l;}//取頂點i的鄰接表的鏈表元l=edge[i].link;}}圖的問題之為拓撲排序。拓撲排序在實際生活中和算法中都有很大的應(yīng)沒有前驅(qū)--入度為零，刪除頂點及以它為尾的弧--弧頭頂點的1。12VjVjVk(k=1,2Vk度減1，并將入度為0的頂點進棧。最短路問題是指給定一個邊帶權(quán)的圖G，求從某個起始點到某個終點e應(yīng)用：在一個交通網(wǎng)絡(luò)中求城市之間的最短路徑，求互如果圖的邊所帶的權(quán)值規(guī)定為非負的，固定起始點s，要求sDijkstravoidDijkstra(int//DsPint*S=newint[n];int*D=newint[n];int*P=newEdgeDP{D[l->dest]=l-P[l- l=l-}n-1Sfor(inti=0;i<n-{intj,min=-SDw }//如果找不到符合條件的w，最短路已不存在，結(jié)束循環(huán) 將wSD l->destwl->dest,則更新l->dest的D值和它的最短的上一個頂if(D[l->dest]<0||D[w]+l->value<D[l-{D[l-dest]=D[w]+l->value;}l=l-G=<V，E>T=<V，E1>G一部分邊組成的子圖并且TTG當邊帶有權(quán)值，對于G的任意一個生成樹，把屬于T的各條邊的長度加起來的和成為T的長度，在G的所有生成樹中，路徑長度最小經(jīng)典算法：primeKluskalkruskal取所有結(jié)點中距離最小的兩個結(jié)點,看這兩個結(jié)點的路徑是否與已經(jīng)存在的結(jié)點路徑構(gòu)成回路,如果不構(gòu)成回路,那么這兩個結(jié)點的路徑就是最小生成樹的一條路,否的話舍棄這條路,繼續(xù)找所有結(jié)點最小的路直到所有的路都遍歷完.將邊按權(quán)從小到大排序，放到一個隊列中（按先進先出順序取邊T=<V，T=<T，E>中；T=<T，E>中的邊不形成回路T=<T，E>中；T黃老師教學內(nèi)動態(tài)規(guī)劃的簡介：求解決策過程(decisionprocess)最優(yōu)化的數(shù)學方法，是信息學奧賽的必考算法之一。動態(tài)規(guī)劃的概念及意義多階段決策過程的最優(yōu)化問題:含有遞推的思想以及各種數(shù)學原理（加法多階段決策過程的最優(yōu)化問題:含有遞推的思想以及各種數(shù)學原理（加法 基本思想雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時間無關(guān)的靜態(tài)規(guī)劃，只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。們具有相同的填表格式。6. 基本模型根據(jù)上例分析和動態(tài)規(guī)劃的基本概念，可以得到動態(tài)規(guī)劃的基本模型如下：(1)確定問題的決策對象。(2)對決策過程劃分階段。(3)對各階段確定狀態(tài)變量。(4)根據(jù)狀態(tài)變量確定費用函數(shù)和目標函數(shù)。(5)建立各階段狀態(tài)變量的轉(zhuǎn)移過程，確定狀態(tài)轉(zhuǎn)移方程動態(tài)規(guī)劃適用條件：適用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。1）.最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）最優(yōu)化原理可這樣闡述：一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2）.無后效性：將各階段按照一定的次序排列好之后，對于某個給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當前的這個狀態(tài)。換句話說，每個狀態(tài)都是過去歷史的一個完整總結(jié)。這就是無后向性，又稱為無后效性。3）.子問題的性動態(tài)規(guī)劃將原來具有指數(shù)級復(fù)雜度的搜索算法改進成龔老師主要給我們講解了計算幾何方面的內(nèi)容和怎樣使用opencv這個軟件。37509做題。doublemulti(TPointp1,TPointp2,TPoint{//求矢量[p0p1p0p2]//p0return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-0，p0p2p0p10，p0p2p0p1}折線的拐向的判斷（從p0向p1看過去的左邊）若(p2p1)叉乘(p1p00則p0p1在p1點拐向左側(cè)后得到(p2p1)叉乘(p1p00則p0p1p2若(p2p1)叉乘(p1p00則p0p1在p1點拐向右側(cè)后得到 S=ah/ S=absinC/ S=sqrt(p*(p-a)*(p-b)*(p-c)),p=(a+b+c)/ S=abc/R/{returnfabs(t.t[0].x*t.t[1].y+t.t[1].x*t.t[2].y+t.t[2].x*-t.t[1].x*t.t[0].y-t.t[2].x*t.t[1].y-t.t[0].x*t.t[2].y)/}doublepolygonArea(TPolygonp,int{doublearea;intarea=for(i=1;i<area+=(p.p[i-1].x*p.p[i%n].y-p.p[i%n].x*p.p[i-}returnfabs(area)/}{TCircletmp;doublea,b,c,c1,doublexA,yA,xB,yB,xC,yC;a=distance(t.t[0],t.t[1]);b=distance(t.t[1],c=distance(t.t[2],//Sa*b*cR/4;Rtmp.ra*b*ctriangleArea(t4;xA=t.t[0].x;yA=xB=t.t[1].x;yB=xC=t.t[2].x;yC=c1=(xA*xA+yA*yA-xB*xB-yB*yB)/2;c2=(xA*xA+yA*yA-xC*xC-yC*yC)/tmp.centre.x=(c1*(yA-yC)-c2*(yA-yB))/(xA-xB)*(yA-yC)-(xA-xC)*(yA-yB);tmp.centre.y=(c1*(xA-xC)-c2*(xA-xB))/(yA-yB)*(xA-xC)-(yA-yC)*(xA-xB);return}{TCircletmp;doublea,b,c,angleA,angleB,angleC,p,p2,p3,f1,f2;doublexA,yA,xB,yB,xC,yC;a=distance(t.t[0],b=distance(t.t[1],c=distance(t.t[2],S=p*p=(a+b+c)/r=S/P=2*S/(a+b+tmp.r=2*triangleArea(t)/(a+bangleA=acos((b*b+c*c-a*a)/(2*b*c));angleB=acos((a*a+c*c-b*b)/(2*a*c));angleC=acos((a*a+b*b-c*c)/(2*a*b));p=sin(angleA/2);p2=sin(angleB/2);p3=sin(angleC/xA=t.t[0].x;yA=xB=t.t[1].x;yB=xC=t.t[2].x;yC=f1=((tmp.r/p2)*(tmp.r/p2)-(tmp.r/p)*(tmp.r/p)+xA*xA-xB*xB+yA*yA-yB*yB)/2;f2=((tmp.r/p3)*(tmp.r/p3)-(tmp.r/p)*(tmp.r/p)+xA*xA-xC*xC+yA*yA-yC*yC)/2;tmp.centre.x=(f1*(yA-yC)-f2*(yA-yB))((xA-xB)*(yA-yC)-(xA-xC)*(yA-tmp.centre.y=(f1*(xA-xC)-f2*(xA-xB))((yA-yB)*(xA-xC)-(yA-yC)*(xA-return}boolisPointOnSegment(TPointp,TPointp1,TPoint{//判斷p點是否段p1p2//1.pp1p2//2.pp1p2if(multi(p1,p2,p)!=0)returnfalseif((p.x>p1.x&&p.x>p2.x)||(p.x<p1.x&&p.x<p2.x))returnfalse;if((p.y>p1.y&&p.y>p2.y)||(p.y<p1.y&&p.y<p2.y))returnfalse;returntrue;}boolisPointOnSegment(TPointp,TPointp1,TPoint{//判斷p點是否段p1p2//1.pp1p2//2.pp1p2if(multi(p1,p2,p)!=0)returnfalseif((p.x>p1.x&&p.x>p2.x)||(p.x<p1.x&&p.x<p2.x))returnfalse;if((p.y>p1.y&&p.y>p2.y)||(p.y<p1.y&&p.y<p2.y))returnfalse;returntrue;}opencv畫出圖形來檢驗我們所求的圓是否正確趙老師教學內(nèi)歐幾里得算法（輾轉(zhuǎn)相除法(A,B)=(B,Amodabmodk(amodk)bmod通過計算b的二進制位上的數(shù)，并計算amodk，a^2modk……，通過相應(yīng)的a^bmodklog2(n)

lim(n)nn/Mp=2^p-1(0846個被發(fā)現(xiàn)nn N(n

N

(n)

kk

pei1ipii小于n且與n互素的數(shù)的個數(shù)

k 1abmodpa[bmod(p-1)]mod

(n)n1p

i1 i j1',1} j1',1}ornot1',?,- allare1'如果一個數(shù)是素數(shù)且x21mod當且僅當x1(mod算法：任取k個整數(shù)（b1,b2,……bk）

{bdd,

,b2j1d,b2jd}(mod 中任一種，且對于k個整數(shù)都成立。判斷其為素數(shù)，出錯率為1/4k形如ax+by=n的式子（a，b，arith1e2c(cot.allns a

(tI

1 cane

)he(x1a2t/d)2a1t/d 2 1 2

a

a

(a

a

)t/dn=n1n2n3……nk考慮下列對應(yīng)關(guān)系a——（a1,a2,……,ak）ai屬于Zi=1,2,3,……kai=amod則a——（a1,a2,……,ak）有（a+b）modn——((a1+b1)modn1,(a2+b2)modn2,……,(ak+bk)modnk)(ab)modn——(a1b1modn1,……,akbkmodnk)intext(inta,intb,int&x,int&y) intt,d;if(b==0){x=1;y=0;returna;}d=ext(b,a%b,x,y);returnd;}int(intB[],intw[],int{intintd,x,y,a=0,m,n=1;for(i=0;i<k;i++)for{}if(a>0)returna;elsereturn(a+n);}第二章OJ上題目的解題報動態(tài)規(guī)Poj1050（韋Givenatwo-dimensionalarrayofpositiveandnegativeintegers,asub-rectangleisanycontiguoussub-arrayofsize1*1orgreaterlocatedwithinthewholearray.Thesumofarectangleisthesumofalltheelementsinthatrectangle.Inthisproblemthesub-rectanglewiththelargestsumisreferredtoasthe alsub-rectangle.Asanexample, alsub-rectangleofthe0-2-792-6-41-4-180-isinthelowerleft9-4-1andhasasumofTheinputconsistsofanN*Narrayofintegers.TheinputbeginswithasinglepositiveintegerNonalinebyitself,indicatingthesizeofthesquaretwo-dimensionalarray.ThisisfollowedbyN^2integersseparatedbywhitespace(spacesandnewlines).ThesearetheN^2integersofthearray,presentedinrow-majororder.Thatis,allnumbersinthefirstrow,lefttoright,thenallnumbersinthesecondrow,lefttoright,etc.Nmaybeaslargeas100.Thenumbersinthearraywillbeintherange[-127,127].Outputthesumofthealsub-Sample40-2-7092-6-41-41-80-Sampledpdp方程：第i個元素。usingnamespacestd;intmain(){intintn,i,j,k,l,max=0;{ }{ }}}}Michael喜歡滑雪百這并不奇怪，因為滑雪的確很刺激?？墒菫榱双@得速度，降機來載你。Michael想知道載一個區(qū)域中最長底滑坡。區(qū)域由一個二維數(shù)組給 424252012111024-17-16-125-24-23-...-3-2-1更長。事輸入的第一行表示區(qū)域的行數(shù)R和列數(shù)C(1R,C100)R行，每行有C個整數(shù)，代表高度h，0<=h<=10000。Sample512425201110Sampledp問題，要求最長路徑，我們可以用枚舉法把每一個點的大路徑這就是子問題了，m[i][j]數(shù)組代表從i，j點出發(fā)能滑雪的最大步數(shù)，h[i][j]組原來的高度；dp方程為：usingnamespacestd;intintGetHigh(inti,int{if(m[i][j]!=-1)//m[i][j]的值已經(jīng)被計算過了returnm[i][j];{intmax=0;inttemp;{{}}{{}}{{}}{{}}returnm[i][j];}}int{inti,j,max;{}return}Apalindromeisasymmetricalstring,thatis,astringreadidenticallyfromlefttorightaswellasfromrighttoleft.Youaretowriteaprogramwhich,givenastring,determinestheminimalnumberofcharacterstobeinsertedintothestringinordertoobtainapalindrome.Asanexample,byinserting2characters,thestring"Ab3bd"canbetransformedintoapalindrome("dAb3bAd"or"Adb3bdA").However,insertingfewerthan2charactersdoesnotproduceapalindrome.Yourprogramistoreadfromstandardinput.Thefirstlinecontainsoneinteger:thelengthoftheinputstringN,3<=N<=5000.ThesecondlinecontainsonestringwithlengthN.Thestringisformedfromuppercaselettersfrom'A'to'Z',lowercaselettersfrom'a'to'z'anddigitsfrom'0'to'9'.Uppercaseandlowercaselettersaretobeconsidereddistinct.Yourprogramistowritetostandardoutput.Thefirstlinecontainsoneinteger,whichisthedesiredminimalnumber.Sample5Sample2和上一道題非常相似，狀態(tài)轉(zhuǎn)移方程：1如果第i個元素和第j個相同則Count[5005][5005]太大了剛開始超內(nèi)存了.short剛好可以過。不過把時間和intn;chara[5005];void{int{}}

else}void{ }}Atpresent,theuniversityrankingsareverypopular.Theyhelpseniorhighschoolstudentstochooseuniversityforfurtherstudent.Asweknow,auniversityusuallyhasmanydifferentdepartments,suchasdepartmentofcomputerscience,departmentofElectronicEngineering,etc.Someofthemarequitegoodwhencomparingtotheotheruniversities,butothersarenot.So,mostofuniversityrankingsarecomposedofseveralrankinglists,eachlistforonedepartment.Butherecomesaproblemthatsometimesit’shardtodeterminewhichuniversityisbetter,whencomparingtwouniversitieswitheachother.Fortunay,DoctorBobhasadvancedanewconceptnamedabsoluybetter”,withwhichtheproblemabovecanbepartiallysolved.Now,hereisanexampletoexintheconcept“absoluyAssumethattherearethreeuniversities(X,Y,Z)andeveryuniversityhasthreedepartment:CS,EEandFLS.Andtherankingofdifferentdepartmentsareasfollowed:TherankingofCS:X>Y>Z(X>YmeansXhaveabetterCSdepartmentthanY)TherankingofEEL:X>Z>YTherankingofFLS:Obviously,eachdepartmentofuniversityXisbetterthanthatofuniversityY.Thenit’scalledthatXisabsoluybetterthanY.Usingthe“absoluybetter”concept,it espossibletocomparesomepairsoftheuniversities.NowBobhasthecompleterankingofdifferentdepartmentsofmanyuniversities,andhewantstofindkuniversities(U1,…,UK)suchthatUiisabsoluybetterthanUj(foranyi<j).CouldyoulBobtheumvalueofK?<DIVtheof>ThefirstlineoftheinputisapositiveintegerC.CisthenumberoftestcasesThefirstlineofeachtestcaseistwopositiveintegerN,M(0＜N,M≤100),NisthenumberofuniversitiesandMisthenumberofdepartments.AndthenMlinesfollow.Theith(1＜=i＜=M）linecontainsNnumbersUi（1≤i≤N,1≤Ui≤N),indicatingtherankingoftheithdepartment.IfUniversityUiprecedestoUniversityUjinlinek,thenthekthdepartmentofUiisbetterthanthekthdepartmentofUj.TheoutputshouldconsistofClines,onelineforeachtestcase.Eachlineonlycontainsoneinteger-the umvalueofkasdescribedabove.Noredundantspacesareneeded.Sample2SampleOutput看到該題發(fā)現(xiàn)是一個的動態(tài)規(guī)劃，很難解決，到的是求最長上升 ybetter”就是全部的都要比另一所學校好才行，于是我將學校按照某int//num用于保存輸入的數(shù)據(jù)，re[i]0-istruct//ansvoidint}}}}}}}Poj1050TotheMax(周源TimeLimit:1000MS MemoryLimit:10000KTotalSubmissions:21755Accepted:11278Givenatwo-dimensionalarrayofpositiveandnegativeintegers,asub-rectangleisanycontiguoussub-arrayofsize1*1orgreaterlocatedwithinthewholearray.Thesumofarectangleisthesumofalltheelementsinthatrectangle.Inthisproblemthesub-rectanglewiththelargestsumisreferredtoasthealsub-rectangle.Asanexample,thealsub-rectangleofthearray:0-2-792-6-41-4-180-isinthelowerleft9-4-1andhasasumofTheinputconsistsofanN*Narrayofintegers.TheinputbeginswithasinglepositiveintegerNonalinebyitself,indicatingthesizeofthesquaretwo-dimensionalarray.ThisisfollowedbyN^2integersseparatedbywhitespace(spacesandnewlines).ThesearetheN^2integersofthearray,presentedinrow-majororder.Thatis,allnumbersinthefirstrow,lefttoright,thenallnumbersinthesecondrow,lefttoright,etc.Nmaybeaslargeas100.Thenumbersinthearraywillbeintherange[-127,127].Outputthesumofthealsub-Sample40-2-7092-6-41-41-80-Samplen*n（0<n<=100）,請我們找一個子矩陣，使這個子矩陣之和最大。21維的方法，1n0的話1424行一直到4行獨自一行的情況。428Kintmap[105][105],b[105],n;intfind_max(){inti,sum=0,max=0;}return}void{int }{ }}}}poj1141--BracketsSequence（韋TimeLimit: MemoryLimit:TotalSubmissions:12495Accepted:3345SpecialLetusdefinearegularbracketssequenceinthefollowingEmptysequenceisaregularIfSisaregularsequence,then(S)and[S]arebothregularIfAandBareregularsequences,thenABisaregularForexample,allofthefollowingsequencesofcharactersareregularbracketssequences:(),[],(()),([]),()[],()[()]Andallofthefollowingcharactersequencesare(,[,),)(,([)],Somesequenceofcharacters'(',')','[',and']'isgiven.Youaretofindtheshortestpossibleregularbracketssequence,thatcontainsthegivencharactersequenceasasubsequence.Here,astringa1a2...aniscalledasubsequenceofthestringb1b2...bm,ifthereexistsuchindices1=i1<i2<...<in=m,thataj=bijforall1=j=n.Theinputfilecontainsatmost100brackets(characters'(',')','['and']')thataresituatedonasinglelinewithoutanyothercharactersamongthem.Writetotheoutputfileasinglelinethatcontainssomeregularbracketssequencethathastheminimalpossiblelengthandcontainsthegivensequenceasasubsequence.SampleSample題目大意:給你一貫括號序列(只包含小括號和中括號)，讓你找出長度最小的regularbracketssequence包含此子序列.其中的regularbracketssequence定義如regularbrackets如果s是一個regularbracketssequence,那么[s]也是一個regularbracketssequence,(s)regularbracketssequence.如果A,B都是regularbracketssequence,那么AB也是一個regularbrackets例如:()、[]、()[]、([])、([])()[()]regularbracketssequence而[[[(((((則都不是regularbracketssequence。其中以“([)]”為例，包含regularbracketssequence有兩個:()[()]或者是([])[].而你只要輸出其中一轉(zhuǎn)移方程告訴我們了。1.ij個字符匹配時（即為（））2.不匹配時count[i][j]=min{count[i+1][j]+1,count[i][j-1]+1ans[i][j]表示第i到j(luò)個元素代碼usingnamespacestd;stringans[105][105];chara[105];intn,count[105][105];voiddp(){inti,j,k;{}}

{{}{{}}}}int{return0;}poj1160PostOffice(黃屹瀾TimeLimit:1000MSMemoryLimit:TotalSubmissions: Accepted:Thereisastraighthighwaywithvillagesalongsidethehighway.Thehighwayisrepresentedasanintegeraxis,andthepositionofeachvillageisidentifiedwithasingleintegercoordinate.Therearenotwovillagesinthesameposition.Thedistancebetweentwopositionsistheabsolutevalueofthedifferenceoftheirintegercoordinates.Postofficeswillbebuiltinsome,butnotnecessarilyallofthevillages.Avillageandthepostofficeinithavethesameposition.Forbuildingthepostoffices,theirpositionsshouldbechosensothatthetotalsumofalldistancesbetweeneachvillageanditsnearestpostofficeisminimum.Youaretowriteaprogramwhich,giventhepositionsofthevillagesandthenumberofpostoffices,computestheleastpossiblesumofalldistancesbetweeneachvillageanditsnearestpostoffice.Yourprogramistoreadfromstandardinput.Thefirstlinecontainstwointegers:thefirstisthenumberofvillagesV,1<=V<=300,andthesecondisthenumberofpostofficesP,1<=P<=30,P<=V.ThesecondlinecontainsVintegersinincreasingorder.TheseVintegersarethepositionsofthevillages.ForeachpositionXitholdsthat1<=X<=10000.ThefirstlinecontainsoneintegerS,whichisthesumofalldistancesbetweeneachvillageanditsnearestpostoffice.Sample10123679112244Sample9iij個郵局(j<=i),要是各個 個村莊推廣到多個。狀態(tài)轉(zhuǎn)移方voidmain() intn,m,i,j,mid,k;{{} }

{}}}poj1163TheTriangle（黃屹瀾TimeLimit:1000MS MemoryLimit:10000KTotalSubmissions:20992Accepted:121227 (FigureFigure1showsanumbertriangle.Writeaprogramthatcalculatesthehighestsumofnumberspassedonaroutethatstartsatthetopandendssomewhereonthebase.Eachstepcangoeitherdiagonallydowntotheleftordiagonallydowntotheright.Yourprogramistoreadfromstandardinput.ThefirstlinecontainsoneintegerN:thenumberofrowsinthetriangle.ThefollowingNlinesdescribethedataofthetriangle.Thenumberofrowsinthetriangleis>1but<=100.Thenumbersinthetriangle,allintegers,arebetween0and99.Yourprogramistowritetostandardoutput.ThehighestsumiswrittenasanSample573812744526Sampleintway[102][102],n;void{inti,j;}

void{inti,j,max; }}數(shù)論相Poj1061（韋也沒有約定見面的具置。不過青蛙們都是很樂觀的，它們覺得只要一直朝一點上，不然是都不可能碰面的。為了幫助這兩只樂觀的青蛙，你被要求我們把這兩只青蛙分別叫做青蛙A和青蛙B0度處為1米，這樣我們就得到了一條首尾相接的數(shù)軸。設(shè)青蛙A的出發(fā)點坐標是xB的出發(fā)點坐標是y。青蛙AmBnL輸入只包括一行5個整數(shù)x，y，m，n，L，其中x≠y ，0<m、n，0L 輸出碰面所需要的跳躍次數(shù)，如果不可能碰面則輸出一行Sample1234Sampleintint相乘已經(jīng)超過了int的范圍，剛開始想用_int64,aclonglong才通過了。因為longlong不能用math.husingnamespacestd;longlongabs(longlong{if(a>0)returna;elsereturn-a;}int{longlongi,a,b,n,k,t,t1,t2,sign1,sign2,x0,y0,x1,y1,x,y,,z1,z2;{}{return0;}{if(a%b==1)break;}return0;}Somepeoplebelievethattherearethreecyclesina'slifethatstartthedayheorsheisborn.Thesethreecyclesarethephysical,emotional,andinlectualcycles,andtheyhaveperiodsoflengths23,28,and33days,respectively.Thereisonepeakineachperiodofacycle.Atthepeakofacycle,aperformsathisorherbestinthecorrespondingfield(physical,emotionalormental).Forexample,ifitisthementalcurve,thoughtprocesseswillbesharperandconcentrationwillbeeasier.Sincethethreecycleshavedifferentperiods,thepeaksofthethreecyclesgenerallyoccuratdifferenttimes.Wewouldliketodeterminewhenatriplepeakoccurs(thepeaksofallthreecyclesoccurinthesameday)forany.Foreachcycle,youwillbegiventhenumberofdaysfromthebeginningofthecurrentyearatwhichoneofitspeaks(notnecessarilythefirst)occurs.Youwillalsobegivenadateexpressedasthenumberofdaysfromthebeginningofthecurrentyear.Youtaskistodeterminethenumberofdaysfromthegivendatetothenexttriplepeak.Thegivendateisnotcounted.Forexample,ifthegivendateis10andthenexttriplepeakoccursonday12,theansweris2,not3.Ifatriplepeakoccursonthegivendate,youshouldgivethenumberofdaystothenextoccurrenceofatriplepeak.Youwillbegivenanumberofcases.Theinputforeachcaseconsistsofonelineoffourintegersp,e,i,andd.Thevaluesp,e,andiarethenumberofdaysfromthebeginningofthecurrentyearatwhichthephysical,emotional,andinlectualcyclespeak,respectively.Thevaluedisthegivendateandmaybesmallerthananyofp,e,ori.Allvaluesarenon-negativeandatmost365,andyoumayassumethatatriplepeakwilloccurwithin21252daysofthegivendate.Theendofinputisindicatedbyalineinwhichp=e=i=d=-1.Foreachtestcase,printthecasenumberfollowedbyamessageindicatingthenumberofdaystothenexttriplepeak,intheform:Case1:thenexttriplepeakoccursin1234days.Usethepluralform``days''eveniftheansweris1.SampleInput0000005203445628310223203301203-1-1-1-SampleCase1:thenexttriplepeakoccursin21252days.Case2:thenexttriplepeakoccursin21152days.Case3:thenexttriplepeakoccursin19575days.Case4:thenexttriplepeakoccursin16994days.Case5:thenexttriplepeakoccursin8910days.Case6:thenexttriplepeakoccursin10789days.天、28天和33天，讓我們算出三個周期同時達到的時間2328*33*n%23=1n=828對于33算出n=2。a,b,c,d別表示體力、情感和智力出現(xiàn)的時間，d代表給定的時間384Kvoidmain(){int{ printf("Case%d:thenexttriplepeakoccursin%d}}3個質(zhì)數(shù)，通過（n*A1*A2）%A3==1A3A2A11的那個對應(yīng)的N然后通過(N1*A2*A3+N2*A1*A3+N3*A2*A1)%(A1*A2*A3)poj1014–Dividing（韋TimeLimit:1000MS MemoryLimit:10000KTotalSubmissions:31636 Accepted:7740MarshaandBillownacollectionofmarbles.Theywanttosplitthecollectionamongthemselvessothatbothreceiveanequalshareofthemarbles.Thiswouldbeeasyifallthemarbleshadthesamevalue,becausethentheycouldjustsplitthecollectioninhalf.Butunfortunay,someofthemarblesarelarger,ormorebeautifulthanothers.So,MarshaandBillstartbyassigningavalue,anaturalnumberbetweenoneandsix,toeachmarble.Nowtheywanttodividethemarblessothateachofthemgetsthesametotalvalue.Unfortunay,theyrealizethatitmightbeimpossibletodividethemarblesinthisway(evenifthetotalvalueofallmarblesiseven).Forexample,ifthereareonemarbleofvalue1,oneofvalue3andtwoofvalue4,thentheycannotbesplitintosetsofequalvalue.So,theyaskyoutowriteaprogramthatcheckswhetherthereisafairpartitionofthemarbles.Eachlineintheinputfiledescribesonecollectionofmarblestobedivided.Thelinescontainsixnon-negativeintegersn1,...,n6,whereniisthenumberofmarblesofvaluei.So,theexamplefromabovewouldbedescribedbytheinput-line"101200".TheumtotalnumberofmarbleswillbeThelastlineoftheinputfilewillbe"000000";donotprocessthisForeachcollection,output"Collection#k:",wherekisthenumberofthetestcase,andtheneither"Canbedivided."or"Can'tbedivided.".OutputablanklineaftereachtestSample101200100011000000SampleCollectionCan'tbeCollectionCanbe1880kBintmy_find(intstart,intres){intreturn0;{{return1; return1;}if(gogal>sum)return}}return}void inti,num=1,p,k[7];charch; {printf("Collection#%d:\nCan'tbeprintf("Collection#%d:\nCanbeprintf("Collection#%d:\nCan'tbe}}Problemsinvolvingthecomputationofexactvaluesofverylargemagnitudeandprecisionarecommon.Forexample,thecomputationofthenationaldebtisataxingexperienceformanycomputersystems.ThisproblemrequiresthatyouwriteaprogramtocomputetheexactvalueofRnwhereRisarealnumber(0.0<R<99.999)andnisanintegersuchthat0<n<=25.TheinputwillconsistofasetofpairsofvaluesforRandn.TheRvaluewilloccupycolumns1through6,andthenvaluewillbeincolumns8and9.TheoutputwillconsistofonelineforeachlineofinputgivingtheexactvalueofR^n.Leadingzerosshouldbesuppressedintheoutput.Insignificanttrailingzerosmustnotbeprinted.Don'tprintthedecimalpointiftheresultisaninteger.Sample9Sample . 解題思路：這道題是高精度的運算，對于CC++來編寫有一定難度，但用javajava中有大叔這樣一個類，就可以直接編寫C++來編寫就會很麻煩，但我們可以通過模擬手算法來計算這個usingnamespacestd;intmain(){inta[1001],i,j,re,n,b[1010],k,z,s[30],t;charstr[30];{{{}}

{{intc=0;{}}}while(!a[i]&&i>=re)i--;while(!a[j]&&j<re)j++;{}}return}圖論相Stockbrokersareknowntooverreacttorumours.Youhavebeencontractedtodevelopamethodofspreadingdisinformationamongstthestockbrokerstogiveyouremployerthetacticaledgeinthestockmarket.For umeffect,youhavetospreadtherumoursinthefastestpossibleway.Unfortunayforyou,stockbrokersonlytrustinforationcoingfromtheir"Trustedsources"Thismeansyouhavetotakeintoaccountthestructureoftheircontactswhenstartingarumour.Ittakesacertainamountoftimeforaspecificstockbrokertopasstherumourontoeachofhiscolleagues.Yourtaskwillbetowriteaprogramthatlsyouwhichstockbrokertochooseasyourstartingpointfortherumour,aswellasthetimeitwilltakefortherumourtospreadthroughoutthestockbrokercommunity.ThisdurationismeasuredasthetimeneededforthelasttoreceivetheYourprogramwillinputdatafordifferentsetsofstockbrokers.Eachsetstartswithalinewiththenumberofstockbrokers.Followingthisisalineforeachstockbrokerwhichcontainsthenumberofpeoplewhotheyhavecontactwith,whothesepeopleare,andthetimetakenforthemtopassthemessagetoeach .Theformatofeachstockbrokerlineisasfollows:Thelinestartswiththenumberofcontacts(n),followedbynpairsofintegers,onepairforeachcontact.Eachpairlistsfirstanumberreferringtothecontact(e.g.a'1'meansnumberoneintheset),followedbythetimeinminutestakentopassamessagetothat.Therearenospecialpunctuationsymbolsorspacingrules.Eachisnumbered1throughtothenumberofstockbrokers.Thetimetakentopassthemessageonwillbebetween1and10minutes(inclusive),andthenumberofcontactswillrangebetween0andonelessthanthenumberofstockbrokers.Thenumberofstockbrokerswillrangefrom1to100.Theinputisterminatedbyasetofstockbrokerscontaining0(zero)people.Foreachsetofdata,yourprogrammustoutputasinglelinecontainingthewhoresultsinthefastestmessagetransmission,andhowlongbeforethelastwillreceiveanygivenmessageafteryougiveittothis,measuredinintegerItispossiblethatyourprogramwillreceiveanetworkofconnectionsthatexcludessomes,i.e.somepeoplemaybeunreachable.Ifyourprogramdetectssuchabrokennetwork,simplyoutputthemessage"disjoint".NotethatthetimetakentopassthemessagefromAtoBisnotnecessarilythesameasthetimetakentopassitfromBtoA,ifsuchtransmissionispossibleatall.Sample3224352123621222534428505225150Sample33iksta),iksta的時間復(fù)雜度是iktai表示從指定點到第i點的最短距離，沒循環(huán)一次i就更新一次。usingnamespacestd;#defineN#defineMAXvoiddijkstra(intv){intbools[N]={false};{inttemp=MAX;intu=v;{}}}int{{{}if(n==0)break;{{}}{{}}{}{}}return}Inakbit2'scomplementnumber,wherethebitsareindexedfrom0tok-1,theweightofthemostsignificantbit(i.e.,inpositionk-1),is-2^(k-1),andtheweightofabitinanypositioni(0≤i<k-1)is2^i.Forexample,a3bitnumber101is-2^2+0+2^0=-3.Anegativelyweightedbitiscalledanegabit(suchasthemostsignificantbitina2'scomplementnumber),andapositivelyweightedbitiscalledaposibit.AFunnumbersystemisapositionalbinarynumbersystem,whereeachbitcanbeeitheranegabit,oraposibit.Forexampleconsidera3-bitfunnumbersystemFun3,wherebitsinpositions0,and2areposibits,andthebitinposition1isanegabit.(110)Fun3isevaluatedas2^2-2^1+0=3.NowyouaregoingtohavefunwiththeFunnumbersystems!Youaregiventhedescriptionofak-bitFunnumbersystemFunk,andanintegerN(possiblynegative.YoushoulddeterminethekbitsofarepresentationofNinFunk,orreportthatitisnotpossibletorepresentthegivenNinthegivenFunk.Forexample,arepresentationof-1intheFun3numbersystem(definedabove),is011(evaluatedas0-2^1+2^0),andrepresenting6inFun3isThefirstlineoftheinputfilecontainsasingleintegert(1≤t≤10),thenumberoftestcases,followedbytheinputdataforeachtestcase.Eachtestcaseisgiveninthreeconsecutivelines.Inthefirstlinethereisapositiveintegerk(1≤k≤64).Inthesecondlineofatestdatathereisastringoflengthk,composedonlyoflettersn,andp,describingtheFunnumbersystemforthattestdata,whereeachn(p)indicatesthatthebitinthatpositionisanegabit(posibit).ThethirdlineofeachtestdatacontainsanintegerN(-2^63≤N<2^63),thenumbertorepresentedintheFunknumbersystembyyourprogram.Foreachtestdata,youshouldprintonelinecontainingeitherak-bitstringrepresentingthegivennumberNintheFunknumbersystem,orthewordImpossible,whenitisimpossibletorepresentthegivennumber.Sample234Sample權(quán)用p表示，負權(quán)用n表示，然后給你一個正整數(shù)N，要你用給定了權(quán)重的k位二進制表示，如果不能表示則輸Impossiable。否則輸出相應(yīng)的二進制位。一位控制的是奇偶。然后再判斷正負，若為負這個1的意思就是減1所以要再原是用來存放第i384Kvoid intcharlonglongbig;//{{}else{b[i]=0;}}}}}1122--FDNYtotheRescue!．（周源TimeLimit:1000MS MemoryLimit:10000KTotalSubmissions:1180 Accepted:322TheFireDepartmentofNewYork(FDNY)hasalwaysbeenproudoftheirresponsetimetofiresinNewYorkCity,buttheywanttomaketheirresponsetimeevenbetter.Tohelpthemwiththeirresponsetime,theywanttomakesurethatthedispatchersknowtheclosestfirehousetoanyaddressinthecity.YouhavebeenhiredtowritethissoftwareandareentrustedwithmaintainingtheproudtraditionofFDNY.Conceptually,thesoftwarewillbegiventheaddressofthefire,thelocationsofthefirehouses,streetintersections,andthetimeittakestocoverthedistancebetween