多校9-解題報(bào)告

APoorKing

Tag:ReversedBFS

Preprocessingisneededtocalculateanswersforallpositions(states).Beginningwithallcheckmatestates,youshoulddoreversedBreath-FirstSearch(BFS)toupdatevalues.Thestatecanbespecifiedbythreepositions,so64*64*64statesinall.Foreachstate,makeallpossiblenextstatesandcheckifalltheirvalueshadalreadydetermined.Ifso,youcandeterminethevalue(answer)forthisstate.

BestDivision

Tag:DP,Trie,Datastructure

ThisisaDynamicProgramming(DP)problem.Letdp[i]betheanswer(maximumK)forthesubarrayA[1]~A[i].Then,dp[i]=(maxi-L≤j<i,S[i]^S[j]≤Xdp[j])+1(S[i]=A[1]^A[2]^…^A[i]).Now,buildbit(1-0)trietoaddS[i]valuesinorder.Foreachi,indicessuchthatS[i]^S[j]≤Xisdeterminedbygoingdownalongthetrie,consideringX.Maximumvaluesofasubtreecanbestoredinitsroot.Addingorremovingvaluesto/fromthetriecanbedonebysuitabledatastructuresuchasslidingRMQormultiset.

ConvexHull

Tag:Geometry,3Dtransform,Convexhull

Severalgeometricproceduresareneededtosolvethisproblem.First,constructthe3Dconvexhullofgivenpoints.Then,foreachquery,useCGformulastotransformthequeryplanetoXOYplane.Afterthat,youcanfindoutallintersectionpointsbetweentheedgesofconvexhullandXOYplane.Now,answeristheareaof2Dconvexhullofthesepoints.

DifferentSums

Tag:Construction,Math

Forsmalln,it’seasyproblem.

LetS[i]bethesumoffirstinumbers.

Wetakeaprimenumberplargerthann,andanintegerx(0<=x<p),makeS[i]=2*i*p+(i*(i+1)/2*x)%p.Let’sdefiner[i]=(i*(i+1)/2*x)%p.

IfS[i]–S[j]=S[k]–S[l],theni–j=k–lbecause|r[i]-r[j]|<pand|r[k]–r[l]|<p.Also(r[i]–r[j]–r[k]+r[l])mustbedivisiblebyp,thisleadstoi+j=k+l.Itmeansthati=kandj=l.

Thus,thearraythathasthesesubsumssatisfiestheproblemstatement.

Nowwemustmakeallintegersinthearraylessthan3*n+18.

Wecanchoosepasthesmallestprimelargerthann,andselectxthatminimizesmax{S[i]-S[i-1]}.

Forall6<=n<=2000,ifwechoosexoptimally,themaximumvalueofS[i]-S[i-1]islessthan3*n+18.

EasyHomework

Tag:Numbertheory,Baby-stepgiant-stepalgorithm

Asimpleidentityf(n+1)*f(n-1)–f(n)*f(n)=(-1)^nholdsforallintegersn.

Assumethatf(n)=x,f(n-1)=y,thenaquadraticmodularcongruence(A*x+y)*y–x*x=(-1)^nholds.

Thus,thenumberofdifferentpairs(x,y)isO(p)formodulop,sotheperiodmustbeO(p).Alsoforgivenx,thereareatmostfourdifferentyvalues.AllycandidatescanbecalculatedbyShanks-Tonellialgorithm.Now,youpre-calculatesqrt(p)pairsandcheckwhether(x,y)pairappearsusingbaby-stepgiant-stepalgorithm.Bydoingso,theperiodcanbecomputedinO(sqrt(p))stepsandthetotaltimecomplexityisO(sqrt(p)),theproblemcanbesolved.

Flight

Tag:Datastructure,RMQ

Wecaneasilyfindouttheanswerforeachquerycanbeanintegerfrom-1to3.

FirstfindthediameterDofthegiventree.Let’sassumethatitstwoendnodesareUandV.Fromnow,Uistherootofthetree,andthepathfromUtoVwillbemarked.Let’sdenotef(u)asthenearestmarkednodefromu.

MathisFun

Tag:DP,Statecompression,Inclusion-exclusionprinciple

Foreveryintegerg,calculatetheGLLvalueofthesubsetconsistsofmultiplesofginA.ThisisdonebyDP-likeapproach.RepresentLCMsasitsprimefactorizationstate.Usemap(orunordered_map)tohashstates.Whenaddinganumber,updatemapwithoriginalstatesandnewstateswhichisLCMoforiginalstateandanewnumber.Forbranchingandbounding,primesthatdonotappearfurthershouldberemovedtocompre