hzwer.com _ Home | https://hzwer.com

« 上一页下一页 »Current position : 首页 >> 树 >> 第5页

• 「BZOJ3282」Tree

  

  Description给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变...
  22014年9月18日6,054link cut tree

• 「BZOJ3514」Codechef MARCH14 GERALD07加强版

  

  DescriptionN个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。Input第一行四个整数N、M、K、type，代表点数、边数、询问数以及询问是否加密。接下来M行，代表图中的每条边。接下来K行，每行两个整数L、R代表一组询问。对于type=0的测试点，读入的L和R即为询问的L、R；对于type=1的测试点，每组询问的L、R应为Lxorlastans和Rxorlastans。Output K行每行一个整数代表该组询问的联通块...
  32014年9月11日8,262主席树,link cut tree

• 「BZOJ3479」[Usaco2014 Mar] Watering the Fields

  

  Description Duetoalackofrain,FarmerJohnwantstobuildanirrigationsystemtosendwaterbetweenhisNfields(1<=N<=2000).Eachfieldiisdescribedbyadistinctpoint(xi,yi)inthe2Dplane,with0<=xi,yi<=1000.ThecostofbuildingawaterpipebetweentwofieldsiandjisequaltothesquaredEuclideandistancebetweenthem:(xi-xj)^2+(yi-yj)^2FJwouldliketobuildaminimum-costsystemofpipessothatallofhisfieldsarelinkedt...
  02014年9月7日3,507prim

• 「BZOJ2599」[IOI2011] Race

  

  Description给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.Input第一行两个整数n,k第二..n行每行三个整数表示一条无向边的两端和权值(注意点的编号从0开始)Output一个整数表示最小边数量如果不存在这样的路径输出-1SampleInput43011122134SampleOutput2题解这题有点怪的点分治。。。我的做法也比较逗，就是开一个100W的数组t,t[i]表示权值为i的路径最少边数找到重心分成若干子树后，得出一棵子树的所有点到...
  22014年9月7日8,365点分治

• 「BZOJ2152」聪聪可可

  

  Description聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下...
  22014年9月7日6,748点分治

• NOIP2012开车旅行

  

  描述小A和小B决定利用假期外出旅行，他们将想去的城市从1到N编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市i的海拔高度为Hi，城市i和城市j之间的距离d[i,j]恰好是这两个城市海拔高度之差的绝对值，即d[i,j]=|Hi-Hj|。旅行过程中，小A和小B轮流开车，第一天小A开车，之后每天轮换一次。他们计划选择一个城市S作为起点，一直向东行驶，并且最多行驶X公里就结束旅行。小A和小B的...
  22014年8月31日7,897树上倍增

• 「BZOJ3551」[ONTAK2010] Peaks加强版

  

  Description「题目描述」同3545Input第一行三个数N，M，Q。第二行N个数，第i个数为h_i接下来M行，每行3个数abc，表示从a到b有一条困难值为c的双向路径。接下来Q行，每行三个数vxk，表示一组询问。v=vxorlastans，x=xxorlastans，k=kxorlastans。如果lastans=-1则不变。Output同3545HINT「数据范围」同3545题解本题强制在线。。。据出题人的做法。。。就是做最小生成树，但合并两结点x，y的时新建结点ext，把ext连向fa...
  22014年8月30日9,409kruskal,主席树

• 「BZOJ2594」[Wc2006] 水管局长数据加强版

  

  DescriptionSC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。在...
  52014年8月13日8,414kruskal,离线处理,link cut tree

• NOI2014魔法森林

  

  Description为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在号节点住着两种守护精灵：A型守护精灵与B型守护精灵。...
  82014年8月12日25,362kruskal,link cut tree

• 「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,385link 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,915线段树,树链剖分

• 公路修建

  

  http://218.5.5.242:9018/JudgeOnline/problem.php?id=1443题目描述     某国有n个城市，它们互相之间没有公路相通，因此交通十分不便。为解决这一“行路难”的问题，政府决定修建公路。修建公路的任务由各城市共同完成。修建工程分若干轮完成。在每一轮中，每个城市选择一个与它最近的城市，申请修建通往该城市的公路。政府负责审批这些申请以决定是否同意修建。政府审批的规则如下：（1）如果两个或以上城市申请修建同一条...
  02014年8月2日3,915prim