hzwer.com - Page 72

「BZOJ2631」tree
Description　一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一：+uvc：将u到v的路径上的点的权值都加上自然数c；-u1v1u2v2：将树中原有的边(u1,v1)删除，加入一条新边(u2,v2)，保证操作完之后仍然是一棵树；*uvc：将u到v的路径上的点的权值都乘上自然数c；/uv：询问u到v的路径上的点的权值和，求出答案对于51061的余数。Input　　第一行两个整数n，q接下来n-1行每行两个正整数u，v，描述这...
112014年8月8日8,085link cut tree

「BZOJ1576」[Usaco2009 Jan] 安全路经Travel
DescriptionInput*第一行:两个空格分开的数,N和M*第2..M+1行:三个空格分开的数a_i,b_i,和t_iOutput*第1..N-1行:第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.SampleInput45122132344321243输入解释:跟题中例子相同SampleOutput336输出解释:跟题中例子相同题解首先用dijkstra得出最短路径树然后我的做法是树链剖分+线段树对于一条不在最...
12014年8月7日6,632线段树,树链剖分
「BZOJ1935」[SHOI2007] Tree 园丁的烦恼
Description很久很久以前，在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者，在他的皇家花园里种植着各种奇花异草。有一天国王漫步在花园里，若有所思，他问一个园丁道：“最近我在思索一个问题，如果我们把花坛摆成六个六角形，那么……”“那么本质上它是一个深度优先搜索，陛下”，园丁深深地向国王鞠了一躬。“嗯……我听说有一种怪物叫九头蛇，它非常贪吃苹果树……”“是的，显然这是一道经典的...
22014年8月6日5,707树状数组,离线处理
「BZOJ2548」[Ctsc2002] 灭鼠行动
Description最近，有一些繁殖力很强的老鼠在下水道非常猖獗，灭鼠特工队正在计划消灭这些老鼠。下水道只有东西方向和南北方向的管道，如图所示。灭鼠特工队的队员拥有强大的武器。他们将在某些时刻t在某些位置(x,y)放置武器。他们所使用的武器包括：强力炸弹：它的攻击范围限定在管道内部，是沿竖直和水平方向，离(x,y)的距离不超过L的区域，但是不能穿透下水道壁。它将在放置之后立刻爆炸，且攻击范围内的老鼠将被全部炸死。神秘...
02014年8月6日4,048模拟
「BZOJ2346」[Baltic 2011] Lamp
Description2255是一个傻X，他连自己家灯不亮了都不知道。某天TZ大神路过他家，发现了这一情况，于是TZ开始行侠仗义了。TZ发现是电路板的问题，他打开了电路板，发现线路根本没有连上！！于是他强大的脑力可以使某个格子上的线路从\变为/，或者从/变为\。2255不会电路（因为他什么都不会），但是他想知道TZ最少要用多少次脑力才能使他家的灯变亮。如果无法变亮，输出“NOSOLUTION”。n,m<=500SampleInput...
02014年8月5日3,507dijkstra
「BZOJ1483」[HNOI2009] 梦幻布丁
DescriptionN个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有3段颜色.Input第一行给出N,M表示布丁的个数和好友的操作次数.第二行N个数A1,A2...An表示第i个布丁的颜色从第三行起有M行,对于每个操作,若第一个数字是1表示要对颜色进行改变，其后的两个整数X,Y表示将所有颜色为X的变为Y，X可能等于Y.若第一个数字为2表示...
12014年8月5日7,864treap,链表
「BZOJ2304」[APIO2011] 寻路path
DescriptionTooDee是一块二维格子状的土地（就像著名的笛卡尔坐标系那样），在这里生活着很多可爱的Dee。Dee是像蜜蜂一样的小动物，它们只在二维活动，而且它们非常的文明开化。TooDee的蜂窝和正常世界的蜂窝也是很不一样的，它们是矩形的且它们的边平行于TooDee的地理坐标系，就是说矩形的边或者是东西走向，或者是南北走向。因为Dees是很高级的生物，它们有很多固定的飞行轨道，这些轨道由一些平行于坐标轴的线段组成，...
02014年8月5日7,260模拟,spfa,dijkstra,线段树
「BZOJ1685」[Usaco2005 Oct] Allowance 津贴
DescriptionAsarewardforrecordmilkproduction,FarmerJohnhasdecidedtostartpayingBessiethecowasmallweeklyallowance.FJhasasetofcoinsinN(1<=N<=20)differentdenominations,whereeachdenominationofcoinevenlydividesthenext-largerdenomination(e.g.,1centcoins,5centcoins,10centcoins,and50centcoins).Usingthegivensetofcoins,hewouldliketopayBessieatleastsomegivenamountofmoneyC(1<=C<=100,000...
12014年8月2日4,051贪心
「BZOJ1269」[AHOI2006] 文本编辑器editor
Description这些日子，可可不和卡卡一起玩了，原来可可正废寝忘食的想做一个简单而高效的文本编辑器。你能帮助他吗？为了明确任务目标，可可对“文本编辑器”做了一个抽象的定义：文本：由0个或多个字符构成的序列。这些字符的ASCII码在闭区间[32,126]内，也就是说，这些字符均为可见字符或空格。光标：在一段文本中用于指示位置的标记，可以位于文本的第一个字符之前，文本的最后一个字符之后或文本的某两个相邻字符之...
12014年8月2日6,926STL
「BZOJ3674」可持久化并查集加强版
DescriptionDescription：自从zkysb出了可持久化并查集后……hzwer:乱写能AC，暴力踩标程KuribohG：我不路径压缩就过了！ndsf：暴力就可以轻松虐！zky:……n个集合m个操作操作：1ab合并a,b所在集合2k回到第k次操作之后的状态(查询算作操作)3ab询问a,b是否属于同一集合，是则输出1否则输出0请注意本题采用强制在线,所给的a,b,k均经过加密,加密方法为x=xxorlastans,lastans的初始值为00<n,m<=2*10^5SampleInput5611231...
132014年8月2日9,358可持久化线段树
「NOIP模拟赛」打地鼠游戏
题目描述：伟大的2320学长特别喜欢打地鼠游戏，这个游戏开始后，会在地板上冒出一些地鼠来，你可以用榔头去敲击这些地鼠，每个地鼠被敲击后，将会增加相应的游戏分值。可是，所有地鼠只会在地上出现一段时间（而且消失后再也不会出现），每个地鼠都在0时刻冒出，但停留的时间可能是不同的，而且每个地鼠被敲击后增加的游戏分值也可能是不同。最近2320学长经常玩这个游戏，以至于敲击每个地鼠只要1秒。他在想如何敲击能使总分最大。...
02014年8月2日4,572贪心
「NOIP模拟赛」果实计数
题目描述：淘淘家有棵奇怪的苹果树，这棵树共有n+1层，标号为0~n。这棵树第0层只有一个节点，为根节点。已知这棵树为b叉树，且保证是一颗满b叉树。如图为一颗满3叉树。现在，该树第n层的每个节点上都结出了一个苹果，淘淘想知道共结了多少苹果。由于数量可能很大，答案要求输出modk后的结果。输入描述：给出第1层的节点数b和层数n和k.输出描述：输出苹果数modk后的结果。样例输入：2109样例输出：7数据范围：30%的数据保证：b<=...
02014年8月2日2,860快速幂