• 「BZOJ3282」Tree

    「BZOJ3282」Tree

    Description给定N个点以及每个点的权值,要你处理接下来的M个操作。操作有4种。操作从0到3编号。点从1到N编号。0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1:后接两个整数(x,y),代表连接x到y,若x到Y已经联通则无需连接。2:后接两个整数(x,y),代表删除边(x,y),不保证边(x,y)存在。3:后接两个整数(x,y),代表将点X上的权值变...

    22014年9月18日5,783link cut tree
  • 「BZOJ3514」Codechef MARCH14 GERALD07加强版

    「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日7,942主席树,link cut tree
  • 「BZOJ3479」[Usaco2014 Mar] Watering the Fields

    「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,291prim
  • 「BZOJ2599」[IOI2011] Race

    「BZOJ2599」[IOI2011] Race

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

    22014年9月7日8,022点分治
  • 「BZOJ2152」聪聪可可

    「BZOJ2152」聪聪可可

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

    22014年9月7日6,481点分治
  • NOIP2012开车旅行

    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,676树上倍增
  • 「BZOJ3551」[ONTAK2010] Peaks加强版

    「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日8,900kruskal,主席树
  • 「BZOJ2594」[Wc2006] 水管局长数据加强版

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

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

    52014年8月13日8,023kruskal,离线处理,link cut tree
  • NOI2014魔法森林

    NOI2014魔法森林

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

    82014年8月12日24,005kruskal,link cut tree
  • 「BZOJ2631」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,039link cut tree
  • 「BZOJ1576」[Usaco2009 Jan] 安全路经Travel

    「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,584线段树,树链剖分
  • 公路修建

    公路修建

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

    02014年8月2日3,757prim
5 / 9 « 上一页 1 ...3 4 5 6 7 ...9 下一页 »