分类 - 数据结构

? 解题记录 ? ? 洛谷 ? ? 可并堆 ?    2018-05-26 21:41:33    544    0    0
题目描述如题,一开始有N个小根堆,每个堆包含且仅包含一个数。接下来需要支持两种操作: 操作1: 1 x y 将第x个数和第y个数所在的小根堆合并(若第x或第y个数已经被删除或第x和第y个数在用一个堆内,则无视此操作) 操作2: 2 x 输出第x个数所在的堆最小数,并将其删除(若第x个数已经被删除,则输出-1并无视删除操作) 输入输出格式输入格式:   第一行包含两个正整数N、M,分别表示一开始小根堆的个数和接下来操作的个数。 第二行包含N个正整数,其中第i个正整数表示第i个小根堆初始时包含且仅包含的数。 接下来M行每行2个或3个正整数,表示一条操作,格式如下: 操作1 : 1 x y
? 解题记录 ? ? HDU ? ? 线段树分治 ? ? 线性基 ?    2018-05-23 19:33:51    345    0    0
【题目描述】小苗去市场上买了一捆小葱苗,她突然一时兴起,于是她在每颗小葱苗上写上一个数字,然后把小葱叫过来玩游戏。 每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗,并且让小葱从自己手中的小葱苗里选出一些小葱苗使得选出的小葱苗上的数字的异或和最大。 这种小问题对于小葱来说当然不在话下,但是他的身边没有电脑,于是他打电话给同为Oi选手的你,你能帮帮他吗? 你只需要输出最大的异或和即可,若小葱手中没有小葱苗则输出0" data-mce-tabindex="0">00。 【输入】第一行一个正整数n" data-mce-tabindex="0">nn表示总时间;第二行n" dat
? 解题记录 ? ? BZOJ ? ? cdq分治 ? ? 分治 ? ? Kruscal ?    2018-05-21 18:44:15    489    0    0
【题目描述】PS国是一个拥有诸多城市的大国,国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路,在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素,城市之间修建道路需要的花费会随着时间而改变,Louis会不断得到某道路的修建代价改变的消息,他希望每得到一条消息后能立即知道使城市连通的最小花费总和, Louis决定求助于你来完成这个任务。 【输入】文件第一行包含三个整数N,M,Q,分别表示城市的数目,可以修建的道路个数,及收到的消息个数。 接下来M行,第i+1行有三个用空格隔开的整数Xi,Yi,Zi(1≤Xi
? 解题记录 ? ? BZOJ ? ? 并查集 ? ? 分治 ? ? 线段树分治 ?    2018-05-21 18:10:14    712    0    0
【题目描述】神犇有一个n个节点的图。因为神犇是神犇,所以在T时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了,于是他想考考你。   【输入】输入数据的第一行是三个整数n,m,T。 第2行到第m+1行,每行4个整数u,v,start,end。第i+1行的四个整数表示第i条边连接u,v两个点,这条边在start时刻出现,在第end时刻消失。     【输出】输出包含T行。在第i行中,如果第i时间段内这个图是二分图,那么输出“Yes”,否则输出“No”,不含引号。     【输入样例】3 3&
? 解题记录 ? ? 洛谷 ? ? 可并堆 ?    2018-05-21 11:16:54    698    0    0
 【题目描述】烟花表演是最引人注目的节日活动之一。在表演中,所有的烟花必须同时爆炸。为了确保安全,烟花被安置在远离开关的位置上,通过一些导火索与开关相连。导火索的连接方式形成一棵树,烟花是树叶,如[图1]所示。火花从开关出发,沿导火索移动。每当火花抵达一个分叉点时,它会扩散到与之相连的所有导火索,继续燃烧。导火索燃烧的速度是一个固定常数。[图1]展示了六枚烟花{E1,E2...E6 }的连线布局,以及每根导火索的长度。图中还标注了当在时刻 从开关点燃火花时,每一发烟花的爆炸时间。 Hyunmin为烟花表演设计了导火索的连线布局。不幸的是,在他设计的布局中,烟花不一定同时爆炸。我们希
? 解题记录 ? ? 洛谷 ? ? 二分图匹配 ? ? 线段树 ?    2018-05-15 13:19:38    420    1    1
题意翻译滑冰俱乐部初始有 1..n 号码溜冰鞋各 k 双,已知 x 号脚的人可以穿 x..x + d 号码的鞋子。现 在有 m 次操作,每次两个数 r、x,表示 r 号脚的人来了 x 个,x 为负表示离开。对于每次操作, 输出溜冰鞋是否足够。 数据范围: n,k,m\leq5*10^5, k\leq10^9n,k,m≤5∗105,k≤109 题目背景题目描述Byteasar runs a skate club. Its members meet on a regular basis and train together, and they always use the club's
? 解题记录 ? ? 洛谷 ? ? 线段树 ? ? 线段树合并 ?    2018-05-15 07:59:50    462    0    0
题目描述Byteasar the gardener is growing a rare tree called Rotatus Informatikus. It has some interesting features: The tree consists of straight branches, bifurcations and leaves. The trunk stemming from the ground is also a branch. Each branch ends with either a bifurcation or a leaf on its top end. E
? 解题记录 ? ? 洛谷 ? ? 线段树 ? ? 并查集 ?    2018-05-04 19:06:46    401    1    1
题目描述佳佳有一个 n 行 n 列的黑白棋盘,每个格子都有两面,一面白色,一面黑色。佳佳把棋盘平放在桌子上,因此每个格子恰好一面朝上,如下图所示: 我们把每行从上到下编号为 1 , 2 , 3 ,……, n ,各列从左到右编号为 1 , 2 , 3 ,……, n ,则每个格子可以用棋盘坐标 (x, y)表示。在上图中,有 8 个格子黑色朝上,另外 17&n
? 解题记录 ? ? 洛谷 ? ? 线段树 ?    2018-05-04 18:27:03    674    0    0
题目描述维护一个长度为n的序列,一开始都是0,支持以下两种操作:1.U k a 将序列中第k个数修改为a。2.Z c s 在这个序列上,每次选出c个正数,并将它们都减去1,询问能否进行s次操作。每次询问独立,即每次询问不会对序列进行修改。 输入输出格式输入格式:   第一行包含两个正整数n,m(1<=n,m<=1000000),分别表示序列长度和操作次数。接下来m行为m个操作,其中1<=k,c<=n,0<=a<=10^9,1<=s<=10^9。   输出格式:   包含若干行,对于每个Z询问,若可行,输出TAK,否则
? 解题记录 ? ? 洛谷 ? ? LCT ? ? Kruscal ?    2018-04-04 15:01:00    634    0    0
题目描述为了得到书法大家的真传,小 E 同学下定决心去拜访住在魔法森林中的隐 士。魔法森林可以被看成一个包含 n 个节点 m 条边的无向图,节点标号为 1,2,3,…,n,边标号为 1,2,3,…,m。初始时小 E 同学在 1 号节点,隐士则住在 n 号节点。小 E 需要通过这一片魔法森林,才能够拜访到隐士。 魔法森林中居住了一些妖怪。每当有人经过一条边的时候,这条边上的妖怪 就会对其发起攻击。幸运的是,在 1 号节点住着两种守护精灵:A 型守护精灵与 B 型守护精灵。小 E 可以借助它们的力量,达到自己的目的。 只要小 E 带上足够多的守护精灵,妖怪们就不会发起攻击了。具体来说,无 向图中的