算法 - Page 41 - hzwer.com

「CODEVS1743」反转卡片
题目描述Description「dzy493941464|yywyzdzr原创」小A将N张卡片整齐地排成一排，其中每张卡片上写了1~N的一个整数，每张卡片上的数各不相同。比如下图是N=5的一种情况：34215接下来你需要按小A的要求反转卡片，使得左数第一张卡片上的数字是1。操作方法：令左数第一张卡片上的数是K，如果K=1则停止操作，否则将左数第1~K张卡片反转。第一次(K=3)反转后得到：24315第二次(K=2)反转后得到：42315第三次(K=4)反转后得到：...
22014年12月10日5,609splay

「BZOJ2716 / 2648」SJY摆棋子
Description这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是曼哈顿距离即(|x1-x2|+|y1-y2|)。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。Input第一行两个数NM以后M...
62014年12月10日26,256K-Dtree
「BZOJ2165」大楼
Descriptionxz是一个旅游爱好者，这次他来到了一座新的城市。城市中央有一幢高耸入云的大楼。这幢楼到底有多少层呢？据说和非负整数的个数是一样多的。xz想爬上这座大楼来观赏新城市的全景。这幢大楼的楼层从下至上用从小到大的非负整数编号。每层楼有n个房间，用1到n的正整数编号。楼层之间用电梯连接，电梯只能上行，不能下行或者同层移动。（下楼一般自行解决）电梯用(u,v,w)的形式给出，表示对于任意正整数i，有第i层的房间u到...
42014年12月9日5,289矩阵乘法
「BZOJ2929」[POI1999] 洞穴攀行
Description一队洞穴学者在ByteMountain的GrateCave里组织了一次训练。训练中，每一位洞穴学者要从最高的一个室到达最底下的一个室。他们只能向下走。一条路上每一个连续的室都要比它的前一个低。此外，每一个洞穴学者都要从最高的室出发，沿不同的路走到最低的室。问：可以有多少个人同时参加训练？任务：写一个程序：l 读入对洞穴的描述。l 计算可以同时参加训练的人数。l 将...
132014年12月9日4,396最大流
「BZOJ1027」[JSOI2007] 合金
Description某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。现在，用户给出了n种他们需要的合金，以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料，并且使用这些原材料可以加工出用户需要的所有种类的合金。Input第一行两个...
82014年12月9日6,796floyd,几何
「BZOJ3174」[TJOI2013] 拯救小矮人
Description一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。即：一个小矮人站在另一小矮人的肩膀上，知道最顶端的小矮人伸直胳膊可以碰到陷阱口。对于每一个小矮人，我们知道他从脚到肩膀的高度Ai，并且他的胳膊长度为Bi。陷阱深度为H。如果我们利用矮人1，矮人2，矮人3,。。。矮人k搭一个梯子，满足A1+A2+A3+....+Ak+Bk>=H,那么矮人k就可以离开陷阱逃跑了，一旦一个矮人逃跑了，他就...
02014年12月9日3,914递推与动规
「BZOJ2751」[HAOI2012] 容易题(easy)
Description为了使得大家高兴，小Q特意出个自认为的简单题（easy）来满足大家，这道简单题是描述如下：有一个数列A已知对于所有的A[i]都是1~n的自然数，并且知道对于一些A[i]不能取哪些值，我们定义一个数列的积为该数列所有元素的乘积，要求你求出所有可能的数列的积的和mod1000000007的值，是不是很简单呢？呵呵！Input第一行三个整数n,m,k分别表示数列元素的取值范围，数列元素个数，以及已知的限制条数。接下来k行，每行...
12014年12月9日5,818快速幂
「BZOJ2656」[ZJOI2012] 数列(sequence)
Description小白和小蓝在一起上数学课，下课后老师留了一道作业，求下面这个数列的通项公式：小白作为一个数学爱好者，很快就计算出了这个数列的通项公式。于是，小白告诉小蓝自己已经做出来了，但为了防止小蓝抄作业，小白并不想把公式公布出来。于是小白为了向小蓝证明自己的确做出来了此题以达到其炫耀的目的，想出了一个绝妙的方法：即让小蓝说一个正整数N，小白则说出的值，如果当N很大时小白仍能很快的说出正确答案，这就...
102014年12月9日5,389高精度
「BZOJ2819」Nim
Description著名游戏设计师vfleaking，最近迷上了Nim。普通的Nim游戏为：两个人进行游戏，N堆石子，每回合可以取其中某一堆的任意多个，可以取完，但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。于是vfleaking决定写一个玩Nim游戏的平台来坑玩家。为了设计漂亮一点的初始局面，vfleaking用以下方式来找灵感：拿出很多石子，把它们聚成一堆一堆的，对每一堆编号1,2,3,4,...n,在堆与堆间连边，没有自环与重边，从任意堆...
82014年12月9日7,637dfs序,树状数组,博弈论
「BZOJ3653」谈笑风生
Description设T为一棵有根树，我们做如下的定义：•设a和b为T中的两个不同节点。如果a是b的祖先，那么称“a比b不知道高明到哪里去了”。•设a和b为T中的两个不同节点。如果a与b在树上的距离不超过某个给定常数x，那么称“a与b谈笑风生”。给定一棵n个节点的有根树T，节点的编号为1到n，根节点为1号节点。你需要回答q个询问，询问给定两个整数p和k，问有多少个有序三元组(a;b;c)满足：1.a、b和c为T中三个不同的点，且a为p号节...
02014年12月8日7,364dfs序,线段树
「BZOJ3770」疯狂的限制
Description给定k个限制条件，其中第i个条件用c[i],l[i],r[i]表示：字符c[i]在字符串中的出现次数大等于l[i]，小等于r[i]。若一个字符串满足的限制条件的个数大等于L，小等于R，则称该串为StenisString给定一小写字母串s，求s有多少个子串是SteinsString。Input第一行一个非空的小写字母串s第二行三个整数k,L,R。以下k行，每行1个字符和2个整数表示c[i],l[i],r[i]Output一个整数，表示答案SampleInputelpsycongroo312...
42014年12月8日3,211递推与动规
「BZOJ2802」[POI2012] Warehouse Store
Description有一家专卖一种商品的店，考虑连续的n天。第i天上午会进货Ai件商品，中午的时候会有顾客需要购买Bi件商品，可以选择满足顾客的要求，或是无视掉他。如果要满足顾客的需求，就必须要有足够的库存。问最多能够满足多少个顾客的需求。Input第一行一个正整数n(n<=250,000)。第二行n个整数A1,A2,...An(0<=Ai<=10^9)。第三行n个整数B1,B2,...Bn(0<=Bi<=10^9)。Output第一行一个正整数k，表示最多...
02014年12月7日3,298STL,贪心