算法 - Page 108 - hzwer.com

「JoyOI1459」穿越沙漠
描述Description魔法师小F来到了沙漠，他希望通过沙漠去挑战邪恶的魔法师。这个是一个n*m的矩形沙漠，除了北面和南面，西边和东边都是特别高的大山，小F不会爬山。沙漠中，每个地方都有一个邪恶魔法师召唤的邪恶的生物，每个生物都有自己的属性，“攻击力，防御力，血量”，当然，小F同样也有“攻击力，防御力，血量”这3个属性，而且小F可以召唤其他生物来协助自己作战，被召唤的生物也有“攻击力，防御力，血量”这3个属性。...
02014年3月25日2,703状压动规

「BZOJ2763」[JLOI2011] 飞行路线
DescriptionAlice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务，设这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？Input数据的第一行有三个整...
02014年3月25日5,753spfa
「BZOJ1222」[HNOI2001] 产品加工
Description某加工厂有A、B两台机器，来加工的产品可以由其中任何一台机器完成，或者两台机器共同完成。由于受到机器性能和产品特性的限制，不同的机器加工同一产品所需的时间会不同，若同时由两台机器共同进行加工，所完成任务又会不同。某一天，加工厂接到n个产品加工的任务，每个任务的工作量不尽一样。你的任务就是：已知每个任务在A机器上加工所需的时间t1,B机器上加工所需的时间t2及由两台机器共同加工所需的时间t3，请...
02014年3月24日3,786递推与动规
「BZOJ1606」[Usaco2008 Dec] Hay For Sale 购买干草
Description 约翰遭受了重大的损失：蟑螂吃掉了他所有的干草，留下一群饥饿的牛．他乘着容量为C(1≤C≤50000)个单位的马车，去顿因家买一些干草．顿因有H(1≤H≤5000)包干草，每一包都有它的体积Vi(l≤Vi≤C).约翰只能整包购买，他最多可以运回多少体积的干草呢？Input 第1行输入C和H，之后H行一行输入一个Vi．Output 最多的可买干草体积．SampleInput73//总体积为7,用3个物品来背包265T...
02014年3月24日4,826背包动规
「hdu2222」Keywords Search
ProblemDescriptionInthemoderntime,SearchenginecameintothelifeofeverybodylikeGoogle,Baidu,etc.Wiskeyalsowantstobringthisfeaturetohisimageretrievalsystem.Everyimagehavealongdescription,whenuserstypesomekeywordstofindtheimage,thesystemwillmatchthekeywordswithdescriptionofimageandshowtheimagewhichthemostkeywordsbematched.Tosimplifytheproblem,givingyouadescriptionofimage,andsomekeywords,yousho...
42014年3月24日7,987AC自动机
「BZOJ1030」[JSOI2007] 文本生成器
DescriptionJSOI交给队员ZYX一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章——也就是说，生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章a包含单词b，当且仅当单词b是文章a的子串）。但是，...
42014年3月24日8,916AC自动机
「CODEVS1710」生日蛋糕
题目描述 Description7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri,高度为Hi的圆柱。当i<M时，要求Ri>Ri+1且Hi>Hi+1。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。令Q=Sπ请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使...
02014年3月23日2,905深度搜索
「BZOJ1708」[Usaco2007 Oct] Money奶牛的硬币(货币系统)
Description在创立了她们自己的政权之后，奶牛们决定推广新的货币系统。在强烈的叛逆心理的驱使下，她们准备使用奇怪的面值。在传统的货币系统中，硬币的面值通常是1，5，10，20或25，50，以及100单位的货币，有时为了更方便地交易，会发行面值为2单位的硬币。奶牛们想知道，对于一个给定的货币系统，如果需要正好凑出一定数量的钱，会有多少种不同的方法。比如说，你手上有无限多个面值为{1，2，5，10，...}的硬币，并且打算凑出...
12014年3月23日4,393背包动规
「th04」秋静叶&秋穣子
Description在幻想乡，秋姐妹是掌管秋天的神明，作为红叶之神的姐姐静叶和作为丰收之神的妹妹穰子。如果把红叶和果实联系在一起，自然会想到烤红薯。烤红薯需要很多的叶子，才能把红薯烤得很香，所以秋姐妹决定比比谁能够收集到最多的红叶。静叶将红叶分成了N堆(编号1..N)，并且规定了它们的选取顺序，刚好形成一颗有向树。在游戏过程中，两人从根节点开始，轮流取走红叶，当一个人取走节点i的红叶后，另一个人只能从节点i的儿子...
02014年3月23日3,874树形动规,博弈论
「th04」河城荷取
Description在幻想乡，河城荷取是擅长高科技工业的河童。荷取的得意之作除了光学迷彩外，还有震动整个幻想乡的巨型人形『非想天则』。不过由于人形太过巨大，所以为它充能是一件很麻烦的事。人形一共有N个电能池，编号1..N。其中前L个电能池(即编号为1..L的电能池)连接着外部充能接口，而编号为N的电能池连接着动力炉核心。在N个蓄能池之间有M条单向管道，每条管道有一个激活代价cost和电能传输极限limit。当激活度达到某个...
02014年3月23日4,795最大流
「BZOJ1345」[Baltic2007] 序列问题Sequence
Description对于一个给定的序列a1,…,an，我们对它进行一个操作reduce(i)，该操作将数列中的元素ai和ai+1用一个元素max(ai，ai+1)替代，这样得到一个比原来序列短的新序列。这一操作的代价是max(ai，ai+1)。进行n-1次该操作后，可以得到一个长度为1的序列。我们的任务是计算代价最小的reduce操作步骤，将给定的序列变成长度为1的序列。Input第一行为一个整数n(1<=n<=1,000,000)，表示给定序列的长度。接下来的n行，每行一个...
22014年3月23日4,286单调栈
「CF405C」Unusual Product
LittleChrisisahugefanoflinearalgebra.Thistimehehasbeengivenahomeworkaboutthe unusualsquare ofasquarematrix.The dotproduct oftwointegernumbervectors x and y ofsize n isthesumoftheproductsofthecorrespondingcomponentsofthevectors.The unusualsquare ofan n × n squarematrix A isdefinedasthesumof n dotproducts.The i-thofthemisthedotproductofthe i-throwvectorandthe i-thcolum...
02014年3月23日2,415模拟