- 浏览: 601183 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
关于树状数组,参看:http://128kj.iteye.com/blog/1743633
POJ3067题意:
东海岸与西海岸分别有N和M个城市,现在修高速公路连接东西海岸的城市,求交点个数。
做法:记每条告诉公路为(x,y), 即东岸的第x个城市与西岸的第y个城市修一条路。当两条路有交点时,满足(x1-x2)*(y1-y2) < 0。所以,将每条路按x从小到达排序,若x相同,按y从小到大排序。 然后按排序后的公路用树状数组在线更新,求y的逆序数之和即为交点个数。
详细说明如下。 记第i条边的端点分别为xi,yi。
由于x是从小到大排序的,假设当前我们在处理第k条边,那么第1~k-1条边的x必然是小于(等于时候暂且不讨论)第k条边的x的,那么前k-1条边中,与第k条边相交的边的y值必然大于yk的,所以此时我们只需要求出在前k-1条边中有多少条边的y值在区间[yk, M]即可,也就是求yk的逆序数,M为西岸城市个数,即y的最大值。 所以就将问题转化成区间求和的问题,树状数组解决。当两条边的x相同时,我们记这两条边的y值分别为ya,yb(ya<yb),我们先处理(x,ya),再处理(x,yb),原因很明显,因为当x相同时,这两条边是认为没有交点的,若先处理(x,yb),那么下次处理(x,ya)时,(x,ya)就会给(x,yb)增加一个逆序,也就是将这两条边做相交处理了。
样例:
Sample Input
1 (一次测试)
3 4 4 (东,西岸的城市数及总的公路数)
1 4 (公路的两端点)
2 3
3 2
3 1
Sample Output
Test case 1: 5
AC代码:
POJ3067题意:
东海岸与西海岸分别有N和M个城市,现在修高速公路连接东西海岸的城市,求交点个数。
做法:记每条告诉公路为(x,y), 即东岸的第x个城市与西岸的第y个城市修一条路。当两条路有交点时,满足(x1-x2)*(y1-y2) < 0。所以,将每条路按x从小到达排序,若x相同,按y从小到大排序。 然后按排序后的公路用树状数组在线更新,求y的逆序数之和即为交点个数。
详细说明如下。 记第i条边的端点分别为xi,yi。
由于x是从小到大排序的,假设当前我们在处理第k条边,那么第1~k-1条边的x必然是小于(等于时候暂且不讨论)第k条边的x的,那么前k-1条边中,与第k条边相交的边的y值必然大于yk的,所以此时我们只需要求出在前k-1条边中有多少条边的y值在区间[yk, M]即可,也就是求yk的逆序数,M为西岸城市个数,即y的最大值。 所以就将问题转化成区间求和的问题,树状数组解决。当两条边的x相同时,我们记这两条边的y值分别为ya,yb(ya<yb),我们先处理(x,ya),再处理(x,yb),原因很明显,因为当x相同时,这两条边是认为没有交点的,若先处理(x,yb),那么下次处理(x,ya)时,(x,ya)就会给(x,yb)增加一个逆序,也就是将这两条边做相交处理了。
样例:
Sample Input
1 (一次测试)
3 4 4 (东,西岸的城市数及总的公路数)
1 4 (公路的两端点)
2 3
3 2
3 1
Sample Output
Test case 1: 5
AC代码:
import java.io.StreamTokenizer; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; import java.io.OutputStreamWriter; import java.io.IOException; import java.util.Arrays; class Node implements Comparable{//一条公路 int x;//公路的左端点 int y;//另一个端点 public int compareTo(Object b) { int v=((Node)b).x; if(this.x==v) return this.y-((Node)b).y; //x相同,按y升序排序 return this.x-((Node)b).x;//x不同,按x升序排序 } public String toString(){ return ("["+x+","+y+"]"); } } public class Main{ private long C[]; //树状数组 private Node[] edge;//所有公路 private int n,m,k; //东,西岸的城市数及总的公路数 private int lowbit(int t){//计算C[t]展开的项数 return t&(-t); } private long Sum(int k){ //求前k项的和. long sum=0; while(k>0){ sum+=C[k]; k=k-lowbit(k); } return sum; } private void update(int i,int x){ //增加某个元素的大小,给某个节点 i 加上 x while(i<=m){ C[i]=C[i]+x; //更新父节点 i=i+lowbit(i); } } public static void main(String[] args) throws IOException{ Main ma=new Main(); ma.go(); } public void go() throws IOException{ StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); int T=0; int cas; st.nextToken(); cas= (int) st.nval; while(cas-->0){ st.nextToken(); n=(int) st.nval; st.nextToken(); m=(int) st.nval; st.nextToken(); k=(int) st.nval; C=new long[m+1]; edge=new Node[k]; for(int i=0;i<k;i++){ edge[i]=new Node(); st.nextToken(); edge[i].x=(int) st.nval; st.nextToken(); edge[i].y=(int) st.nval; } // for(int i=0;i<edge.length;i++) // System.out.println(edge[i]); Arrays.sort(edge); long ans=0; for(int i=0;i<k;i++){ update(edge[i].y,1); //加入一条公路 ans+=(Sum(m)-Sum(edge[i].y)); //统计 } T++; System.out.printf("Test case %d: %d\n",T,ans); } } }
发表评论
-
求推箱子的最小步数(java)
2014-05-06 08:32 3744题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1654POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2394北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1986import java.util.*; ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3053POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1478POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1928题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1639关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1869关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1877POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1894POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1764POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1643分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2248接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1543关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1396接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2467当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1822关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1817关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1773一、树状数组是干什么的? 平常我们会遇到一些对数组进 ...
相关推荐
【标题】"树状数组练习:POJ 2481(JAVA)" 是一篇关于使用树状数组(也称为线段树)解决编程竞赛问题的文章。这篇文章可能详细讲解了如何运用这种数据结构来解决特定的问题POJ 2481。POJ(Programming Online Judge)...
标题中的“图的深搜+树状数组练习 POJ 3321(JAVA)”指的是一个编程题目,其中涉及到图的深度优先搜索(DFS, Depth First Search)算法和树状数组(也称为线段树,Segment Tree)的数据结构。这个题目来源于POJ...
它扩展了一维树状数组(也称作线段树),能够处理二维或多维的数组更新和查询操作。在POJ 2029这个题目中,我们可能面临的问题是需要对一个二维矩阵进行动态更新和求和查询,例如计算某一个矩形区域内的元素总和。 ...
在本篇中,我们将深入学习二维树状数组的应用,并通过解决POJ 1195问题来实践这一概念。 POJ 1195题目要求我们计算一个二维矩阵中的子矩阵之和。这正是二维树状数组的优势所在,因为我们可以快速地对矩阵的任意矩形...
- **树形DP**:针对树形结构的问题,利用子问题的解来求解原问题。 - 示例题目:POJ 2531, POJ 1416, POJ 2676, 1129 ##### 4. 几何问题 - **凸包**:构建凸包并求解相关的几何问题。 - 示例题目:POJ 1837, POJ...
poj2528、poj2777等是线段树的题目,poj2482、poj2352等涉及平衡树,poj1195、poj3321则训练了树状数组。 5. **搜索算法的优化**:poj1699、poj3411等训练搜索技巧和剪枝方法,poj3373、poj1691则介绍了记忆化搜索。...
4. 数据结构高级应用:线段树、静态二叉检索树、树状数组、RMQ和并查集的更复杂用法。 5. 搜索优化:最优化剪枝、搜索技巧和记忆化搜索。 这些内容构成了一个全面的ACM训练框架,旨在全面提升参赛者的编程思维、...
- **定义**: 一种用于存储字符串的树形结构。 - **应用场景**: 字典管理。 - **示例题目**: POJ 2513 - **注意事项**: 区分静态建树和动态建树的不同。 #### 四、简单搜索 **1. 深度优先搜索** - **定义**: ...
- 高级数据结构如线段树、树状数组等可以提高程序效率。 2. **状态压缩** - 推荐题目:[poj2482](https://vjudge.net/problem/POJ-2482)、[poj2352](https://vjudge.net/problem/POJ-2352) - 状态压缩DP用于处理...
在初级阶段的基础上,中级阶段涵盖了更多复杂的数据结构和算法,如差分约束系统、最小费用最大流、双连通分量、强连通分支、最小割模型等,以及线段树、树状数组、RMQ查询等高级数据结构的应用。这些内容进一步深化...
在题目描述中提到,一个公司内部的员工关系构成一棵树形结构,其中每个员工(除了最高级别的老板)都有一个直属上司。公司计划举办一场聚会,希望邀请尽可能多的员工参加。但存在一定的限制条件:如果某员工参加聚会...
- **定义**: 树状树组是一种用于维护动态数组的高效数据结构。 - **应用场景**: 在区间查询、动态数组等问题中有广泛应用。 - **示例题目**: - poj1195: 涉及树状树组的应用。 以上内容涵盖了ACM竞赛中涉及到的...
树形结构 - **题目**: 如`poj2488`、`poj3083`等。 - **所需知识**: 树的定义、遍历方法、特殊树结构(如二叉查找树、红黑树等)。 #### 2. 字符串处理 - **题目**: 包括`poj3278`、`poj1426`等。 - **所需知识*...
- 高级数据结构:平衡树(AVL树、红黑树)、线段树、树状数组、并查集等。 - 特殊的数据结构:后缀数组、LCP数组等用于文本处理的高效结构。 #### 6. 几何题 几何题通常涉及到几何图形的性质、计算等。 - **知识点*...
10. T062.cpp - 可能是树形结构问题,如二叉树或树的遍历,C++的递归和指针操作是基础。 通过分析和学习这些源码,开发者不仅可以提升C++编程技巧,还能加深对算法的理解,对于参加ACM/ICPC等编程竞赛或者提高软件...
- **技能提升**:项目涉及的数据结构(如二维数组、树形图、向量等)和算法(如字符串处理、文件读写)对于提高编程技能非常有帮助。 - **创新思维**:在解决具体问题时,鼓励学生思考不同的解决方案,培养创新思维...
- **数据结构**:掌握线段树、静态二叉检索树、树状数组等高级数据结构。 - **搜索**:进一步学习最优化剪枝和可持久化数据结构。 通过以上步骤,持续练习和分析题目,你可以逐渐提高算法能力。同时,理解每种...
- **最小生成树**:Prim算法和Kruskal算法用于寻找边权和最小的树形子图。 - **拓扑排序**:对于有向无环图(DAG),可以进行拓扑排序来确定事件的顺序。 3. **数据处理**: - **排序**:快速排序、归并排序、堆...
1. **高级数据结构**(如poj2528, poj2828, poj2777, poj2886, poj2750):包括线段树、树状数组、Trie树等,用于解决复杂的数据查询和更新问题。 2. **平衡树**(如poj2482, poj2352):如AVL树、红黑树等,保持树...