数据结构 - Page 19

「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,566线段树,树链剖分

「BZOJ1935」[SHOI2007] Tree 园丁的烦恼
Description很久很久以前，在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者，在他的皇家花园里种植着各种奇花异草。有一天国王漫步在花园里，若有所思，他问一个园丁道：“最近我在思索一个问题，如果我们把花坛摆成六个六角形，那么……”“那么本质上它是一个深度优先搜索，陛下”，园丁深深地向国王鞠了一躬。“嗯……我听说有一种怪物叫九头蛇，它非常贪吃苹果树……”“是的，显然这是一道经典的...
22014年8月6日5,588树状数组,离线处理
「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,737treap,链表
「BZOJ2304」[APIO2011] 寻路path
DescriptionTooDee是一块二维格子状的土地（就像著名的笛卡尔坐标系那样），在这里生活着很多可爱的Dee。Dee是像蜜蜂一样的小动物，它们只在二维活动，而且它们非常的文明开化。TooDee的蜂窝和正常世界的蜂窝也是很不一样的，它们是矩形的且它们的边平行于TooDee的地理坐标系，就是说矩形的边或者是东西走向，或者是南北走向。因为Dees是很高级的生物，它们有很多固定的飞行轨道，这些轨道由一些平行于坐标轴的线段组成，...
02014年8月5日7,084模拟,spfa,dijkstra,线段树
「BZOJ1269」[AHOI2006] 文本编辑器editor
Description这些日子，可可不和卡卡一起玩了，原来可可正废寝忘食的想做一个简单而高效的文本编辑器。你能帮助他吗？为了明确任务目标，可可对“文本编辑器”做了一个抽象的定义：文本：由0个或多个字符构成的序列。这些字符的ASCII码在闭区间[32,126]内，也就是说，这些字符均为可见字符或空格。光标：在一段文本中用于指示位置的标记，可以位于文本的第一个字符之前，文本的最后一个字符之后或文本的某两个相邻字符之...
12014年8月2日6,730STL
「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,282可持久化线段树
「BZOJ1861」[ZJOI2006] Book 书架
Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有X本书，那么放回去时这本...
22014年8月1日5,732splay
「BZOJ3673」可持久化并查集 by zky
Descriptionn个集合m个操作操作：1ab合并a,b所在集合2k回到第k次操作之后的状态(查询算作操作)3ab询问a,b是否属于同一集合，是则输出1否则输出00<n,m<=2*10^4SampleInput561123122031221312SampleOutput101题解这题不知道出题人什么做法，但是代码很短的样子UPD：出题人用的是rope，即stl中的可持久化平衡树KuribohG神犇告诉了我可以用可持久化线段树实现可持久化数组TT 既然都有可持久化数组了，只要用个再...
162014年8月1日25,160可持久化线段树
「POJ3321」Apple Tree
DescriptionThereisanappletreeoutsideofkaka'shouse.Everyautumn,alotofappleswillgrowinthetree.Kakalikesappleverymuch,sohehasbeencarefullynurturingthebigappletree.ThetreehasNforkswhichareconnectedbybranches.Kakanumberstheforksby1toNandtherootisalwaysnumberedby1.Appleswillgrowontheforksandtwoapplewon'tgrowonthesamefork.kakawantstoknowhowmanyapplesarethereinasub-tree,forhisstudyoftheproduceabi...
02014年8月1日6,766dfs序,线段树
NOI2007项链工厂
Description Input输入文件第一行包含两个整数N,c，分别表示项链包含的珠子数目以及颜色数目。第二行包含N个整数，x1,x2…,xn，表示从位置1到位置N的珠子的颜色，1≤xi≤c。第三行包含一个整数Q，表示命令数目。接下来的Q行每行一条命令，如上文所述。Output对于每一个C和CS命令，应输出一个整数代表相应的答案。SampleInput53123214CR2P552CS41SampleOutput41HINT 对于60%的数据，N≤1000，Q≤1000...
02014年7月31日5,489线段树
「BZOJ2733」[HNOI2012] 永无乡
Description永无乡包含n座岛，编号从1到n，每座岛都有自己的独一无二的重要度，按照重要度可以将这n座岛排名，名次用1到n来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛a出发经过若干座（含0座）桥可以到达岛b，则称岛a和岛b是连通的。现在有两种操作：Bxy表示在岛x与岛y之间修建一座新桥。Qxk表示询问当前与岛x连通的所有岛中第k重要的是哪座岛，即所有与岛x连通的岛中重要度排名第k小的岛是哪座...
12014年7月31日8,076线段树
NOI2003Editor
DescriptionInput输入文件editor.in的第一行是指令条数t，以下是需要执行的t个操作。其中：为了使输入文件便于阅读，Insert操作的字符串中可能会插入一些回车符，请忽略掉它们（如果难以理解这句话，可以参考样例）。除了回车符之外，输入文件的所有字符的ASCII码都在闭区间[32,126]内。且行尾没有空格。这里我们有如下假定：MOVE操作不超过50000个，INSERT和DELETE操作的总个数不超过4000，PREV和N...
152014年7月31日4,849STL