算法 - Page 57 - hzwer.com

「CF477C」Dreamoon and Strings
Dreamoonhasastringsandapatternstringp.Hefirstremovesexactlyxcharactersfromsobtainingstrings'asaresult.Thenhecalculatesthatisdefinedasthemaximalnumberofnon-overlappingsubstringsequaltopthatcanbefoundins'.Hewantstomakethisnumberasbigaspossible.Moreformally,let'sdefineasmaximumvalueofoveralls'thatcanbeobtainedbyremovingexactlyxcharactersfroms.Dreamoonwantstoknowforallxfrom0to|s|where|s|denotest...
02014年10月13日5,198递推与动规

「CF477B」Dreamoon and Sets
Dreamoonlikestoplaywithsets,integersand.isdefinedasthelargestpositiveintegerthatdividesbothaandb.LetSbeasetofexactlyfourdistinctintegersgreaterthan0.DefineStobeofrankkifandonlyifforallpairsofdistinctelementssi,sjfromS,.Givenkandn,Dreamoonwantstomakeupnsetsofrankkusingintegersfrom1tomsuchthatnointegerisusedintwodifferentsets(ofcourseyoucanleavesomeintegerswithoutuse).Calculatetheminimummth...
02014年10月13日4,454构造
「CF477A」Dreamoon and Sums
Dreamoonlovessummingupsomethingfornoreason.Onedayheobtainstwointegersaandboccasionally.Hewantstocalculatethesumofallniceintegers.Positiveintegerxiscalledniceifand,wherekissomeintegernumberinrange[1, a].Bywedenotethequotientofintegerdivisionofxandy.Bywedenotetheremainderofintegerdivisionofxandy.Youcanreadmoreabouttheseoperationshere:http://goo.gl/AcsXhT.Theanswermaybelarge,sopleaseprint...
02014年10月13日2,743其它
「BZOJ1119」[POI2009] SLO
Description对于一个1-N的排列(ai)，每次你可以交换两个数ax与ay(x<>y)，代价为W(ax)+W(ay)若干次交换的代价为每次交换的代价之和。请问将(ai)变为(bi)所需的最小代价是多少。Input第一行N。第二行N个数表示wi。第三行N个数表示ai。第四行N个数表示bi。2<=n<=1000000100<=wi<=65001<=ai,bi<=nai各不相等，bi各不相等(ai)<>(bi)样例中依次交换数字(2,5)(3,4)(1,5)Output一个数，最小代价。...
02014年10月12日3,795置换
「BZOJ1131」[POI2008] Sta
Description给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大Input给出一个数字N,代表有N个点.N<=1000000下面N-1条边.Output输出你所找到的点,如果具有多个解,请输出编号最小的那个.SampleInput814564567682434SampleOutput7题解发现从根从某个位置移到它的一个子树得出ans只要O1的时间那么树形dp即可[crayon-687624d94bca1512735255/] ...
02014年10月11日3,650树形动规
「BZOJ1132」[POI2008] Tro
Description平面上有N个点.求出所有以这N个点为顶点的三角形的面积和N<=3000Input第一行给出数字N,N在[3,3000]下面N行给出N个点的坐标,其值在[0,10000]Output保留一位小数,误差不超过0.1SampleInput50012021011SampleOutput7.0题解叉积求面积：abs（xi*yj-yi*xj）所以去掉绝对值，把xi和xj提出来就可以求和了每次把最左边的点当成原点，然后剩下的极角排序，接着枚举第二个点，求叉积之和……坐标都是整数，用lon...
02014年10月11日4,247几何
「BZOJ1106」[POI2007] 立方体大作战tet
Description一个叫做立方体大作战的游戏风靡整个Byteotia。这个游戏的规则是相当复杂的，所以我们只介绍他的简单规则：给定玩家一个有2n个元素的栈，元素一个叠一个地放置。这些元素拥有n个不同的编号，每个编号正好有两个元素。玩家每次可以交换两个相邻的元素。如果在交换之后，两个相邻的元素编号相同，则将他们都从栈中移除，所有在他们上面的元素都会掉落下来并且可以导致连锁反应。玩家的目标是用最少的步数将方块全部消除...
02014年10月11日3,537树状数组
「BZOJ1108」[POI2007] 天然气管道Gaz
DescriptionMary试图控制成都的天然气市场。专家已经标示出了最好的天然气井和中转站在成都的地图。现在需要将中转站和天然气井连接起来。每个中转站必须被连接到正好一个钻油井，反之亦然。Mary特别指名，建设的天然气管道必须从某个天然气井开始，向南或者向东建设。Mary想知道怎么连接每个天然气井和中转站，使得需要的天然气管道的总长度最小。Input输入文件的第一行为一个正整数n(2<=n<=50000)，表示天然气井的数量...
02014年10月10日3,428其它
「BZOJ1023」[SHOI2008] cactus仙人掌图
Description如果某个无向连通图的任意一条边至多只出现在一条简单回路（simplecycle）里，我们就称这张图为仙人图（cactus）。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。举例来说，上面的第一个例子是一张仙人图，而第二个不是——注意到它有三条简单回路：（4，3，2，1，6，5，4）、（7，8，9，10，2，3，7）以及（4，3，7，8，9，10，2，1，6，5，4），而（2，3）同时出现在前两个的简单回路里。另外，第三张图也...
22014年10月10日11,038递推与动规,单调队列,仙人掌
「BZOJ1072」[SCOI2007] 排列perm
Description给一个数字串s和正整数d,统计s有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能被2整除，其中末位为2的有30种，末位为4的有60种。Input输入第一行是一个整数T，表示测试数据的个数，以下每行一组s和d，中间用空格隔开。s保证只包含数字0,1,2,3,4,5,6,7,8,9.Output每个数据仅一行，表示能被d整除的排列的个数。SampleInput7000100111234567890112343421234712345171234567829SampleOutput13...
02014年10月10日5,600状压动规
「BZOJ2324」[ZJOI2011] 营救皮卡丘
Description皮卡丘被火箭队用邪恶的计谋抢走了！这三个坏家伙还给小智留下了赤果果的挑衅！为了皮卡丘，也为了正义，小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。火箭队一共有N个据点，据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发，营救被困在N号据点的皮卡丘。为了方便起见，我们将真新镇视为0号据点，一开始K个人都在0号点。由于火箭队的重重布防，要想摧毁K号据点，必须按照顺序先摧...
02014年10月9日8,075费用流,floyd
「BZOJ1833」[ZJOI2010] count 数字计数
Description给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。Input输入文件中仅包含一行两个整数a、b，含义如上所述。Output输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。SampleInput199SampleOutput9202020202020202020HINT30%的数据中，a<=b<=10^6；100%的数据中，a<=b<=10^12。题解裸的数位dp大概只有我这种逗比不会做递推出f[i][j][k]表示长度为i开头...
02014年10月9日8,514数位动规