分类 - 数据结构

? 解题记录 ? ? BZOJ ? ? 动态规划 ? ? 组合数 ?    2018-09-25 08:31:27    808    0    0
Description在Byteland一共有n个城市,编号依次为1到n,它们之间计划修建n(n-1)/2条单向道路,对于任意两个不同的点i和 j,在它们之间有且仅有一条单向道路,方向要么是i到j,要么是j到i。换句话说,这是一个n个点的竞赛图。Byte asar居住在1号城市,他希望从1号城市出发,沿着单向道路不重复地访问一些城市,使得访问的城市数尽可能多。 请写一个程序,帮助Byteasar计算有多少种道路修建方式,使得从1号点出发的最长简单路径经过点数恰好为k,由 于答案可能很大,请对P取模输出 Input第一行包含两个正整数n,P,表示点数和模数。 2≤P≤1e9,N<=200
? 解题记录 ? ? BZOJ ? ? 并查集 ? ? 线段树 ? ? Kruscal ?    2018-09-25 08:06:17    338    0    0
Description在Byteland一共有n个城市,编号依次为1到n,它们之间计划修建m条双向道路,其中修建第i条道路的费用为ci。B yteasar作为Byteland公路建设项目的总工程师,他决定选定一个区间[l,r],仅使用编号在该区间内的道路。他希 望选择一些道路去修建,使得连通块的个数尽量少,同时,他不喜欢修建多余的道路,因此每个连通块都可以看成 一棵树的结构。为了选出最佳的区间, Byteasar会不断选择 q个区间,请写一个程序,帮助 Byteasar计算每个区 间内修建公路的最小总费用。  Input第一行包含三个正整数n; m; q,表示城市数、道路数和询问数
? 解题记录 ? ? Codeforces ? ? 贪心 ? ? 构造 ?    2018-09-18 10:45:43    441    0    0
You are given a tube which is reflective inside represented as two non-coinciding, but parallel to Ox" data-mce-tabindex="0">OxOx lines. Each line has some special integer points — positions of sensors on sides of the tube. You are going to emit a laser ray in the tube. To do so, y
【题目描述】给定一棵n个点的有根树,编号依次为1到n,其中1号点是根节点。每个节点都被染上了某一种颜色,其中第i个节点的颜色为c[i]。如果c[i]=c[j],那么我们认为点i和点j拥有相同的颜色。定义depth[i]为i节点与根节点的距离,为了方便起见,你可以认为树上相邻的两个点之间的距离为1。站在这棵色彩斑斓的树前面,你将面临m个问题。 每个问题包含两个整数x和d,表示询问x子树里且depth不超过depth[x]+d的所有点中出现了多少种本质不同的颜色。请写一个程序,快速回答这些询问。 【输入】第一行包含一个正整数T(1<=T<=500),表示测试数据的组数。 每组数据中,第
? 解题记录 ? ? Atcoder ? ? 堆 ? ? 贪心 ? ? 并查集 ?    2018-07-15 10:47:36    1100    0    0
Problem StatementSnuke has a rooted tree with N vertices, numbered 1 through N. Vertex 1 is the root of the tree, and the parent of Vertex i ( 2≤i≤N ) is Vertex Pi ( Pi<i ). There is a number, 0 or 1, writte
? 解题记录 ? ? 杂OJ ? ? cdq分治 ?    2018-07-13 23:28:09    805    0    0
【题目描述】给定一个有n个元素的序列,元素编号为1~n,每个元素有三个属性a,b,c,求序列中满足i<j且ai<aj且bi<bj且ci<cj的数对(i,j)的个数。 【输入格式】第一行一个整数n,表示序列长度。 第二行n个整数,分别表示a1~an。 第三行n个整数,分别表示b1~bn。 第四行n个整数,分别表示c1~cn。 【输出格式】一个整数,表示答案。 【样例输入】5 1 5 3 4 2 2 5 3 4 1 1 2 5 3 4【样例输出】3【样例解释】满足条件的(i,j)共有以下三对: (1,2) (1,3) (1,4) 【数据范围与约定】对于30%的数据,n<
? 解题记录 ? ? Atcoder ? ? 线段树 ?    2018-07-13 22:38:40    802    0    0
Problem StatementWe have a sequence A of length N. On this sequence, we can perform the following two kinds of operations: Swap two adjacent elements. Select one element, and increment it by 1. We will repeatedly perform these operations so that A will be a non-decreasi
? 解题记录 ? ? Codeforces ? ? 并查集 ?    2018-07-10 17:52:07    415    0    0
For long time scientists study the behavior of sharks. Sharks, as many other species, alternate short movements in a certain location and long movements between locations. Max is a young biologist. For n" data-mce-tabindex="0">nn days he watched a specific shark, and now he knows the di
? 解题记录 ? ? 洛谷 ? ? 线段树 ?    2018-07-05 23:15:03    663    0    0
一条东西走向的穆西河将巴邻旁市一分为二,分割成了区域 A" data-mce-tabindex="0">AA 和区域 B" data-mce-tabindex="0">BB。 每一块区域沿着河岸都建了恰好 1000000001" data-mce-tabindex="0">10000000011000000001 栋的建筑,每条岸边的建筑都从 0" data-mce-tabindex="0">00 编号到 1000000000" data-mce-tabindex="0">100000
? 解题记录 ? ? 洛谷 ? ? 线段树 ?    2018-06-24 23:16:11    535    0    0
题目描述共有m部电影,编号为1~m,第i部电影的好看值为w[i]。在n天之中(从1~n编号)每天会放映一部电影,第i天放映的是第f[i]部。你可以选择l,r(1<=l<=r<=n),并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次,你会感到无聊,于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。 输入输出格式输入格式:   第一行两个整数n,m(1<=m<=n<=1000000)。第二行包含n个整数f[1],f[2],…,fn。第三行包含m个整数w[1],w[2],…,wm。