协会历届acm实习

第一 教学内 第二 OJ上题目的解题报 动态规 数论相 图论相 组合数 博弈 计算几 第三章心得体 韦心得体 参考文 第一章学内喻老师教学内一个图是一个三元组<V(G),E(G),φG>，其中V(G)是一个非空的结点集合，E(G)称为边集，φG是从边集合E(G)到结点无序偶(有序偶）集合上的函数。子图：设图G=<V,E>,如果有图 G‘,其顶点集合为G的顶点集的子集，边集合为G的边集的子集，则称G’为G的子图。路径：从结点出发v0的交替序列 envn称为联结v0到vn回路：v0vnnv0=vnGuvu连通图无向图G是平凡图或G中任意两顶点都是连通的则称G是连通图。有向图G中，略去各有向边的方向后所得无向图G是连通图，则称G为弱连通图；若G中任意两顶点一个可达另一个，则称G为单向连通图；若G中任意两顶点相互可达，则称G邻接矩阵：用一个矩阵顶点之间是否直接有边相连这个二元关系，设图GnV={v1,v2,···，vn},nA(G)=(aij)Gadj，nadj1341340101110001000111010111110缺点不能随机任意两个顶点的关系一定要通过顺序查找链表才能确//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;}}图的问题之为拓扑排序。拓扑排序在实际生活中和算法中都有很大的应没有前驱--入度为零，删除顶点及以它为尾的弧--弧头顶点的1。12VjVjVk(k=1,2Vk度减1，并将入度为0的顶点进栈。最短路问题是指给定一个边带权的图G，求从某个起始点到某个终点e应用：在一个交通网络中求城市之间的最短路径，求互如果图的边所带的权值规定为非负的，固定起始点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，最短路已不存在，结束循环 将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当边带有权值，对于G的任意一个生成树，把属于T的各条边的长度加起来的和成为T的长度，在G的所有生成树中，路径长度最小经典算法：primeKluskalkruskal取所有结点中距离最小的两个结点,看这两个结点的路径是否与已经存在的结点路径构成回路,如果不构成回路,那么这两个结点的路径就是最小生成树的一条路,否的话舍弃这条路,继续找所有结点最小的路直到所有的路都遍历完.将边按权从小到大排序，放到一个队列中（按先进先出顺序取边T=<V，T=<T，E>中；T=<T，E>中的边不形成回路T=<T，E>中；T黄老师教学内动态规划的简介：求解决策过程(decisionprocess)最优化的数学方法，是信息学奥赛的必考算法之一。动态规划的概念及意义多阶段决策过程的最优化问题:含有递推的思想以及各种数学原理（加法多阶段决策过程的最优化问题:含有递推的思想以及各种数学原理（加法 基本思想虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。们具有相同的填表格式。6. 基本模型根据上例分析和动态规划的基本概念，可以得到动态规划的基本模型如下：(1)确定问题的决策对象。(2)对决策过程划分阶段。(3)对各阶段确定状态变量。(4)根据状态变量确定费用函数和目标函数。(5)建立各阶段状态变量的转移过程，确定状态转移方程动态规划适用条件：适用动态规划的问题必须满足最优化原理和无后效性。1）.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2）.无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。3）.子问题的性动态规划将原来具有指数级复杂度的搜索算法改进成龚老师主要给我们讲解了计算几何方面的内容和怎样使用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点拐向左侧后得到(p2p1)叉乘(p1p00则p0p1p2若(p2p1)叉乘(p1p00则p0p1在p1点拐向右侧后得到 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画出图形来检验我们所求的圆是否正确赵老师教学内欧几里得算法（辗转相除法(A,B)=(B,Amodabmodk(amodk)bmod通过计算b的二进制位上的数，并计算amodk，a^2modk……，通过相应的a^bmodklog2(n)

lim(n)nn/Mp=2^p-1(0846个被发现nn N(n

N

(n)

kk

pei1ipii小于n且与n互素的数的个数

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

(n)n1p

i1 i j1',1} j1',1}ornot1',?,- allare1'如果一个数是素数且x21mod当且仅当x1(mod算法：任取k个整数（b1,b2,……bk）

{bdd,

,b2j1d,b2jd}(mod 中任一种，且对于k个整数都成立。判断其为素数，出错率为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考虑下列对应关系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上题目的解题报动态规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想知道载一个区域中最长底滑坡。区域由一个二维数组给 424252012111024-17-16-125-24-23-...-3-2-1更长。事输入的第一行表示区域的行数R和列数C(1R,C100)R行，每行有C个整数，代表高度h，0<=h<=10000。Sample512425201110Sampledp问题，要求最长路径，我们可以用枚举法把每一个点的大路径这就是子问题了，m[i][j]数组代表从i，j点出发能滑雪的最大步数，h[i][j]组原来的高度；dp方程为：usingnamespacestd;intintGetHigh(inti,int{if(m[i][j]!=-1)//m[i][j]的值已经被计算过了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和上一道题非常相似，状态转移方程：1如果第i个元素和第j个相同则Count[5005][5005]太大了刚开始超内存了.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看到该题发现是一个的动态规划，很难解决，到的是求最长上升 ybetter”就是全部的都要比另一所学校好才行，于是我将学校按照某int//num用于保存输入的数据，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有两个:()[()]或者是([])[].而你只要输出其中一转移方程告诉我们了。1.ij个字符匹配时（即为（））2.不匹配时count[i][j]=min{count[i+1][j]+1,count[i][j-1]+1ans[i][j]表示第i到j个元素代码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),要是各个 个村庄推广到多个。状态转移方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; }}数论相Poj1061（韦也没有约定见面的具置。不过青蛙们都是很乐观的，它们觉得只要一直朝一点上，不然是都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求我们把这两只青蛙分别叫做青蛙A和青蛙B0度处为1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是xB的出发点坐标是y。青蛙AmBnL输入只包括一行5个整数x，y，m，n，L，其中x≠y ，0<m、n，0L 输出碰面所需要的跳跃次数，如果不可能碰面则输出一行Sample1234Sampleintint相乘已经超过了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别表示体力、情感和智力出现的时间，d代表给定的时间384Kvoidmain(){int{ printf("Case%d:thenexttriplepeakoccursin%d}}3个质数，通过（n*A1*A2）%A3==1A3A2A11的那个对应的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的时间复杂度是iktai表示从指定点到第i点的最短距离，没循环一次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权用p表示，负权用n表示，然后给你一个正整数N，要你用给定了权重的k位二进制表示，如果不能表示则输Impossiable。否则输出相应的二进制位。一位控制的是奇偶。然后再判断正负，若为负这个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