标签 - 分治

? 解题记录 ? ? BZOJ ? ? cdq分治 ? ? 分治 ? ? Kruscal ?    2018-05-21 18:44:15    480    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    706    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&
? 解题记录 ? ? KD tree ? ? BZOJ ? ? cdq分治 ? ? 分治 ?    2017-07-21 10:06:08    781    0    0
Description 有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),又三个整数表示。现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。Input 第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。 以下N行,每行三个整数si, ci, mi (1 <= si, ci, mi <= K),
? 解题记录 ? ? 洛谷 ? ? cdq分治 ? ? 模板 ? ? 分治 ?    2017-07-18 11:19:52    1227    0    0
题目背景这是一道模版题 可以使用bitset,CDQ分治,K-DTree等方式解决。 题目描述有  个元素,第  个元素有 、、 三个属性,设  表示满足  且  且  的  的数量。 对于 ,求  的数量 输入输出格式输入格式:  第一行两个整数 、,分别表示元素数量和最大属性值。 之后  行,每行三个整数 、、,分别表示三个属性值。   输出格