算法 - Page 43 - hzwer.com

「vijos1382」寻找主人
Description给定两个项链的表示，判断他们是否可能是一条项链。Input输入文件只有两行，每行一个由0至9组成的字符串，描述一个项链的表示（保证项链的长度是相等的）。Output如果两条项链不可能同构，那么输出’No’，否则的话，第一行输出一个’Yes’，第二行输出该项链的字典序最小的表示。设L=项链长度，对于50%的数据L<=100000；对于100%的数据L<=1000000。题解http://wenku.baidu.com/link?url=Jtn398dsc9nSs...
02014年12月3日3,574字符串,其它

「BZOJ3289」Mato的文件管理
DescriptionMato同学从各路神犇以各种方式（你们懂的）收集了许多资料，这些资料一共有n份，每份有一个大小和一个编号。为了防止他人偷拷，这些资料都是加密过的，只能用Mato自己写的程序才能访问。Mato每天随机选一个区间[l,r]，他今天就看编号在此区间内的这些资料。Mato有一个习惯，他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来，再用他写的排序程序给文件大小排序。排序程序可以在1单位时间内...
42014年12月3日7,416树状数组,莫队算法
「BZOJ4014」[FJOI2014] 病毒防护带
根据点到直线距离公式ans=min(Σ(kxi-yi+b)^2/(k^2+1))这个可以三分套三分算。。。我不会偏导不会证展开->(k^2x^2-2*k*x*y+y^2+2*b*k*x-2*b*y+b^2)/(k^2+1)预处理出Σxi、Σxi、Σyi、Σxi^2、Σyi^2、Σxiyi可以O(1)计算答案[crayon-684ac37e3d9d0931255763/] ...
02014年12月3日3,931三分法
WC2010重建计划
DescriptionInput第一行包含一个正整数N，表示X国的城市个数.第二行包含两个正整数L和U，表示政策要求的第一期重建方案中修建道路数的上下限接下来的N-1行描述重建小组的原有方案，每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi其中城市由1..N进行标号Output输出最大平均估值，保留三位小数SampleInput423121132143SampleOutput2.500HINT20%的数据,N<=500030%的数据,N<=100000,原有方案恰...
22014年12月3日7,890二分法,点分治,单调队列
「BZOJ1145」[CTSC2008] 图腾totem
Description在完成了古越州圆盘密码的研究之后，考古学家小布来到了南美大陆的西部。相传很久以前在这片土地上生活着两个部落，一个部落崇拜闪电，另一个部落崇拜高山，他们分别用闪电和山峰的形状作为各自部落的图腾。小布的团队在山洞里发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。小布认为这幅壁画所包含的信息仅与这N个点的相对位置有关，因此不妨设坐标分别为(1,y...
12014年12月2日6,481树状数组
「BZOJ2428」[HAOI2006] 均分数据
Description已知N个正整数：A1、A2、……、An。今要将它们分成M组，使得各组数据的数值和最平均，即各组的均方差最小。均方差公式如下：,其中σ为均方差，是各组数据和的平均值，xi为第i组数据的数值和。Input第一行是两个整数，表示N,M的值（N是整数个数，M是要分成的组数）第二行有N个整数，表示A1、A2、……、An。整数的范围是1--50。（同一行的整数间用空格分开）Output这一行只包含一个数，表示最小均方差的值...
42014年12月2日5,711其它
致NOIP2014
大概记录一下吧考前听说NOIP面向社会征题难度会比较高，做好了暴力的准备。。。day0看考场，福州高级中学好像发生了点不愉快的事情，比较压抑day1第一题，数据范围逗我么，好吧我好像初中玩过这个加强版锤子剪刀布，不过送分也不要这样吧卧槽表只有一半真是坑第二题这不是傻逼树形dp么。。。写完，暴力，对拍一下。。。（为什么我要对拍）第三题嗯好像100很有难度，让我来先写个70的写完->过样例，才过了一个半小时嗯我先来...
182014年12月2日9,512竞赛历程
「CF492E」Vanya and Field
Vanyadecidedtowalkinthefieldofsizen × ncells.Thefieldcontainsmappletrees,thei-thappletreeisatthecellwithcoordinates(xi, yi).Vanyamovestowardsvector(dx, dy).ThatmeansthatifVanyaisnowatthecell(x, y),theninasecondhewillbeatcell.Thefollowingconditionissatisfiedforthevector:,whereisthelargestintegerthatdividesbothaandb.Vanyaendshispathwhenhereachesthesquarehehasalreadyvisited.Vanyawonders...
02014年12月2日4,008其它
「CF492D」Vanya and Computer Game
VanyaandhisfriendVovaplayacomputergamewheretheyneedtodestroynmonsterstopassalevel.Vanya'scharacterperformsattackwithfrequencyxhitspersecondandVova'scharacterperformsattackwithfrequencyyhitspersecond.Eachcharacterspendsfixedtimetoraiseaweaponandthenhehits(thetimetoraisetheweaponis1 / xsecondsforthefirstcharacterand1 / ysecondsforthesecondone).Thei-thmonsterdiesafterhereceivesaihits.Vanya...
02014年12月2日3,440二分法
「CF492C」Vanya and Exams
Vanyawantstopassnexamsandgettheacademicscholarship.Hewillgetthescholarshipiftheaveragegrademarkforalltheexamsisatleastavg.Theexamgradecannotexceedr.Vanyahaspassedtheexamsandgotgradeaiforthei-thexam.Toincreasethegradeforthei-thexamby1point,Vanyamustwritebiessays.Hecanraisetheexamgrademultipletimes.WhatistheminimumnumberofessaysthatVanyaneedstowritetogetscholarship?InputThefirstlinecontai...
22014年12月2日3,528贪心
「CF492B」Vanya and Lanterns
Vanyawalkslateatnightalongastraightstreetoflengthl,litbynlanterns.Considerthecoordinatesystemwiththebeginningofthestreetcorrespondingtothepoint0,anditsendcorrespondingtothepointl.Thenthei-thlanternisatthepointai.Thelanternlightsallpointsofthestreetthatareatthedistanceofatmostdfromit,wheredissomepositivenumber,commonforalllanterns.Vanyawonders:whatistheminimumlightradiusdshouldthelanternshavet...
02014年12月2日2,199模拟
「CF492A」Vanya and Cubes
Vanyagotncubes.Hedecidedtobuildapyramidfromthem.Vanyawantstobuildthepyramidasfollows:thetoplevelofthepyramidmustconsistof1cube,thesecondlevelmustconsistof1 + 2 = 3cubes,thethirdlevelmusthave1 + 2 + 3 = 6cubes,andsoon.Thus,thei-thlevelofthepyramidmusthave1 + 2 + ... + (i - 1) + icubes.Vanyawantstoknowwhatisthemaximumheightofthepyramidthathecanmakeusingthegivencubes.InputT...
02014年12月2日2,586模拟